?FA -> regulärer Ausdruck
| Was macht der r.A.? | zurück |
Der r.A. beschreibt alle Wörter, die in der Sprache liegen.
Aus Sicht des Automaten also alle Eingaben, die vom Startzustand zum Endzustand führen.
| Was suchen wir also? | zurück |
Den r.A., der beschreibt, wie wir vom Startzustand zum Endzustand kommen unter Zuhilfenahme aller Zustände:
| Was, wenn es mehrere Start-/ Endzustände gibt? | zurück |
Dann müssen wir alle r.A. bestimmen, die von jedem Start- zu jedem Endzustand führen und alle mit ODER verknüpfen:
| Was bedeuten die Indizes? | zurück |
Der unten links gibt an, wo wir losgehen,
der unten rechts, wo wir hingehen und
der oben, welche Zustände wir dabei passieren dürfen - nämlich alle, die kleiner gleich dem oberen Index sind.
| Wie werden die Zustände indiziert? | zurück |
Das ist egal.
Wichtig ist nur, dass man bei 1 zu indizieren beginnt.
Bei geschickter Indizierung kommt man evtl. schneller ans Ziel. An kommt man aber immer...
| Wie geht das Verfahren jetzt? | zurück |
Den gesuchten r.A. findet man, indem man einfach rekursiv nach der Formel die Alphas so lange ersetzt, bis der obere Index 0 ist.
Denn das bedeutet, wir wollen von i nach j und dürfen dabei keinen Zustand ausser i und j verwenden. Folglich ist das dann der direkte Verbindungspfeil:
| Was ist, wenn es den "direkten Verbindungspfeil" nicht gibt? | zurück |
Dann liefert dieser r.A. kein Ergebnis.
Insbesondere bedeutet das, wenn wir uns die Rekursionsformel oben anschauen, dass sobald der linke oder rechte Ausdruck des Dreierterms nicht geht, der gesamte Dreierterm nicht geht!
Denn bildlich gesprochen bedeutet die rechte Seite:
"[gehe möglichst direkt]" | "[gehe einen Umweg] [dort weitere Umwege] [komm' wieder zurück]"
Wenn nun aber das Hingehen zum Umweg oder das Zurückkommen nicht gehen (weil es eben keinen Weg/ Pfeil gibt), so kann der ganze Umweg nicht genommen werden!
Nur der mittlere (gesternte) Term darf "nicht gehen".
| Wann sind wir fertig? | zurück |
Wenn unser regulärer Ausdruck vom Start keine Alphas mehr enthält, also komplett aufgelöst ist.
Da Teilterme des öfteren mehrfach zu berechnen sind, ist es zumeist hilfreich, diese als Nebenrechnung auszurechnen. Das vermeidet dann auch eine gewisse Unübersichtlichkeit ;-)
| Ist das Ergebnis eindeutig? | zurück |
Nein.
Es kommt zwar immer ein gültiger regulärer Ausdruck heraus, aber nicht unbedingt der minimale.
| b | Sehr ausführlich Blatt 4 Aufgabe 5 | ps (zip) |