Rationale Ausdrücke - FB18

was bedeutet + , * , .

+ normal: Ist ein oder-Zeichen.
+ hochgestellt: Du darfst das wo das + dransteht so oft wie du willst im Wort haben, mindestens einmal aber
*: Du darfst das wo das * dransteht so oft wie du willst im Wort haben, oder auch keinmal
.: (sofern das der Malpunkt sein soll) heißt einfach Hinterinanderschreiben, so ist ab dann nichts anderes als a.b

Welche Menge beschreibt dieser rationale Ausdruck?
(a + b)*? oder (a*b*)? oder (a+b*) ?????????????

(a + b)*: Sei das + ein normales. Dann heißt das in der Klammer ein a oder ein b. Um die Klammer ist ein *, also darf man beliebig oft ein a oder ein b nehmen oder auch garnicht. Also sind das alle Wörter die Lambda oder irgendein Wort aus a und b sind.

(a*b*): Erst dürfen beliebig viele a, dann beliebig viele b kommen. Also sind das alle Wörter, die lambda, a, b, oder ein Wort aus as und bs wo allle as am Anfang stehen, sind.

(a+b*): Sofern das + hochgestellt ist: So wie eben, nur dass lambda und b als Wörter nicht auftreten können, weil ja mindestens ein a kommen muss

(a+b*): Sofern das + normal: Entweder ein a oder beliebig viele bs. Also die Wörter: a, lambda, b, bb, bbb, bbbb, bbbbb, ….

Gibt es ein verfahren wie man aus einem Automat den rationalen
Ausdruck bestimmen kann?

Z.B.:

K:={(z1,a,z1),(z1,b,z2),(z2,a,z2)} ?

Wie kann man hier den rationalen Ausdruck bestimmen?

Ich danke euch schon im voraus!!!!!!

Ja, ein Verfahren gibt es, das ist im Beweis auf Seite 70 mit drin. Meist ist es jedoch einfacher durch gucken und Nachdenken den Ausdruck zu bilden.

Ich nehme mal einfach an z1 ist Startzustand, z2 ist Endzustand.
Wie man sieht kann man zuerst mal beliebig viele as machen, man ist immernoch in z1. Also Fangen wie an mit a*. Um irgendwann zum Endzustand z2 zu kommen brauchen wir ein b. Wenn wir in z2 sind, gehen noch beliebig viele as wieder, oder auch gar keins. Also nochmal a*. Damit ist der Ausdruck:
a*ba*

Homme geholfen zu haben [img]http://www.fb18.de/gfx/28.gif[/img]