Es sei ´A = (T, Z, z_0, F, delta)´ der endliche Automat, der ´L´ akzeptiert. Wir konstruieren den nicht-deterministischen endlichen Automaten ´A'´, der außer dem Zustand ´delta(z, x)´ bei Lesen von ´x´ auch noch ´q = delta(z, xa)´ berechnet. Da aber mit ´q´ nicht weitergerechnet werden darf, denn wir wollen nur das zusätzlichen ´a´ am Ende erfassen, verwenden wir dafür eine gestrichene Variante ´q'´ von ´q´, für die dann keine Nachfolgezustände definiert sind. Da wir ´b_1 b_2 … b_n´ akzeptieren wollen, wenn ´b_1 b_2 … b_n a in T(A)´ liegt, müssen wir bei Erreichen von ´z´ nach Lesen von ´b_1 b_2 … b_(n−1)´ in die Zustände ´delta(z, b_n)´ und ´delta(z, b_n a)'´ gehen und ´delta(z, b_n a)´ muss in ´F´ liegen. Erneut ist gesondert zu betrachten, ob ´a´ in ´L´ liegt. Im positiven Fall, ist das Leerwort zu akzeptieren, im negativen Fall nicht. Daher benötigen wir noch einen zusätzlichen Anfangszustand ´z_0^('')´. Dies liefert

´A' = (T, Z uu {z' | z in Z} uu {z_0^('')}, z_0^(''), F', delta')´

mit disjunkten Vereinigungen,

´delta'(z_0^(''), x) = {delta(z, x), delta(z, xa)'} " für " x in T´ ´delta'(z, x) = {delta(z, x), delta(z, xa)'} " für " z in Z, x in T´ ´delta'(z', x) = O/ " für " z in Z, x in T´

und

´F' = {({z' | z in F}, "falls " a !in T(A)), ({z' | z in F} uu {z_0^('')}, "falls " a in T(A)):}´

Es sei ´A = (T, Z, z_0, F, delta)´ der endliche Automat, der ´L´ akzeptiert. Wir konstruieren den Automaten ´A'´, der sich von ´A´ nur in der Menge der akzeptierenden Zustände unterscheidet: ein Zustand ´z´ soll genau dann akzeptierend sein, wenn es in ´A´ einen Übergang beim Lesen eines ´a´ von ´z´ in einen Zustand aus der Menge ´F´ gibt. Damit ergibt sich

´A' = (T, Z, z_0, F', delta)´

mit

´F' = {z in Z | delta(z, a) in F}´

Es gilt also

´w in T(A') <=> delta(z_0, w) in F' <=> delta(delta(z_0, w), a) in F <=> delta(z_0, wa) in F <=> wa in T(A) = L´

Somit ist die von ´A'´ akzeptierte Sprache ´T(A') = {w | wa in L} = d_r^a (L)´.