Satz DEA zu NEA

Einfache Sprache

Def. Satz DEA zu NEA

Für jeden DEA $\mathcal A$ existiert ein NEA $\mathcal A'$ der die dieselbe Sprache erkennt, also $L(\mathcal A) = L(\mathcal A')$.

Beiweisidee: Wir geben eine Methode an wie man einen gegeben DEA in einen äquivalent NEA umwandelt.

Beweis: Gegeben den DEA $\mathcal A = (Q,A,\delta,q_I,F)$. Dann ist der äquivalente NEA wie folgt definiert $\mathcal A' = (Q,A,\delta',\{q_I\},F)$ mit