"Zuerst formen wir die Grammatik um, damit wir nur noch die terminierende Regel ´$ -> lambda´ haben. Dies ergibt folgende Regelmenge:\n\n´P = {S -> aA_1, S -> bA_2, A_1 -> aA_2, A_2 -> cA_3, A_3 -> a$, A_3 -> b$, $ -> lambda}´\n\nWir konstruieren zuerst einen nichtdeterministischen Automaten. Hierfür wird aus jeder Regel ´X -> xY´ ein Übergang ´Y in delta(X, x)´, der Anfangszustand ist ´S´ und die Menge ´F´ der akzeptierenden Zustände ist ´{$}´. Für ´delta´ ergibt sich:\n\n´delta´ | ´S´ | ´A_1´ | ´A_2´ | ´A_3´ | ´$´\n---|---|---|---|---|---\n´a´ | ´{A_1}´ | ´{A_2}´ | ´O/´ | ´{$}´ | ´O/´\n´b´ | ´{A_2}´ | ´O/´ | ´O/´ | ´{$}´ | ´O/´\n´c´ | ´O/´ | ´O/´ | ´{A_3}´ | ´O/´ | ´O/´\n\n\nMan sieht, dass alle Mengen einelementig, d.h. der Automat ist deterministisch. Formal muss als Zustand aber eine Menge verwendet werden und der erreichbare Zustand der leeren Menge mit betrachtet werden. Dies liefert den endlichen Automaten\n\n´delta´ | ´{S}´ | ´{A_1}´ | ´{A_2}´ | ´{A_3}´ | ´{$}´ | ´O/´\n---|---|---|---|---|---|---\n´a´ | ´{A_1}´ | ´{A_2}´ | ´O/´ | ´{$}´ | ´O/´ | ´O/´\n´b´ | ´{A_2}´ | ´O/´ | ´O/´ | ´{$}´ | ´O/´ | ´O/´\n´c´ | ´O/´ | ´O/´ | ´{A_3}´ | ´O/´ | ´O/´ | ´O/´\n\n\nDer gleiche Automat entsteht, wenn man mit ´{S}´ anfängt und nun die daraus erreichbaren Zustände ermittelt und von diesen aus analog fortfährt, d.h. die Teilmengen von ´{S, A_1 , A_2 , A_3 , $}´ die mindestens zwei Elemente enthalten sind nicht erreichbar und daher entbehrlich."