Ist L(X) eine reguläre Sprache wenn X der Ausdruck (aa*)*ist?
Was ist mit (ahochplus)*
Hallo,
reguläre Ausdrücke erzeugen immer reguläre Sprachen. Je nachdem, wie ihr eure regulären Sprachen definiert hat, kann man das beweisen, indem man einen Algorithmus angibt, der einen regulären Ausdruck in einen bspw. nichtdeterministischen endlichen Automaten überführt, der die gleiche Sprache erzeugt.
Nico
Danke Nico, das ist mir bekannt.
Ich wollte wissen, ob der Ausdruck (aa*)* regulär ist und welche Sprache er erzeugt.
Meine Zusatzfrage war wie ich einen Ausdruck der Form a(a^+b^+)* in etwas handlicheres umforme.
Anm.: a^+ ist gleichbedeutend aa*
Alles, was du mit den syntaktischen Elementen eines regulären Ausdrucks aufschreiben kannst, ist auch ein regulärer Ausdruck. Also auch (aa*)* oder dergleichen. In dem Fall vereinfacht sich das sogar noch zu a*, was man auch relativ gut beweisen kann:
(aa^*)^*=(a^+)^* = (\bigcup_{n = 1} ^ \infty a^n)^*
=\bigcup_{m = 0}^\infty (\bigcup_{n = 1} ^ \infty a^n)^m
=\bigcup_{m = 0}^\infty a^m
=a^*
Eine einfache Regel zum Vereinfachen solcher Ausdrücke kenne ich nicht. Ich würde mir jeweils die Sprachen ansehen, die einzelne Teile erzeugen.
Dementsprechend ist (a^+ b^+)* gleichbedeutend mit (a* b*)* und erzeugt alle möglichen Kombinationen aus a und b. a(a^+ b^+)* erzeugt also alle Wörter aus a und b, die mit a anfangen.
Nico
1 Like