Vom Automaten zum regulären Ausdruck

Verarbeitung eines erkennenden Automaten für Binärzahlen

Der folgende erkennende Automat akzeptiert die Sprache L_Bin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}

:

Wenn man in JFlap die Menupunkte [Convert][Convert FA to RE] auswählt, dann lässt sich schrittweise zum gegebenen erkennenden Automaten ein regulärer Ausdruck erzeugen. Man muss zunächst einen zusätzlichen (End-) Zustand erzeugen und anschließend mit [Do it] die Verarbeitung Schritt für Schritt aktivieren.

Aufgabe 1

Probiere das selbst einmal aus. Welcher reguläre Ausdruck kommt als Ergebnis heraus? Beschreibt er tatsächlich die Sprache L_Bin?

Aufgabe 2

Welcher Zusammenhang besteht zwischen regulären Ausdrücken und erkennenden Automaten?