Marco D. - Do 03.12.09 19:16
Titel: Formale Sprache zu Grammatik angeben

---

Hallo Community,

kommenden Montag schreibe ich meine Klausur in Formale Sprachen und Automaten.
Als Übungsaufgabe sollen wir zu einer Grammatik G eine formale Sprache L(G) angeben.
G hat folgende Produktionen, Startsymbol ist X:

X->XX
X->aXb
X->bXa
X->e (leeres Wort)

Eine mögliche Ableitung wäre (von mir aufgestellt):
X => aXb => abXab => abXXab => abbXabXaab => abbabaab

Jedoch fällt es mir schwer, dafür eine Sprache L(G) anzugeben.

Kann mir jemand weiterhelfen?

Grüße aus Karlsruhe
Marco

Gausi - Do 03.12.09 19:29

---

So auf Anhieb würde ich sagen: Das sind alle Wörter, die gleich viele a's und b's haben. Oder gibt es ein ab-Wort mit der Bedingung, das sich aber mit den Regeln nicht bauen lässt?

Ein regulärer Ausdruck will mir dafür jetzt nicht einfallen, was aber daran liegen könnte, dass die Sprache nicht regulär ist (zumindest ist dir Grammatik nicht vom Typ 3 in der Chomsky-Hierarchie). :D

Marco D. - Do 03.12.09 19:37

---

Hallo Gausi,

ja dann wird es wohl so sein, eine Bildungsvorschrift in der Form wie a^k b^k (nur als Beispiel) fällt mir für die obenstehende Grammatik nicht ein.

Dann wäre L(G) = { w e {a,b}* | #a = #b } korrekt, oder?

Gausi - Do 03.12.09 20:21

---

Würde ich sagen, ja. :)

elundril - Do 03.12.09 20:24

---

naja das wort aabbbbaa wäre teil der sprache aber nicht teil der grammatik oder? oder is das egal? (muss ich noch lernen :mrgreen:)

lg elundril

Gausi - Do 03.12.09 20:32

---

;-)

Nein, das wäre nicht egal, aber dieses Wort lässt sich mit den regeln ableiten

elundril - Do 03.12.09 20:34

---

-.- stimmt, danke. Also wirklich noch mehr lernen. :D

lg elundril

Kha - Do 03.12.09 22:49

---

FYI: Der erste Teil der Aufgabe stammt aus dem Dragonbook, 2.2.2 d). Formale Sprache wird in dem Buch (afair) gar nicht behandelt.
Dummerweise gibt es für die Aufgaben keine offizielle Lösung :lol: , Gausis Lösung deckt sich aber wenigstens hiermit: http://www.cs.odu.edu/~wilson/cs488/key/key1.doc