Grundlagen der CFG verstehen

Question

Haben Sie gerade das Kapitel über CFL in Sipsers Buch begonnen und verstehen bereits die Grundlagen nicht.

Dies seien die Grammatik einer Sprache sein:

S -> A0A 
A -> 00A | 11A | 10A | 01A | e 

ich diesen A0A Teil wirklich verwirrt bin. Bedeutet es, dass die linke Seite von 0 immer die gleiche wie die rechte Seite sein sollte. Bedeutet das, dass 00011 oder 000 nicht in dieser Sprache sind?

Answer 1

Beliebig S ist jede Option, die Sie für alle A haben, gefolgt von einem einzelnen Literal 0 und dann eine andere Option für A. Jeder A ist unabhängig.

Der String 00011 ist in der Sprache, weil Sie Ihre zwei A s (zum Beispiel), so dass die erste 00A holen kann und die zweite ist 11A ist. Wenn Sie die leere Zeichenfolge (e) für beide "verbleibenden" A s rekursiv auswählen, erhalten Sie bei der Verkettung von allem die Zeichenfolge 00011.

Sie können eine ähnliche Aktion durchführen, um die Zeichenfolge 000 zu erhalten.

Answer 2

A wird entweder in eine leere Zahl oder in zwei Binärziffern umgewandelt. Dann bedeutet A, dass A in eine beliebige Folge von geraden Zahlen von Binärziffern umgewandelt wird.

S transformiert zu A, dann 0, dann A. Das bedeutet, dass S in eine gerade Anzahl von Binärziffern umgewandelt wird, dann 0, dann eine gerade Anzahl von Binärziffern. Das heißt, S ist irgendeine Folge von ungeraden Zahlen von Binärziffern mit 0 in der Mitte.

Bedeutet es, dass die linke Seite von 0 immer die gleiche wie die rechte Seite sein sollte.

Nein, warum? Zwei verschiedene A's können in verschiedene Sequenzen umgewandelt werden.