| |
| Autor |
 Verständnisprobleme: Beweis, dass L(G) = {a^n b^n c^n | n >= 1} |
|
MrObvious
Junior 
Dabei seit: 22.03.2023
Mitteilungen: 5
 |  Themenstart: 2023-03-22
|
Guten Abend,
bin hier neu im Forum.
Bin gerade im 4. Semester für Informatik B. Sc. und ich habe jetzt das Modulfach \darkblue\ Theoretische Informatik \black\(gerade im Wiederholungsanlauf wegen Corona letztes Jahr usw.).
Bin damit schon etwas vertraut mit dem Stoff,
\red\ aber meine Mathe-Kenntnisse (besonders Beweisführung und Beweisarten) sind echt grottenschlecht.
Potenzmengen usw., dem kann ich noch folgen,
aber sobald das kreative Denken bei Beweisführungen anfängt,
dann fällt es mir sehr schwer.
Jetzt haben wir auf jeden Fall in der ersten Vorlesungseinheit einen Übungszettel bekommen und da konnte ich alles so durchrattern (9 Aufgaben von 11 bis jetzt und von Alphabet bis EBNF alles dabei).
Jetzt bleibe ich wie so üblich bei einem Beweis wieder hängen..
\red\ Die Aufgabe ist so gestellt:
Auf Seite 7 in \darkblue\Theoretische Informatik - kurz gefasst\black\ Buch ist folgende
Grammatik G = (V, \Sigma, P, S) angegeben:
V = {S, B, C}
\Sigma = {a, b, c}
P = {S -> aSBC, S -> aBC, CB -> BC, aB -> ab, bB -> bb, bC -> bc, cC -> cc}
In der Vorlesung wurde gezeigt, wie man a^3 b^3 c^3 ableiten kann.
Auf Seite 8 in o.g. Buch wird bewiesen, dass gilt:
L(G) = {a^n b^n c^n \| n >= 1}.
(\supersetequal\) Der oben angegebene Fall n = 3 lässt sich leicht für beliebige n >= 1 verallgemeinern.
(\subsetequal\) Wir beobachten zunächst, dass alle Regeln die "Balance" erhalten,
in dem Sinne, dass in jedem Ableitungsschritt \red\die Anzahl \black\der a's (bzw. A's) gleich der Anzahl der b's (bzw. B's) gleich der Anzahl der c's (bzw. C's) ist.
Deshalb muss für jedes Wort w \el\ L(G) gelten:
Anzahl der a's = Anzahl der b's = Anzahl der c's.
Als Nächstes inspizieren wir die Regeln im Einzelnen,
und zwar im Hinblick darauf, \red\ in welcher Reihenfolge \black\diese Terminalsymbole erzeugt werden können.
Wir wollen zeigen, dass für jedes x in L(G) gilt:
die a's in x kommen vor den b's, und diese vor den c's.
Die a's können nur durch die ersten beiden Regeln erzeugt werden und stehen dann, wie gewünscht, ganz links.
Betrachten wir nun die b's und c's: Ein nur aus den Terminalzeichen b und c bestehendes Teilwort von x kann nur durch die Regeln aB -> ab, bB -> bb, bC -> bc, cC -> cc erzeugt werden.
Diese Regeln sind so aufgebaut, dass die b's sich an die a's anschließen müssen,
und dann die c's an die b's.
Beide Beobachtungen zusammengenommen ergeben, dass jedes Wort in L(G) nur die Form a^n b^n c^n , n >= 1, haben kann.
\blue\(1) \red\Vollziehen Sie diesen Beweis nach.
\blue\(2) \red\Erläutern Sie den Beweis einer\/einem Mitstudierende\/n.
\darkred\Erstmal durchatmen, ok..
\darkred\Ich verstehe das jetzt so:
\blue\(1):
Leitet man irgendein beispielhaftes Wort ab (wie aabbcc),
dann stellt man schnell fest,
dass in jedem Ableitungsschritt (ausgehend von der gegebenen Grammatik G) die Anzahl der a's \/ A's, b's \/ B's und c's \/ C's immer identisch zueinander ist.
Da der letzte Ableitungsschritt immer das letztendlich aufzubauende Wort ergibt,
kann man schlussfolgern,
dass diese Wörter ebenso in {a^n b^n c^n \| n >= 1} liegen.
\darkred\Ok, habe bis hierhin schonmal den Beweisteil mit der \red\Anzahl \darkred\beschrieben (meine Nachvollziehung also).
\darkred\Weiter komme ich sinnhaftig irgendwie nicht..
\darkred\Weiß auch nicht, was das hier für ein Beweis ist und wie der aufgebaut ist?
\darkred\Mein Kopf raucht..
\darkred\Ist das ein induktiver Beweis? Erkenne keine Strukturen..
Kann das jemand irgendwie umgangssprachlich nachvollziehen oder denke ich da in zu komplizierten Mustern?
Hier auch nochmal der Übungszettel (sorry für meine vielen Notizen \*grins\*):
Bildanhang s. hier
\
Mit freundlichen Grüßen
MrObvious
|
 Profil
|
tactac
Senior 
Dabei seit: 15.10.2014
Mitteilungen: 2789
 |  Beitrag No.1, eingetragen 2023-03-22
|
Ein Induktionsbeweis ist es eher nicht. (Und überhaupt eher eine Beweisskizze.) Es geht eher um Invarianten.
Hier haben wir etwa:
* Die Anzahlen der a b/B und c/C sind immer identisch zueinander,
* ein b kann nur rechts von einem a oder einem b "entstehen" (aus einem B),
* ein c nur rechts von einem b oder c (aus einem C).
D.h., wenn ein Wort erreicht wird, das nur aus Terminalsymbolen besteht, sind die a,b,c darin in der richtigen Reihenfolge.
Wichtig ist für das Verständnis vielleicht auch: wenn die Regeln einfach random vorwärts angewendet werden, kann man in eine Situation geraten, von der aus man die Nichtterminalsymbole nicht mehr wegbekommt (mit dieser konkreten Grammatik ist dann unweigerlich irgendwann keine Regel mehr anwendbar und das aktuelle Wort enthält Nichtterminale, aber das muss im Allgemeinen nicht so sein; durch Hinzufügen der Regel BC -> CB beispielsweise hätte man dieselbe Sprache, es gibt aber mehr solcher "Holzwege", auch unendlich lange). So ein Pfad führt nicht zu einem Wort der durch die Grammatik definierten Sprache.
|
Profil
|
MrObvious
Junior
Dabei seit: 22.03.2023
Mitteilungen: 5
|  Beitrag No.2, vom Themenstarter, eingetragen 2023-03-23
|
Ok, vielen Dank für die ausführliche Antwort.
Das mit dem Begriff „Invarianten“ musste ich erstmal noch nachschlagen.
In dem Sinne ist eine Invariante doch nichts Anderes als:
Beschreibt, dass der Wert einer bestimmten Größe (z.B. hier die Anzahl der „Buchstabengruppen“, also b's / B's usw.) mit einem gewählten Verfahren (z.B. Buchstabengruppen zählen) immer wieder zustandekommt; egal wie oft man es wiederholt.
Das Ergebnis ist eindeutig und immer wieder das Selbe.
Aus informatischer Sicht hätte ich auch gesagt, dass eine Invariante doch sowas Ähnliches auch wie Determiniertheit beschreibt (also ich setze für eine mathematische Größe in einem Kontext was ein und bekomme immer wieder das selbe Ergebnis).
Das Gegenteil von Invarianten sind dann doch Fälle wie Zufallszahlen, die immer was Anderes ergeben? (im Normalfall)
Übrigens: das mit der Erklärung des Holzweges am Ende hat mir sehr geholfen, da ich das vorher so noch nicht kannte. Sonst hatten wir immer Grammatiken, die sich immer zuende ableiten ließen zu einem reinen Terminalsymbol-Wort.
\quoteon(2023-03-22 22:24 - tactac in Beitrag No. 1)
Ein Induktionsbeweis ist es eher nicht. (Und überhaupt eher eine Beweisskizze.) Es geht eher um Invarianten.
Hier haben wir etwa:
* Die Anzahlen der a b/B und c/C sind immer identisch zueinander,
* ein b kann nur rechts von einem a oder einem b "entstehen" (aus einem B),
* ein c nur rechts von einem b oder c (aus einem C).
D.h., wenn ein Wort erreicht wird, das nur aus Terminalsymbolen besteht, sind die a,b,c darin in der richtigen Reihenfolge.
Wichtig ist für das Verständnis vielleicht auch: wenn die Regeln einfach random vorwärts angewendet werden, kann man in eine Situation geraten, von der aus man die Nichtterminalsymbole nicht mehr wegbekommt (mit dieser konkreten Grammatik ist dann unweigerlich irgendwann keine Regel mehr anwendbar und das aktuelle Wort enthält Nichtterminale, aber das muss im Allgemeinen nicht so sein; durch Hinzufügen der Regel BC -> CB beispielsweise hätte man dieselbe Sprache, es gibt aber mehr solcher "Holzwege", auch unendlich lange). So ein Pfad führt nicht zu einem Wort der durch die Grammatik definierten Sprache.
\quoteoff
|
Profil
| Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten |
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2789
| Beitrag No.3, eingetragen 2023-03-23
|
\quoteon(2023-03-23 18:16 - MrObvious in Beitrag No. 2)
Aus informatischer Sicht hätte ich auch gesagt, dass eine Invariante doch sowas Ähnliches auch wie Determiniertheit beschreibt (also ich setze für eine mathematische Größe in einem Kontext was ein und bekomme immer wieder das selbe Ergebnis).
Das Gegenteil von Invarianten sind dann doch Fälle wie Zufallszahlen, die immer was Anderes ergeben? (im Normalfall)
\quoteoff
Eine Invariante ist etwas, das einfach immer gilt, auch wenn sich Dinge ändern. Beim Programmieren kann eine "Schleifeninvariante" z.B. eine Aussage über die Variablenbelegungen sein, die sich durch Abarbeiten der Schleife ergeben.
|
Profil
|
| MrObvious wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
