Satz Jede reguläre Sprache wird von DKA erkannt
Einfache Sprache
Def. Satz Jede reguläre Sprache wird von DKA erkannt
Sei $L$ eine Reguläre Sprache. Dann existiert ein DKA $\mathcal P$ mit der Eigenschaft
$$L=L(\mathcal P)\;.$$
Beweisidee: Ein DKA ist im Grunde ein DEA mit einem Kellerspeicher. Für jede Reguläre Sprache existiert ein DEA. Daher müssen wir nur ein bisschen dir Definition ändern und erhalten einen DKA.
Beweis: Sei $L$ eine Reguläre Sprache. Dann existiert nach der Definition mit DEA ein DEA $\mathcal A=(Q,A,\delta_\mathcal A,q_0,F)$ der $L$ erkennt. Sei $\mathcal P$ ein DKA und wie folgt definiert
$$\mathcal P=(Q,A,\{Z_0\},\delta_\mathcal P,q_0,Z_0,F)$$mit $\delta_\mathcal P(q,a,Z_0) = \{(p,Z_0)\}$ für alle $q,p\in Q$ mit $\delta_\mathcal A(q,a) = p$.
Bleibt zu zeigen, dass $\mathcal A$ und $\mathcal P$ dieselbe Sprache erkennen. Also
$$w\in L(\mathcal A)\iff w\in L(\mathcal P)\;.$$Unter Anwendung der Definitionen der Erkannte Sprache eines DEA und Durch Endzustand erkannte Sprache eines NDKA ergibt sich daraus
$$\hat\delta_\mathcal A (q_0,w) = p\iff(q_0,w,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(p,\varepsilon,Z_0)$$Wir beweisen diese Aussage induktiv über $|w|$.
IA: Sei $|w| = 0$. Also muss $w=\varepsilon$. Nach der Definition der erweiterten Transitionfunktion gilt $\hat\delta_\mathcal P(q_0,\varepsilon) = q_0$ und ebenfalls gilt nach der Definition der erweiterten Folgekonfiguration $\delta_\mathcal P(q,\varepsilon,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(q_0,\varepsilon,Z_0)$.
IS: Sei $|w|\geq 1$. Sei $w = va$ mit $a\in A$ und $v\in A^*$.
$$\begin{align}&\hat\delta_\mathcal A(q_0,w)=p&\\\iff&\hat\delta_\mathcal A(q_0,va)=p& &\Huge|\normalsize\text{Def. $w$}\\\iff&\delta_\mathcal A(\hat\delta_\mathcal A(q_0,v), a)=p& &\Huge|\normalsize\text{Def. $\hat\delta$}\\\iff&\hat\delta_\mathcal A(q_0,v) = r\land\delta_\mathcal A(r, a)=p& &\Huge|\normalsize\text{Def. $r$}\\\iff&(q_0,v,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(r,\varepsilon,Z_0)\land\delta_\mathcal A(r, a)=p& &\Huge|\normalsize\textit{IH}\\\iff&(q_0,va,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(r,a,Z_0)\land\delta_\mathcal A(r, a)=p& &\Huge|\normalsize\text{Satz ungelesene Eingabe}\\\iff&(q_0,va,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(r,a,Z_0)\land \delta_\mathcal P(r,a,Z_0) = \{(p,Z_0)\}& &\Huge|\normalsize\text{Def. $\delta_\mathcal P$}\\\iff&(q_0,va,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(r,a,Z_0)\land (r,a,Z_0)\underset{\mathcal P}\vdash(p,\varepsilon, Z_0)& &\Huge|\normalsize\text{Def. $\vdash$}\\\iff&(q_0,va,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(r,a,Z_0)\underset{\mathcal P}\vdash(p,\varepsilon, Z_0)& &\Huge|\normalsize\text{Def. $\vdash$}\\\iff&(q_0,va,Z_0)\overset{*}{\underset{\mathcal P}\vdash}(p,\varepsilon, Z_0)& &\Huge|\normalsize\text{Def. $\overset{*}\vdash$}\\\end{align}$$Hier ist der Satz ungelesene Eingabe.