Satz Jede reguläre Sprache ist auch kontextfrei
Einfache Sprache
Def. Satz Jede reguläre Sprache ist auch kontextfrei
Für jede Reguläre Sprache $L$ existiert eine Kontextfreie Sprache $L'$ die dieselbe Sprache erkennt.
Beweisidee: Wir zeigen eine Konstruktion die einen DEA in eine Kontextfreie Grammatik umwandelt.
Beweis: Gegeben eine Reguläre Sprache $L$. Nach der Definition von $L$ existiert ein DEA $\mathcal A = (Q,A,\delta,q_I,F)$ der $L$ erkennt. Die Kontextfreie Grammatik $\mathcal G = (T, V, S, P)$ mit
- $T = A$,
- $V = Q$,
- $S = Q_I$ und
- $P = \{Q_i\to aQ_j \mid i,j\in[0,|Q|-1]\land a\in A \land(q_i,a,q_j)\in\delta\}\cup\{Q_k\to\varepsilon\mid q_k\in F\}$
Jetzt müssen wir noch zeigen, dass $L(\mathcal A) = L(\mathcal G)$. Dazu zeigen wir, das die Transitionsfunktion bzw. der Syntaxbaum äquivalent sind. Sei $u\in A^*$ und $q\in Q$. Dann ist $\hat\delta(q,u)\in F$ gdw. es einen Pfad $\alpha \in Q^* := q_0,\ldots,q_n$ mit $q_n\in F$ und $\delta(q_i,u[i])=q_{i+1}$ für alle $i\in[0,n-1]$. Das heißt wiederum, dass es einen Syntaxbaum mit Wurzel $q$ gibt.