Suche Home Einstellungen Anmelden Hilfe  

4.3.2 Beispiele

L = {wwR | w {a,b}* und wR ist das Spiegelbild von w}

Zu dieser Sprache gehören z.B. die Wörter: aabbaa, babaabab, aa und aabbaabbaa.

R = {a1 b1}*{a2 b2}*

R ∩ D2 sorgt für gleiche Anzahl von öffnenden und schließenden Klammern im Paar und für die korrekte Schachtelung

a a1 b1 a2 b2
h(a) a b a b

L = {wa|w| | w {a,b}*}

Diese Sprache umfasst diejenigen Wörter, die im ersten Teil aus einer beliebigen Folge von a's und b's bestehen; im zweiten Wortteil folgen soviele a's wie das erste Teilwort Zeichen hatte, also z.B. abaa, bbbaaa, ababaaaa und aaaa.

R = {a1a2c1 b1b2c1}* c2*

R muss mit D3 geschnitten werden, damit die 3 Klammerpaare ordentlich aufgebaut werden. Es entsteht {a1a2c1 b1b2c1}n c2n

Der Homomorphismus muss nun noch einiges im Ausdruck vereinfachen:

a a1 a2 b1 b2 c1 c2
h(a) a ε b ε ε a

Dieses Beispiel verdeutlicht die Tilgung von Zeichen mittels Homomorphismus. Im Regulären Ausdruck müssen immer Klammerpaare auftreten - also öffnende und zugehörige schließende Klammer. Aber nicht immer werden alle Elemente auch in der Zielsprache gebraucht, wie in diesem Beispiel.

Beispiel 1   2   3   4   5   6 Kontextfreie Grammatiken und Kellerautomaten

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: