Elimination von epsilon-Kanten

Einfache Sprache

Def. Elimination von epsilon-Kanten

Konstruktion (\epsilon-Eliminierung)

Sei $\mathcal{A}=(Q,A,\delta,I,F)$ und $\mathcal{B}=(Q,A,\delta',E(I),F)$ mit $\delta'(q,\epsilon)=\emptyset$ und $\delta'(q,x)=E(\delta(q,x))$ für $x\in A$. Behauptung: $L(\mathcal{A})=L(\mathcal{B})$

Worttransitionsfunktion für NEA ohne $\epsilon$-Transition

• $\hat\delta(R,\epsilon)=R$ Sei $w=va,v\in A^*,a\in A$
• $\hat\delta(R,va)=\bigcup_{p\in\hat\delta(R,v)}\delta(p,a)$ => Den letzten Schritt mit $a$ muss man für alle Zustände $p$ machen in den man nach lesen des Worts $v$ sein kann.