Formale Sprachen Jörg Roth 196 3 Formale Sprachen · aA →B, B →Ab }) ... A →BC XXX AB →CD XX. Formale Sprachen Jörg Roth 219 Beispiel. Sei G = ... Umwandlung in die Normalform:

Formale Sprachen Jörg Roth 196

3 Formale Sprachen■ Wir haben uns bisher nur mit einem Typ formaler Sprachen besonders

intensiv beschäftigt – den regulären Sprachen.■ Wir haben aber auch erkannt, dass reguläre Sprachen nur eine sehr

begrenzte Ausdrucksfähigkeit besitzen. Das Pumping-Lemma setzt hierzu die Grenzen.

■ In diesem Kapitel wollen wir weitere Typen von Sprachen einführen. Die so genannte Chomsky-Hierarchie liefert uns eine Einteilung aller forma-ler Sprachen in vier Typen.

■ Wir führen als endliches Beschreibungsinstrument für unendliche Spra-chen so genannte Grammatiken ein. Man könnte Grammatiken für allge-meine Sprachen als das ansehen, was reguläre Ausdrücken für reguläre Sprachen waren.


■ Analog zu den Sprach-Typen der Chomsky-Hierarchie kann man vier Typen von Grammatiken identifizieren.

■ Reguläre Sprachen werden als ein Typ in der Chomsky-Hierarchie identi-fiziert. Wir zeigen, dass reguläre Sprachen gerade von linearen Gramma-tiken generiert werden. Wir haben somit eine weitere Beschreibungsmög-lichkeit für reguläre Sprachen – insgesamt nämlich:• Endliche Automaten• Reguläre Ausdrücke• Lineare Grammatiken

■ Schließlich befassen wir uns noch mit der Klasse der kontextfreien Spra-chen, der nächstgrößeren Sprachklasse in der Chomsky-Hierarchie.


Bemerkungen zur Schreibweise von Produktionen:

■ Produktionen sind Tupel aus . Durch die Schreib-

weise A → B wird also das Tupel (A, B)∈ darge-stellt.

■ Der Strich "|" ist nur eine abkürzende Schreibweise: Bei der Produktion A → B | C handelt es sich also um die zwei Produktionen A → B und A → C, also genau genommen die Tupel (A, B) und (A, C).

N T∪( )+ N T∪( )×*

N T∪( )+ N T∪( )×*


Weiteres Beispiel:

G = ( {A, B},{a, b}, A,{A → bb | aaA, aA → B, B → Ab })

Ableitung von bbbb

A ⇒ aaA ⇒ aB ⇒ aAb ⇒ Bb ⇒ Abb ⇒ bbbb


Beispiele.Es gilt jeweils T = {a, ..., z} N = {A, ..., Z}

Typ 0: aA → a B → ε(weitere Beispiele unter Typ 1 bis Typ 3)

Typ 1: aA → bBbB aa → cc AA → BcB(weitere Beispiele unter Typ 2 und Typ 3)

Typ 2: A → aAAxyzB B → bBB(weitere Beispiele unter Typ 3)

Typ 3: A → xyzB B → bB C → hallo C → D


Übersicht der Normalform-Produktionen zu den Grammatik-Typen

Typ 0 Typ 1 Typ 2 Typ 3A → ε XA → t X X X XA → tB X XA → BC X X XAB → CD X X


Beispiel. Sei G = ({A, B}, {a, b, x, y, z}, A, P) und P seiA → xyzA A → B B → ab

Umwandlung in die Normalform: (nur Regeln A → t, A → tB)

■ A → xyzA A → xA1 A1 → yA2 A2 → zAB → ab B → aB1 B1 → b

■ A → B A → aB1

Damit G = ({A, B, A1, A2, B1}, {a, b, x, y, z}, A, P) und P istA → xA1 A1 → yA2 A2 → zAB → aB1 B1 → b A → aB1

Die Regel B → aB1 ist überflüssig geworden, da B auf keiner rechten Seite mehr vorkommt.


Beispiel. Sei G = ({A}, {x, a, b, c}, A, P) und P seiA → AxA A → abc A → c

Umwandlung in die Normalform: (nur Regeln A → t, A → BC)

■ Einführen von Ti:T1 → x T2 → a T3 → b T4 → c

