Sprache zu regulärem Ausdruck und Grammatik angeben?

Question

Aufgabe:

Zu folgenden Sprachen einen regulären Ausdruck und eine rechts oder linkslineare Grammatik angeben:

b. {a^m b^k a^n | (k = m+n) und (m, n є {1,2})}, Wort: aabbba
c. { a^m (ba)^n | m ist gerade oder n ist gerade}, Wort: aabaaa

Mein Ansatz:

Ich verstehe nicht, wie ich die Abhängigkeiten zwischen der Anzahl der a's und der b's in einen regulären Ausdruck umwandle. Vielen Dank für jede Hilfe.

Answer 1

Das wäre der zu b gehörige Automat.

RegEx: ((a | aabb)bba) | ((abbb | aabbbb)aa)

Grammatik:

________________________________________________________

Der zu c gehörige Automat.

RegEx: (aaba|aaa(aa)*aba|aaa(aa)*baba)(baba)*

Grammatik:

Beste Grüße

Felix

Comments

Mein Tipp ist, mach erst einen Automat, dann wird das mit dem RegEx ein Kinderspiel. Das ist nurnoch ablesen.

---

Vielen Dank für die Hilfe! Aber wäre bei b) laut der RegEx nicht auch aabbbba zulässig, was doch eigentlich falsch sein müsste? Ich komme darauf, da (a | aabb)bba doch so einen Ausdruck zulässt oder?

---

Da hast du recht, streich aus dem regex das allererste b raus. Dann stimmt's.

Gruß