Induktionsbeweise

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Induktionsbeweise
Hallo,

inzwischen habe ich mich an die Aufgaben herangewagt, die einen Beweis per Induktion erfordern.
Das Vorgeplänkel gelingt mir einigermaßen, doch wenn es an den Induktionsschritt geht, fehlen mir die Worte. Ich weiß nicht, wie ich das formulieren muss.
Auch bei der Induktionsvoraussetzung bin ich mir nicht sicher.
Kann mir hier jemand weiterhelfen?

Lieben Dank im Voraus.

[m] S
/
U V
/
aUb aaVb
/
ɛ aaVb

ɛ[/m]

L = {a^nb^na^(2p)b^p}

Zunächst sei definiert:
n = Anzahl an Ableitungsschritten
N = Anzahl an verbleibenden Variablen

Induktionsanfang
Basisfall ist: n = 0 = {a^(2p)b^p}, welches tatsächlich von G erzeugt wird, wie folgender Ableitungsbaum zeigt:

[m] S
/
U V
/
ɛ aaVb

…[/m]

Induktionsvoraussetzung
∃n∈ℕ:
Was genau ist hier die Voraussetzung?

Induktionsbehauptung
G erzeugt L = {a^nb^na^(2p)b^p}

Induktionsschritt
Wenn G die Sprache L = {a^nb^na^(2p)b^p} erzeugt, dann erzeugt es auch {a^(n+1)b^(n+1)a^(2p)b^p} (Ersetze m := +1).
⇒ G erzeugt L.
Genügt das so? Ich weiß nicht so recht, wie ich hier Schritte darstellen soll.

Die nächste Aufgabe:

Induktionsanfang
g(x) ist definitionsgemäß LOOP-berechenbar.
f(x,0) = g(x) ⇒ f(x,0) ist trivial LOOP-berechenbar, weil identisch mit g(x).
f(x,y+1) ist LOOP-berechenbar, wenn h(x,y,f(x,y)) LOOP-berechenbar ist.

Induktionsvoraussetzung
∃n∈ℕ: f(x) ist LOOP-berechenbar

Induktionsbehauptung
f(x+n) ist LOOP-berechenbar

Induktionsschritt
Da die LOOP-berechenbare Funktion h nur abhängig ist von den Parametern x und y (die trivial LOOP-berechenbar sind) sowie von f(x,y), ist h(x,y,f(x,y)) LOOP-berechenbar, wenn f(x,y) LOOP-berechenbar ist.
Deswegen ist f(x,y+1) LOOP-berechenbar, wenn f(x,y) LOOP-berechenbar ist.
Zusammen mit dem Basisfall ergibt sich über Induktion die zu beweisende Eigenschaft.
⇒ f(x) ist LOOP-berechenbar
Auch hier: Genügt das so? Ist vermutlich viel zu informell.

LG Forumsnutzer


Ein bisschen genauer: [m]L = {a^n b^n a^(2p) b^p | n, p >= 0}[/m]

[quote=Forumsnutzer]Zunächst sei definiert:
n = Anzahl an Ableitungsschritten
N = Anzahl an verbleibenden Variablen[/quote]
Du induzierst also über Länge von (vollständigen, d.h. am Ende variablenfreien) Ableitungen. Wie können da Variablen noch verbleiben?

Ein = kann hier ganz sicher nicht stehen. Und es gibt keine Ableitungen der Länge 0. Das ist wohl ein bisschen Definitionssache, aber in deiner Grammatik musst du ja mindestens U und V ableiten. Und das geht weder in 0 noch 1 Schritt. Also ist im Induktionsanfang nichts zu zeigen, würde ich sagen.

[quote=Forumsnutzer]Induktionsvoraussetzung
∃n∈ℕ: [/quote]
Wieso ∃? Meines Erachtens wäre die IV hier: alle Wörter w \in {a, b}^*, die sich in n Schritten von der Grammatik G ableiten lassen, sind auch Element von L.

Induktionsvoraussetzung ist übrigens synonym zu Induktionsbehauptung. Insofern macht es keinen Sinn, verschiedene Dinge damit zu meinen.

Was ist n und was ist p? Sind die fest? Sind die gebunden in der Mengennotation {…}? Falls gebunden, was macht (n+1) dann für einen Sinn?
Das ist genau die Formalität, die man mit paar Semestern Mathe bekommt, wie ich im anderen Beitrag meinte :slight_smile:

Dein Beweis ergibt für mich leider gar keinen Sinn.

Bei der LOOP-Berechenbarkeit: worüber induzierst du? Schreib es bitte hin. Ich nehme an, du induzierst über das zweite Argument von f?

Du meinst „g ist definitionsgemäß LOOP-berechenbar“. (Verschiedene Menschen haben verschiedene Meinungen darüber, ob auch „g(x)“ nur für die Funktion „g“ stehen kann [und das „x“ ohne Bedeutung ist]. Ich teile diese Meinung nicht – zumindest nicht hier.)

Das macht keinen Sinn, wenn du über das zweite Argument von f induzierst.

Was ist n, was ist x? Warum ∃?

2 „Gefällt mir“

Geb ich dir fast recht, aber dann ist der IA für (Ableitungsschritte = 2) zu machen und zu beweisen.


[quote]Das ist genau die Formalität, die man mit paar Semestern Mathe bekommt, wie ich im anderen Beitrag meinte :slight_smile:
(…)
Dein Beweis ergibt für mich leider gar keinen Sinn.[/quote]
Ja, und ich bin diesen Aufgaben offenbar nicht gewachsen.
Es erklärt einem ja auch niemand. Es wird einfach vorausgesetzt, dass man das kann.
Daraus ergeben sich dann die folgenden Patzer:

Gar nicht. Wäre Anzahl an Terminalsymbolen sinnvoller?

Ein = kann hier ganz sicher nicht stehen. Und es gibt keine Ableitungen der Länge 0. Das ist wohl ein bisschen Definitionssache, aber in deiner Grammatik musst du ja mindestens U und V ableiten. Und das geht weder in 0 noch 1 Schritt. Also ist im Induktionsanfang nichts zu zeigen, würde ich sagen.[/quote]
Hier dachte ich, müsste man immer einen Basisschritt machen, weil Induktion das halt so will. Also weglassen?

[quote][quote=Forumsnutzer]Induktionsvoraussetzung
∃n∈ℕ: [/quote]
Wieso ∃?
(…)
Induktionsvoraussetzung ist übrigens synonym zu Induktionsbehauptung. Insofern macht es keinen Sinn, verschiedene Dinge damit zu meinen.
[/quote]
Hatte ich mir von Youtube abgeschaut. Also auch weglassen?

Was ist n und was ist p? Sind die fest? Sind die gebunden in der Mengennotation {…}? Falls gebunden, was macht (n+1) dann für einen Sinn?[/quote]
Damit will ich sagen, dass die Symbole, die ein n bzw. im Exponenten haben, gleich bzw. doppelt so häufig vorkommen, eben abhängig von n oder p.
n+1 ist ein Ableitungsschritt tiefer als n gelegen auf dem Ableitungsast der Produktionsregel U → aUb | ɛ.
Und wenn das möglich ist, wie der Ableitungsbaum ja demonstriert, so sind doch auch dementsprechend beliebig viele weitere Ableitungsschritte möglich, oder?
Wie müsste ich fest oder gebunden erklären?

[quote=Marcel]Bei der LOOP-Berechenbarkeit: worüber induzierst du? Schreib es bitte hin. Ich nehme an, du induzierst über das zweite Argument von f?

Du meinst „g ist definitionsgemäß LOOP-berechenbar“. (Verschiedene Menschen haben verschiedene Meinungen darüber, ob auch „g(x)“ nur für die Funktion „g“ stehen kann [und das „x“ ohne Bedeutung ist]. Ich teile diese Meinung nicht – zumindest nicht hier.)

Das macht keinen Sinn, wenn du über das zweite Argument von f induzierst.

Was ist n, was ist x? Warum ∃?[/quote]

Zweite Aufgabe war mal ein Blindschuss auf gut Glück.
Ich weiß ja nicht, wie ich den Basisfall beweisen kann, geschweige denn den Induktionsschritt.
Hier bin ich mit meinem Latein am Ende.


