0 Daumen
1,2k Aufrufe

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.

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

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

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

Grammatik:

b_grammar.jpg


________________________________________________________


c.jpgDer zu c gehörige Automat.

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

Grammatik:

c_grammar.jpg


Beste Grüße

Felix

Avatar von

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ß

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community