0 Daumen
528 Aufrufe

Hallo,

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

Bild Mathematik

L = { 10n ; 0m ; ε  | 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?

Avatar von

1 Antwort

+1 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community