Zweiter Versuch für die erste Aufgabe. Wahrscheinlich wimmelt sie wieder vor Formfehlern und wird entsprechend zerpflückt, aber ich habe mein Bestes gegeben:

Zunächst sei definiert:
n = Ableitungsschritte auf U-Ast ausgehend von Variable U
p = Ableitungsschritte auf V-Ast ausgehend von Variable V

Induktionsanfang
Nach der Startvariablen S verlaufen die Ableitungen der Grammatik entlang zweier unabhängiger Äste über die Variablen U und V.
Es müssen also zwei Basisfälle unterscheiden werden für die beiden Variablen U und V, auf denen unabhängig voneinander abgeleitet werden kann, so dass sie isoliert betrachtet werden können.

Für n = 1 gilt L={a^(2p) b^p} gibt es zwei mögliche Ableitungen:
[m] S S
| |
V V
| |
aaVb ɛ [/m]
wobei gilt aab,ɛ ∈L(a^n b^n a^(2p) b^p)

Für p = 1 gilt L = {a^n b^n}, gibt es zwei mögliche Ableitungen::
[m] S S
| |
U U
| |
aVb ɛ [/m]
mit ab,ɛ ∈L(a^n b^n a^(2p) b^p | n,p ≥ 0)

Die Verkettung der beiden Basisfälle L={a^(2p) b^p}∘{a^n b^n} entspricht L(a^n b^n a^(2p) b^p), also gilt auch L={a^(2p) b^p}∘{a^n b^n} ∈L(a^n b^n a^(2p) b^p).

Induktionsbehauptung
L(G) ⊆ L = (a^n b^n a^(2p) b^p | n,p ≥ 0),
L erzeugt also ausschließlich Wörter w, für die gilt: w ∈L(a^n b^n a^(2p) b^p | n,p ≥ 0) ⇒ w ∈L(G)

Induktionsschritt
Seien n und p beliebig, aber konstant.
Wenn G die Sprache L = {a^n b^n a^(2p) b^p} erzeugt, dann erzeugt es auch {a^⁽n+1) b^(n+1) a^(2(p+1)) b^(p+1)}, wobei wieder zwei Fälle zu unterscheiden sind:
[m] S S
/ \ / \
U V U V
/ \ /
aUb aaVb aUb aaVb
/ \ /
aUb aaUb ɛ ɛ
/
… … [/m]
mit ab,aabb,aabb,aaaabb ∈L(a^n b^n a^(2p) b^p | n,p ≥ 0)

⇒ Die Induktionsbehauptung ist richtig,
L(G) ⊆ L ((a^n b^n a^(2p) b^p | n,p ≥ 0).


Du kannst ja dem Modulverantwortlichen schreiben, dass dieser die Voraussetzungen im UnivIS das nächste Mal bessern soll :slight_smile:
Das nächste Mal einfach mal hier im Forum oder in einem Informatikerchat nachfragen. Es hätte dir wahrscheinlich jeder davon abgeraten, TheoInf zu belegen, wenn du weder ein Mathe- noch AuD-Wissen besitzt.

Nichts für ungut, aber das ist wahrscheinlich meine letzte fachliche Antwort hier. Dir fehlen zu viele Grundlagen, als dass ich Hoffnung hätte, dir mit fachlichen Antworten irgendwie helfen zu können. Das Forum ersetzt keine 2-3 Semester, die du bräuchtest, um dir diese Grundlagen anzueignen.

Gar nicht. Wäre Anzahl an Terminalsymbolen sinnvoller?[/quote]
Dein Ziel ist „L(G) \subset L“, d.h. „\forall w \in L(G). w \in L“. Dein Kommentar zielt darauf ab, über |w| zu induzieren, korrekt?

@yq53ykyr: Du kannst den IA für n=0 schon machen, ist halt „vacuous truth“. Möglicherweise wird der IS dann wesentlich härter oder selbst eine Fallunterscheidung (im Vergleich dazu, als wie wenn du den IA für n=2 gemacht hättest.)

Nein, den IA brauchst du immer. Aber wenn ihn als n=0 wählst, ist der hier trivial. Stichwort „vacuous truth“. Aber wahrscheinlich hast du auch keine Einführung in Logik bisher gehört?

Ohne das Video gesehen zu haben: der Existenzquantor macht da nicht so viel Sinn.

Was ist n und was ist p? Sind die fest? Sind die gebunden in der Mengennotation {…}? Falls gebunden, was macht (n+1) dann für einen Sinn?[/quote]
Damit will ich sagen, dass die Symbole, die ein n bzw. im Exponenten haben, gleich bzw. doppelt so häufig vorkommen, eben abhängig von n oder p.[/quote]
Also möchtest du n und p binden, d.h. wie in [m]L = {a^nb^na^(2p)b^p | n, p >= 0}[/m]? Hier bindet „n, p >= 0“ die Variablen n und p.
Aber dann macht dein nächster Ausdruck mit n+1 keinen Sinn. Syntaktisch valide ist der schon (wenn man sich n,p >= 0 dazudenkt), aber Sinn machen tut der hier nicht.

Du solltest immer schreiben, worüber du induzierst. Bei deinem letzten Post („zweiter Versuch für die erste Aufgabe“) ist nicht klar, worüber du induzierst. Auch, was n und p genau sind, ist nicht definiert. Sind diese für ein jeweils bestimmtes Wort w \in L(G) definiert? D.h. eigentlich ist n eine Funktion von Ableitungen von Wörtern w \in L(G) nach den natürlichen Zahlen?

Die Gleichung mit L gilt nicht. Was ist „L“ für dich? L ist doch in der ersten Teilaufgabe fest definiert worden. Es ist nicht von irgendeinem Fall abhängig, was es ist.

1 „Gefällt mir“

Ich verstehe deine Anmerkungen zum Teil, kapier aber immer noch nicht, wie ich das selbst auf die Reihe bekommen kann.

Also fehlen mir offenbar wichtige Grundlagen. Nun gut. Kopf hängen lassen kann man machen, bringt aber nichts.
Ich geh entspannt und ohne große Hoffungen in die Prüfung am Dienstag. Sollte ich wieder erwarten mit 4,0 bestehen, dann wäre das halt ein kleiner Trostpreis.

Aber mal kurzer Themenwechsel. Wenn man bei Informatik dauernd stolpert über fehlende Grundlagen, sollte ich mein weiteres Studien gut planen. Es wurde der Modulplan von der Seite vom Fachbereich gerade, warum auch immer, nicht abrufbar. Aber so viel ich weiß, muss ich unter anderem Folgendes ableisten:

Algorithmen und Datenstrukturen
Parallele und Funktionale Programmierung
Theoretische Informatik für Wirtschaftsinformatik und Lehramt
Implementierung von Datenbanksystemen
Software-Entwicklung in Großprojekten
Mathematik für Naturwissenschaftler
Konzeptionelle Modellierung
Didaktik der Informatik I
Didaktik der Informatik II
Seminar Didaktik der Informatik

Davon sind meins Wissens im Wintersemester verfügbar:
Algorithmen und Datenstrukturen
Implementierung von Datenbanksystemen
Software-Entwicklung in Großprojekten
Mathematik für Naturwissenschaftler
Didaktik der Informatik II
Seminar Didaktik der Informatik

Für AuD versuche ich gerade, mich noch durchzuarbeiten durch das Java-Repetitorium.
Was davon kann ich sinnvollerweise belegen kommendes Semester?

LG Forumsnutzer


Algorithmen und Datenstrukturen ist die grundlegenste Grundlagenveranstaltung im Informatik-Studium. Studenten im ersten Semester hören auch alle AuD. IMHO solltest du auf jeden Fall AuD belegen.

Didaktik der Informatik kenne ich nicht. Von Mathematik für Naturwissenschaftler gehe ich mal davon aus, dass es sich nur wenig von Mathematik für Informatiker unterscheidet.

In dem Fall würde ich persönlich dazu raten, auf jeden Fall AuD und Mathe zu hören.

Implementierung von Datenbanksystemen baut etwas auf AuD auf und sollte vermutlich nicht ohne AuD-Vorwissen gehört werden. Software-Entwicklung in Großprojekten ist eine Blödsinnsveranstaltung ohne nennenswerten Erkenntnisgewinn in irgendeine Richtung. Sonderlich viel Vorwissen erfordert es auch nicht, aber etwas AuD kann nicht schaden (dann kennt man z.B. UML bereits).

Theoretische Informatik für Wirtschaftsinformatik und Lehramt ist das Modul, auf das sich deine Fragen im Forum beziehen, korrekt? Solltest du also die Prüfung nicht bestehen, dann ist es unumgänglich, dass du die Veranstaltung im nächsten Semester gewissenhaft besuchst, inklusive Übungsabgaben, um dich auf die Wiederholungsklausur vorzubereiten.

Disclaimer: Ich studiere seit ~2 1/2 Jahren nicht mehr. Dinge könnten sich geändert haben, und Covid-bedingt könnten sich auch Regelungen bzgl. Wiederholerklausuren aufgeweicht haben. Lass dich lieber noch einmal von jemandem beraten, der näher dran ist.

4 „Gefällt mir“

[quote=Forumsnutzer]Aber mal kurzer Themenwechsel. Wenn man bei Informatik dauernd stolpert über fehlende Grundlagen, sollte ich mein weiteres Studien gut planen. Es wurde der Modulplan von der Seite vom Fachbereich gerade, warum auch immer, nicht abrufbar. Aber so viel ich weiß, muss ich unter anderem Folgendes ableisten:

Algorithmen und Datenstrukturen
Parallele und Funktionale Programmierung
Theoretische Informatik für Wirtschaftsinformatik und Lehramt
Implementierung von Datenbanksystemen
Software-Entwicklung in Großprojekten
Mathematik für Naturwissenschaftler
Konzeptionelle Modellierung
Didaktik der Informatik I
Didaktik der Informatik II
Seminar Didaktik der Informatik

Davon sind meins Wissens im Wintersemester verfügbar:
Algorithmen und Datenstrukturen
Implementierung von Datenbanksystemen
Software-Entwicklung in Großprojekten
Mathematik für Naturwissenschaftler
Didaktik der Informatik II
Seminar Didaktik der Informatik[/quote]Ich kenne als Informatiker nur AuD, KonzMod, PFP, SoSy3 und IDB. KonzMod wird auch im Winter angeboten.

[quote=Forumsnutzer]Für AuD versuche ich gerade, mich noch durchzuarbeiten durch das Java-Repetitorium.
Was davon kann ich sinnvollerweise belegen kommendes Semester?[/quote]Wie viel Zeit hast du? Ich würde AuD und KonzMod machen, wenn du das Repetitorium nötig hast und nebeinbei noch andere Veranstaltungen besuchst. SoSy3 und IDB bauen beide auf KonzMod auf. Man kommt aber auch ohne Vorkenntnisse in UML und SQL durch.


Was studierst du eigentlich? Winf oder Lehramt oder etwas anderess? (Sorry, wenn ich das oben überlesen haben sollte)

Für die Inklusion L(G) ⊆ L sollte man sich erstmal überlegen, was man überhaupt per Induktion beweisen möchte. Die Grundidee hier wurde in diesem Thread nämlich noch nicht genannt, findet sich aber eigentlich in VL + Übung:

Zu zeigen: alle Ableitungen S → … → in der Grammatik mit Länge mindestens 1 führen zu einem Wort der Form a^n U^m b^n a^(2p) V^k b^p wobei n,p≥0 und m,k∈{0,1}

Diese Wörter aus Terminalen und Nicht-Terminalen haben auch einen Namen, der mir nur gerade nicht einfällt ;)… Nun zum eigentlichen Beweis:

Induktionsanfang: die Einzige Ableitung der Länge 1 ist S → UV und damit von der ersten Form mit n=p=0.

Induktionsschritt (l → l+1): Betrachte eine Ableitung der Länge l+1. Wir wissen per Induktionsvoraussetzung, dass die ersten l Schritte dieser Ableitung zu einem Wort führt das von einer der vier o.g. Formen führt, d.h. ein Wort a^n U^m b^n a^(2p) V^k b^p mit m,k∈{0,1}. Per Fallunterscheidung über die letzte (d.h. l+1te) Grammatikregel in der Ableitungskette zeigen wir, dass das letzte Wort in der Ableitsungskette wieder von dieser Form ist:

  • Der letzte Schritt kann nicht S → UV sein, da kein S enthalten ist.
  • Nutzt der letzte Schritt U → aUb, dann ist m=1 und somit das neue Wort a^(n+1) U^m b^(n+1) a^(2p) V^k b^p von der gewünschten Form
  • Nutzt der letzte Schritt U → ɛ, dann ist m=1 und somit das neue Wort a^n b^n a^(2p) V^k b^p von der gewünschten Form
  • Nutzt der letzte Schritt V → aaVb, dann ist k=1 und somit das neue Wort a^n U^m b^n a^(2p+2) V^k b^(p+1) von der gewünschten Form
  • Nutzt der letzte Schritt V → ɛ, dann ist k=1 und somit das neue Wort a^n U^m b^n a^(2p) b^p von der gewünschten Form