■ Ersetzen von terminalen Symbolen in Regeln:A → AxA A → AT1AA → abc A → T2T3T4A → c A → T4


■ Umwandeln von Regeln mit 3 oder mehr nichtterminalen Symbolen auf der rechten Seite:A → AT1A A → AA11 A11 → T1AA → T2T3T4 A → T2A21 A21 → T3T4

■ Umwandeln von Regeln mit genau einem nichtterminalen Symbol auf der rechten Seite:A → T4 A → c

Damit G = ({A, T1, T2, T3, T4, A11, A21}, {x, a, b, c}, A, P) und P istT1 → x T2 → a T3 → b T4 → cA → AA11 A11 → T1A A → T2A21 A21 → T3T4A → c


Beispiel im Detail:

G’ (rechtsl.) Regel

GL (linksl.)

S → abR 1 R → abS → cdT 1 T → cdR → abR 3 R → RabR → cdT 3 T → RcdT → bT 3 T → TbT → b 4 S → Tb

Zu Erinnerung: Regeln:rechtslin. linkslin.

1 S → tA A → t2 S → t S → t3 A → tB B → At4 A → t S → At


Beispiele für Produktionen zu einem Automaten:

Ax

B

A xB

zD E

D zD zE

C

y

C yC

E

w

E wE E w


Beispiele von Zustandsübergängen zu Produktionen:

Bemerkung. Der resultierende Automat ist nichtdeterministisch.

■ Für ein A muss es nicht für jedes x eine Regel A → xB geben■ Für ein A und ein x kann es zwei Regeln A → xB und A → xC geben

Ax

B

A xB

zD

D z

C

y

C yC

Nε

D zNε Nε ε( )


Hinweis zum Beispiel (Grammatik zum Automat zur Erkennung vorzeichen-loser Zahlenkonstanten):

■ Achtung: der Automat ist nichtdeterministisch – die Zuordnung im Beweis verlangt allerdings einen deterministischen Automaten.

■ Die Zuordnung funktioniert dennoch, da• der Automat nur einen Anfangszustand hat• und δ(A, x) maximal ein Element hat

d.h. der einzige Nichtdeterminismus dadurch resultiert, dass einige ausge-hende Kanten fehlen, d.h. für einige A, x gilt δ(A, x) = ∅.

■ Wir können die Zuordnung für nichtdeterministische Automaten erwei-tern:• Für alle zi∈Z0 erzeuge Produktion S → z0• Für jedes Z∈δ(A, x) erzeuge Regel A → xZ bzw. A → x analog zu oben.


Wir führen hier die Zuordnung zur deterministischen Variante des Automa-ten zur Erkennung vorzeichenloser Zahlenkonstanten durch (Abschnitt 2.1):

S0 S1 S2

S4

S5

S3

S6

S7

0, …, 90, …, 9

. 0, …, 9

0, …, 9

+, -,E, .

0, …, 9,+, -, E, .

+, - E

+, -,E, .

+, -, .

E

0, …, 9

0, …, 9+, -

0, …, 9

E, .

+, -,E, .

+, -,E, .

S0 0S1

S0 9S1

…S0 0

S0 9…

S1 0S1

S1 9S1

…S1 0

S1 9

… S1 .S2

S1 ES4

S2 0S3

S2 9S3

…S3 0

S3 9

S3 0S3

S3 9S3

…S3 0

S3 9

S3 ES4

S5 0S6

S5 9S6

…S5 0

S5 9…

S4 0S6

S4 9S6

…S4 0

S4 9…

S6 0S6

S6 9S6

…S6 0

S6 9…

S4 +S5S4 -S5

S0 +S7S0 -S7S0 ES7S0 .S7

S7 +S7S7 -S7S7 ES7S7 .S7

S7 0S7

S7 9S7

…


Hinweise zu S7:

■ S7 ist nur an Produktionen der Form Si → xS7 beteiligt (im Bild rosa), nie S7 → x und nie S7 → xSi für i≠7

■ Die Konsequenz: Ableitungen mit S7 führen nie zu einem Wort aus T*. Wir können alle Produktionen mit S7 weglassen.

Documents

Formale Sprachen Jörg Roth 196 3 Formale Sprachen · aA →B, B →Ab }) ... A →BC XXX AB →CD XX. Formale Sprachen Jörg Roth 219 Beispiel. Sei G = ... Umwandlung in die Normalform: