Reguläre Ausdrücke zu gegebenem Automaten oder gegebener Sprache

Question

Hallo,

mathef hat mir bereits beim formulieren der Sprache für den folgenden Automaten geholfen:

L = { 10ⁿ ; 0^m ; ε  | n>1 , m≥2 }

Wen ich dazu nun 2 äquivalente reguläre Ausdrücke angeben will,

geht das so mit dem ersten:  r = (0+1)0⁺

Aber wie sähe ein zweiter aus?

Und muss man das Epsilon in regulären Ausdrücken mit angeben?

Answer 1

Du kannst einen regulären Ausdruck analog zum Aufbau des dazugehörigen Automaten konstruieren:

- Das leere Wort \(\epsilon\)

- Unterer Pfad (\(Z_0\longrightarrow Z_2\longrightarrow Z_3\)): \(00^*0\)

- Oberer Pfad (\(Z_0\longrightarrow Z_1\longrightarrow Z_3\)): \(10^*0\)

- \(Z_4\) ist nicht erreichbar und bleibt ohne Beachtung.

Eine Kombination der Ergebnisse liefert: \(\epsilon|00^*0|10^*0\)

Ein äquivalenter regulärer Ausdruck ist: \(\epsilon|(1|0)0^*0\)

Und muss man das Epsilon in regulären Ausdrücken mit angeben?

Ja! Das Epsilon \(\epsilon\) wird in beiden Fällen benötigt, da sich das leere Wort sonst nicht erzeugen lässt. Es kann aber auch der Fall eintreten, dass das \(\epsilon\) nicht benötigt wird.