Hier ist jetzt der Induktionsbeweis fertig. Aus der per Induktion bewiesenen Aussage folgt:
Wenn ein Wort von der soeben gezeigten Form ist und gleichzeitig nur Terminalsymbole enthält, dann ist es von der Form a^n b^n a^(2p) b^p, n,p≥0, und damit in L enthalten; folglich L(G) ⊆ L

3 „Gefällt mir“

[quote=Forumsnutzer]Also fehlen mir offenbar wichtige Grundlagen. Nun gut. Kopf hängen lassen kann man machen, bringt aber nichts.
Ich geh entspannt und ohne große Hoffungen in die Prüfung am Dienstag. Sollte ich wieder erwarten mit 4,0 bestehen, dann wäre das halt ein kleiner Trostpreis.[/quote]

Beachte, dass du nur eine begrenzte Anzahl an Versuchen für jede Prüfung hast und nach einem Fehlversuch die restlichen konsekutiv sein müssen – zumindest ist das der Fall im reinen Informatikstudium. Ich weiß nicht, welche Fachprüfungsordnung für dich infrage kommt. In der Informatik jedenfalls hast du maximal 3 Versuche. Und bei einem Fehlversuch wirst du im nächsten Semester gleich zwangsangemeldet.

Deshalb melden sich viele 3 Werktage vor Prüfungstermin regulär via Mein Campus von Prüfungen ab, denn das zählt nicht als Fehlversuch und du kannst dich für die Prüfung in einer der nächsten Semester oder auch nie wieder anmelden – was du eben willst.

Da deine Prüfung am Dienstag ist, bleibt nur noch, wie du selbst richtig sagst, Folgendes :slight_smile:

1 „Gefällt mir“

Vorsicht: das ergibt keinen Sin! du sollst Zeigen, dass f LOOP-Berechenbar ist, aber du sagst irgendwas mit „f(x,y) ist LOOP-Berechenbar“, was keinen Sinn ergibt, denn f(x,y) ist eine natürliche Zahl (Also z.B. 1, 5, oder 8), und für natürliche Zahlen ist die Eigenschaft „LOOP-Berechenbarkeit“ gar nicht definiert. (Sollte die 5 (in Worten: fünf) jetzt LOOP-Berechenbar oder nicht sein? ;)). Die definition von X LOOP-Berechenbarkeit beginnt ja mit „Es gibt ein LOOP-Program das X berechnet“. Du musst diese Definition hier dreimal nutzen: 1. um zu zeigen dass f LOOP-Berechenbar ist (setze f für X in der definition ein), 2. um auszunutzen, dass g LOOP-Berechenbar ist (setze g für X ein), 3. um auszunutzen, dass h LOOP-Berechenbar ist.

2 „Gefällt mir“

Das war jetzt wirklich sehr hilfreich. Vielen lieben Dank!
Heute sind meine Batterien leer, aber ich werde mir deinen Beweis morgen sicher noch ein paar mal durchlesen und darüber meditieren. Vielleicht kann ich mir dadurch die Denkweise aneignen.

Mein lieber Scholli. Da muss man ja echt höllisch aufpassen. Hoffe, dass ich das im Laufe des Studiums lerne. Danke für die Hinweise, ich wäre wahrscheinlich nicht drauf gekommen.

Vielen Dank für alle die Hinweise hier! Scheint ja hier immerhin eine durchaus sehr lebendige Forums-Gemeinde zu geben.
Ich find’s jedenfalls total klasse, wie viel Hilfsbereitschaft einem hier entgegenkommt. :slight_smile:


[quote=errnosys]
Was studierst du eigentlich? Winf oder Lehramt oder etwas anderess? (Sorry, wenn ich das oben überlesen haben sollte)[/quote]

Ich studiere für ein Lehramt an Realschulen.

Inzwischen habe etwas meditiert über deinen Beweis. Nochmals vielen Dank dafür!
Wenn man keinen Plan hat, dann ist es nichts als Frust.
Aber sobald man das zu verstehen beginnt, beginnt es tatsächlich auch Spaß zu machen.

Kannst du mir sagen, wo ihm Skript ich das finde? Ich würde die Folie(n) gerne mal nachlesen.

Das Klammerzeichen war ein Flüchtigkeitsfehler, oder?

[quote=errnosys]Hier ist jetzt der Induktionsbeweis fertig. Aus der per Induktion bewiesenen Aussage folgt:
Wenn ein Wort von dieser Form ist[/quote]
Von welcher? Der in der Induktionsbehauptung (a^n U^m b^n a^(2p) V^k b^p)?

Eine Frage: Ich hatte ja im Aufgabenteil (b) die mengentheoretische Beschreibung L((a^n b^n a^(2p) b^p) gegeben. Von ihr möchte ich ja ihre Teilmengenbeziehung zu L(G) beweisen. Nun wird L in der Induktionsbehauptung ergänzt um die Nichtterminale (a^n U^m b^n a^(2p) V^k b^p). Ist das zulässig? Und wenn ja, wieso?


  1. s ↩︎


[quote=Forumsnutzer]Eine Frage: Ich hatte ja im Aufgabenteil (b) die mengentheoretische Beschreibung L((a^n b^n a^(2p) b^p) gegeben. Von ihr möchte ich ja ihre Teilmengenbeziehung zu L(G) beweisen. Nun wird L in der Induktionsbehauptung ergänzt um die Nichtterminale (a^n U^m b^n a^(2p) V^k b^p). Ist das zulässig? Und wenn ja, wieso?
[/quote]

Der Beweis von errnosys beweist „L(G) ⊆ L“ nicht (nicht direkt) via Induktion. Er beweist zuerst ein Hilfslemma,

und erst dann leitet er die eigentlich zu zeigende Aussage davon ab:

[quote=errnosys]Aus der per Induktion bewiesenen Aussage folgt:
Wenn ein Wort von dieser Form ist und gleichzeitig nur Terminalsymbole enthält, dann ist es von der Form a^n b^n a^(2p) b^p, n,p≥0, und damit in L enthalten; folglich L(G) ⊆ L[/quote]

Das ist ziemlich sicher auch so im Sinne der Aufgabenstellung gewesen:

Strikt genommen eben nicht, aber jeder Informatiker/Mathematiker (ohne weiteren Zusammenhang) würde sagen, dass errnosys’ gesamter Beweis per Induktion über der Länge von Ableitungen ist.

3 „Gefällt mir“

Hier errnosys’ Beweis in ausführlicherer Form:

Hilfslemma: alle Ableitungen S → … → in der Grammatik G mit Länge mindestens 1 führen zu einem Wort der Form a^n U^m b^n a^(2p) V^k b^p wobei n,p≥0 und m,k∈{0,1}

Beweis des Hilfslemmas: wir haben ein allquantifiziertes Statement über Ableitungen. Deswegen können wir über Ableitungen induzieren, genauer gesagt: über deren Längen.

IA: die einzige Ableitung der Länge 1 ist S → UV und damit von der ersten Form mit n=p=0.

IS (l → l+1): Die IH ist:

Zu zeigen im IS ist hier:

Um das allquantifizierte Statement zu zeigen, sei also eine beliebige „Ableitung S → … → in der Grammatik G der Länge l+1 mit Länge midestens 1 gegeben“. (Wir vergeben hier keinen Namen für diese Ableitung. Normalerweise tut man das in einem IS, aber hier benötigen wir im Folgenden keinen.) Wir zeigen, dass es zu einem Wort der Form … führt (wie im Zitat).

Per Fallunterscheidung über die letzte (d.h. l+1te) Grammatikregel in der Ableitungskette zeigen wir, dass das letzte Wort in der Ableitsungskette wieder von dieser Form ist:

  • Der letzte Schritt kann nicht S → UV sein, da kein S enthalten ist.
  • Nutzt der letzte Schritt U → aUb, dann ist m=1 und somit das neue Wort a^(n+1) U^m b^(n+1) a^(2p) V^k b^p von der gewünschten Form
  • Nutzt der letzte Schritt U → ɛ, dann ist m=1 und somit das neue Wort a^n b^( a^(2p) V^k b^p von der gewünschten Form
  • Nutzt der letzte Schritt V → aaVb, dann ist k=1 und somit das neue Wort a^n U^m b^n a^(2p+2) V^k b^(p+1) von der gewünschten Form
  • Nutzt der letzte Schritt V → ɛ, dann ist k=1 und somit das neue Wort a^n U^m b^n a^(2p) b^p von der gewünschten Form

— Beweis des Hilfslemmas fertig.

Korollar: L(G) ⊆ L

Beweis des Korollars: Sei w ein Wort aus L(G). Daraus folgt, dass es eine Ableitung via Grammatik G gibt. Wende das Hilfslemma an: wir schließen w = a^n U^m b^n a^(2p) V^k b^p für irgendwelche n, m, p, k. Da w aus L(G), d.h. nur Terminalsymbole enthält, wissen wir, dass w = a^n b^n a^(2p) b^p. Damit ergibt sich direkt: w in L.

— Beweis des Korollars fertig.

3 „Gefällt mir“

[quote=Forumsnutzer]
Kannst du mir sagen, wo ihm Skript ich das finde? Ich würde die Folie(n) gerne mal nachlesen.[/quote]

Das weiß ich leider nicht, sorry

Ja, danke! Ist jetzt ausgebessert.

Ja genau, ich hab das auch mal im Post oben klar gestellt.


  1. s ↩︎

1 „Gefällt mir“

Boah, vielen Dank, ich bin echt beeindruckt über die Ausführlichkeit eurer Beiträge!

Verzeihung, leider hab ich Seite 2 gestern nicht mehr bemerkt, sonst hätte ich eher geantwortet.
Nun ist gleich die Klausur, ich würde mich nach der Klausur nochmal melden. Bestehe sie wahrscheinlich eh nicht.
Finde aber, dass ich nun einen deutlich besseren Ausgangspunkt habe, die Klausur beim nächsten Mal, auch mit einer guten Note, zu bestehen.
Wenn ich dann noch etwas Mathe-Grundlagen parallel gemacht habe, sollte es vermutlich deutlich leichter von der Hand gehen.


Also dann, ich bin zurück aus der Klausur.

Es kam tatsächlich eine Aufgabe genau dieser Machart dran, und ich kam auch dazu, eine Grammatik zu erstellen. Leider ist mir nur eine eingefallen, die gleich fünf oder sechs Nichtterminale benötigte, so dass die Fallunterscheidung dann arg umfangreich ausfiel, weswegen ich sie nach ein paar Fällen “abkürzen” musste mit “…”.
Eine Kommilitonin konnte mir nach der Klausur noch eine Lösung vorstellen mit nur zwei Nichtterminalen, auf die ich allerdings nicht gekommen war.

Überhaupt hat der Zeitfaktor wahrscheinlich mein Scheitern verursacht, denn eigentlich habe ich mehr oder weniger von Anfang bis Ende geschrieben, aber nicht immer besonders strukturiert und schnell.
Da muss man ja echt pfeilschnell analysieren und niederschrieben. Das Gefühl schienen die anderen zu teilen.

Für besagten Beweis etwa ist ja allein die Schreibarbeit schon recht zeitraubend.
Da ich mit den formalen Vorgaben nicht vertraut bin, frage ich mich halt: was davon muss wirklich in der Klausur niedergeschrieben werden? Oder gäbe es da irgendwelche mathematischen Zauberformeln, die Besagtes in ein paar Zeichen zusammenfassen könnten?

Wirklich, sollte ich nicht bestanden haben, muss ich mir nächstes Mal noch ein, zwei weitere Aufgabentypen etwas gründlicher verstehen und an meiner Schnelligkeit arbeiten. Dann wäre auch das heute kein Problem gewesen.