Korrektheit einer Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:39 Sa 22.11.2008 | | Autor: | chriz123 |
| Aufgabe | Könnte mir jemand erklären wie ich die Korrektheit einer Grammatik zeige??
|
Vieleicht an einem Beispiel, allgemein würde mir aber auch erstmal weiterhelfen.
Vielen Dank!
Chriz123
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:50 So 23.11.2008 | | Autor: | bazzzty |
> Könnte mir jemand erklären wie ich die Korrektheit einer
> Grammatik zeige??
>
> Vieleicht an einem Beispiel, allgemein würde mir aber auch
> erstmal weiterhelfen.
Ganz allgemein: Indem ich zeige, daß die Grammatik nur Wörter erzeugt, die in der angegebenen Sprache liegen und das zweitens jedes Wort der Sprache durch die Grammatik erzeugt werden kann.
Den ersten Teil kann man üblicherweise über Invarianten während der Ableitung zeigen, den zweiten Teil meist konstruktiver. Wenn Du ein Beispiel hast, ist es etwas einfacher.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:08 So 23.11.2008 | | Autor: | chriz123 |
> > Könnte mir jemand erklären wie ich die Korrektheit einer
> > Grammatik zeige??
>
> Ganz allgemein: Indem ich zeige, daß die Grammatik nur
> Wörter erzeugt, die in der angegebenen Sprache liegen und
> das zweitens jedes Wort der Sprache durch die Grammatik
> erzeugt werden kann.
> Den ersten Teil kann man üblicherweise über Invarianten
> während der Ableitung zeigen, den zweiten Teil meist
> konstruktiver. Wenn Du ein Beispiel hast, ist es etwas
> einfacher.
Hm, nehmen wir mal zum Beispiel die Grammatik, die Wörter mit doppelt so vielen a's wie b's erzeugt:
$G =({A, B, S}, {a, b}, P, S)$
P: S [mm] \to [/mm] AAB|ABA|BAA,
A [mm] \to [/mm] a|BAAA|ABAA|AABA|AAAB,
B [mm] \to [/mm] b|BBAA|BABA|BAAB|ABAB|AABB
Zu zeigen ist also, das G nur Wörter mit doppelt so vielen a's wie b's erzeugt und das G alle Wörter mit doppelt so vielen a's wie b's erzeugt.
Weiter könnte ich das aber nur mit eigenen Woten erklären:
Von der Startvariable können nur Wörter der Form AAB, ABA oder BAA erzeugt werden.
Da aus der Variable A nur a als Terminalsymbol abgeleitet werden kann und aus B nur b als Terminalsymbol sind die genannten alles wörter mit doppelt so vielen a's wie b's.
Außerdem kann die Variable A durch hinzufügen von wiederum einem B und zwei A's (die Variable selbst bleibt auch erhalten), wieder Wörter mit doppelt so vielen a's wie b's erzeugen.
B ...
Dazu das G alle Wörter der Sprache akzeptiert kann ich nur sagen, das die Regeln alle Positionen von a's bzw. b's einschließen und unendlich lange Wörter erzeugt werden können.
Naja vom Sinn müsste das ja hinhauen...
Aber könnte mir jemand zeigen wie ich das formaler zeigen kann.
Was bedeutet z.B. Invarianten??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:28 So 23.11.2008 | | Autor: | bazzzty |
> Hm, nehmen wir mal zum Beispiel die Grammatik, die Wörter
> mit doppelt so vielen a's wie b's erzeugt:
>
> [mm]G =({A, B, S}, {a, b}, P, S)[/mm]
> P: S [mm]\to[/mm] AAB|ABA|BAA,
> A [mm]\to[/mm] a|BAAA|ABAA|AABA|AAAB,
> B [mm]\to[/mm] b|BBAA|BABA|BAAB|ABAB|AABB
>
> Zu zeigen ist also, das G nur Wörter mit doppelt so vielen
> a's wie b's erzeugt und das G alle Wörter mit doppelt so
> vielen a's wie b's erzeugt.
>
> Weiter könnte ich das aber nur mit eigenen Woten erklären:
> [..]
Deine Erklärung ist schon ganz gut! An dem Beispiel kann man aber auch toll sehen, wie man mit Invarianten argumentiert.
Eine Invariante ist eine Eigenschaft, die durch Ableitungen nicht zerstört wird. Im Beispiel:
Wir zeigen folgende Invariante obiger Grammatik:
"Die Anzahl der "A" plus die Anzahl der "a" ist zu jedem Zeitpunkt
doppelt so groß wie die Anzahl der "B" plus die Anzahl der "b".
Beweis: Bei jeder Ableitung kommen entweder zwei "A" und ein "B" hinzu oder ein "A" wird in ein "a" geändert oder ein "B" in ein "b".
Da die Invariante am Anfang gilt (für "S"), gilt sie dann auch für alle erzeugten Worte. Die enthalten keine Nichtterminale, bestehen also aus doppelt so vielen "a" wie "b".
Das ist schon sehr ausführlich. Meist reicht die Angabe einer Invarianten schon als Beweis.
Daß alle Wörter erzeugt werden, sollte man auch sehr viel formaler zeigen. Hier gibt es sehr viel mehr Techniken, aber in diesem Beispiel bietet sich folgender Beweis an, in etwa ein Beweis des kleinsten Gegenbeispiels:
Wir versuchen, zu zeigen, daß jede Folge von Nichtterminalen A und B
erzeugt werden kann, die doppelt so viele As wie Bs enthält (dann kann man auch jedes Wort erzeugen, weil die Nichtterminale ja einfach umgewandelt werden).
Jetzt nehmen wir an, es gäbe eine solche Folge, die sich nicht erzeugen läßt. Dann gibt es auch eine solche Folge mit minimaler Länge. Und die gucken wir uns an. Wir nehmen also an, es gäbe eine kürzeste Folge von doppelt so vielen As und Bs, die sich nicht ableiten läßt (mal als Beispiel: ABAABAAABBAA, der Beweis ist natürlich allgemein). Jedes solche Wort mit mindestens vier Nichtterminalen enthält aber eine der rechten Seiten (warum?), kann also erzeugt werden aus einem kürzeren Wort (ABAABA/AABB/AA kann z.B. erzeugt werden aus ABAABA/B/AA).
Wenn also letzteres erzeugt werden kann (wir hatten uns das kürzeste nichterzeugbare Wort vorgenommen), dann kann auch unser Wort erzeugt werden. Es gibt also kein nichterzeugbares Wort mit doppelt so vielen As wie Bs.
Es fehlt noch die Behandlung von Wörtern mit Länge <=3 und die Begründung, daß man immer eine rechte Seite in längeren Worten findet, aber ist das Prinzip klar?
|
|
|
|
