Satz Regulärer Ausdruck zu NEA
Einfache Sprache
Wir geben einen Konstruktion an die aus einem Regulärer Ausdruck einen NEA macht, ohne die Erkannte Sprache zu ändern.
Def. Satz Regulärer Ausdruck zu NEA
Sei $R$ ein Regulärer Ausdruck über das Alphabet $\Sigma$. Dann ist ein NEA $N$, der dieselbe Erkannte Sprache wie $R$ hat, wie folgt induktiv definiert: Grundelemente:
- Für $R=\emptyset$ definieren wir $\mathcal N:= (\{q\},\Sigma,\delta(q,x)=\emptyset,\{q\},\emptyset)$.
- Für $R=\varepsilon$ definieren wir $\mathcal N:= (\{q\},\Sigma,\delta(q,x)=\emptyset,\{q\},\{q\})$
- $\forall a\in \Sigma: R = a$ definieren wir $\mathcal N:= (\{q_0,q_1\},\Sigma,\delta(q,x),\{q_0\},\{q_1\})$ mit $\delta(q,x) =\begin{cases}\{q_1\}&\text{falls } q=q_0\land x = a\\\emptyset&\text{sonst}\end{cases}$
Konstruktionsvorschriften: Sei $R_0,R_1\in Reg_A$ so, dass wir zwei NEAs $\mathcal N_1$ und $\mathcal N_2$ haben, die jeweils dieselbe Erkannte Sprache haben wie die Regulären Ausdrücke. Dann geben wir für jede der drei möglichen Konstruktionsvorschriften der Regulären Ausdrücke eine Konstruktion an die die die selbe Sprache erkennt:
- Für $R = (R_1|R_2)\in Reg_\mathcal A$ ergibt sich $\mathcal N$ mit $L(R) = L(\mathcal N)$ aus dem Satz Vereinigung zweier NEAs.
- Für $R = (R_1\circ R_2)\in Reg_\mathcal A$ ergibt sich $\mathcal N$ mit $L(R) = L(\mathcal N)$ aus dem Satz Konkatenation zweier NEAs.
- Für $R = R_1^*\in Reg_\mathcal A$ ergibt sich $\mathcal N$ mit $L(R) = L(\mathcal N)$ aus dem Satz Kleene Hülle eines NEAs.
Beweisidee: Da wir Reguläre Ausdrücke induktiv definiert haben, benutzen müssen wir wir “nur” die Grundelementen in NEAs umwandeln und dann die Konstruktionsvorschriften anpassen. Dann können wir mit Strukturelle Induktion die Korrektheit beweisen. Die Angepassten Konstruktionsvorschriften sind hier definiert und bewiesen: