1. Endlicher Automat für \( \boldsymbol{L}_{\mathbf{1}} \)
Die Sprache \( L_1 \) ist durch den regulären Ausdruck \( {\mathtt{cc}, \mathtt{b}, \mathtt{d}}^+ {\mathtt{ee}} {\mathtt{a}, \mathtt{f}}^* \) definiert.
Ein deterministischer endlicher Automat \(DEA\) dazu sieht folgendermaßen aus:
Zustände:
\( q_0 \): Startzustand \(vor der Verarbeitung von ( {\mathtt{cc}, \mathtt{b}, \mathtt{d}}^+ )\).
\( q_1 \): Zustand nach mindestens einem Element aus \( {\mathtt{cc}, \mathtt{b}, \mathtt{d}} \).
\( q_2 \): Zustand nach dem ersten \( \mathtt{c} \) \(erwartet zweites ( \mathtt{c} )\).
\( q_3 \): Zustand nach \( {\mathtt{cc}, \mathtt{b}, \mathtt{d}}^+ \) \(erwartet ( \mathtt{ee} )\).
\( q_4 \): Zustand nach dem ersten \( \mathtt{e} \) \(erwartet zweites ( \mathtt{e} )\).
\( q_5 \): Akzeptierender Endzustand \(nach ( {\mathtt{a}, \mathtt{f}}^* )\).
Übergangstabelle:
| Zustand | Eingabe | Folgezustand | |---------|---------|--------------| | \( q_0 \) | \( \mathtt{b} \) | \( q_1 \) | | \( q_0 \) | \( \mathtt{d} \) | \( q_1 \) | | \( q_0 \) | \( \mathtt{c} \) | \( q_2 \) | | \( q_1 \) | \( \mathtt{b} \) | \( q_1 \) | | \( q_1 \) | \( \mathtt{d} \) | \( q_1 \) | | \( q_1 \) | \( \mathtt{c} \) | \( q_2 \) | | \( q_1 \) | \( \mathtt{e} \) | \( q_4 \) | | \( q_2 \) | \( \mathtt{c} \) | \( q_1 \) | | \( q_4 \) | \( \mathtt{e} \) | \( q_3 \) | | \( q_3 \) | \( \mathtt{a} \) | \( q_5 \) | | \( q_3 \) | \( \mathtt{f} \) | \( q_5 \) | | \( q_5 \) | \( \mathtt{a} \) | \( q_5 \) | | \( q_5 \) | \( \mathtt{f} \) | \( q_5 \) |
2. Grammatik für \( \boldsymbol{L}_{\mathbf{1}} \)
Produktionsregeln \(Typ-3, rechtslinear\):
Startsymbol: \( S \)
Terminale: \( { \mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d}, \mathtt{e}, \mathtt{f} } \)
Nichtterminale: \( { S, A, B, C, D } \)
\( S &\to A , B , D & &\text{(Startregel)} \\ A &\to \mathtt{b} , A \mid \mathtt{d} , A \mid \mathtt{c} , C \mid \mathtt{b} \mid \mathtt{d} \mid \mathtt{c} , C & &\text{(Mindestens ein Element aus } {\mathtt{cc}, \mathtt{b}, \mathtt{d}}^+ \text{)} \\ C &\to \mathtt{c} , A \mid \mathtt{c} & &\text{(Erzeugt } \mathtt{cc} \text{)} \\ B &\to \mathtt{e} , E & &\text{(Erzeugt } \mathtt{ee} \text{)} \\ E &\to \mathtt{e} & &\text{(Abschluss von } \mathtt{ee} \text{)} \\ D &\to \mathtt{a} , D \mid \mathtt{f} , D \mid \varepsilon & &\text{(Beliebig viele } \mathtt{a}/\mathtt{f} \text{ oder leer)} \)
Normalisierung der Grammatik:
Elimination von ε-Produktionen \(außer für ( D )\):
\( D \to \varepsilon \) bleibt, da \( {\mathtt{a}, \mathtt{f}}^* \) auch leer sein darf.
Vereinfachung der Regeln:
Die Regel \( A \to \mathtt{c} , C \) und \( C \to \mathtt{c} , A \mid \mathtt{c} \) kann zusammengefasst werden zu: \( A \to \mathtt{c} , \mathtt{c} , A \mid \mathtt{c} , \mathtt{c} \)
Ergebnis \(vereinfacht\): \( S &\to A , B , D \\ A &\to \mathtt{b} , A \mid \mathtt{d} , A \mid \mathtt{c} , \mathtt{c} , A \mid \mathtt{b} \mid \mathtt{d} \mid \mathtt{c} , \mathtt{c} \\ B &\to \mathtt{e} , \mathtt{e} \\ D &\to \mathtt{a} , D \mid \mathtt{f} , D \mid \varepsilon \)
Beispielableitung:
Für das Wort \( \mathtt{b , cc , ee , a} \): \( S \to A , B , D \to \mathtt{b} , A , B , D \to \mathtt{b} , \mathtt{c} , \mathtt{c} , A , B , D \to \mathtt{b} , \mathtt{c} , \mathtt{c} , B , D \to \mathtt{b} , \mathtt{c} , \mathtt{c} , \mathtt{e} , \mathtt{e} , D \to \mathtt{b} , \mathtt{c} , \mathtt{c} , \mathtt{e} , \mathtt{e} , \mathtt{a} , D \to \mathtt{b} , \mathtt{c} , \mathtt{c} , \mathtt{e} , \mathtt{e} , \mathtt{a} \)
Zusammenfassung:
Der Automat hat 6 Zustände und folgt der Struktur des regulären Ausdrucks.
Die Grammatik ist rechtslinear \(Typ-3\) und erfüllt nach der Normalisierung die Kriterien für reguläre Grammatiken.
