Dimostriamo che, per ogni n, la stringa aⁿb e' riconosciuta dall'automa.
Lo facciamo per induzione su n
Caso base: n=0
La stringa b e' riconosciuta dall'automa poiche' da q₀, leggendo b arriviamo all'unico stato finale q₁.
Caso induttivo: sia n un numero generico diverso da 0. Supponiamo ora che la stringa a^(n-1)b sia riconosciuta dall'automa e facciamo vedere che lo e' anche aⁿb.
Poiche' l'unico stato finale e' q₁, la stringa aⁿb e' riconosciuta se e solo se δ(q₀,aⁿb) = q₁
δ(q₀,aⁿb) = (per definizione di δ)
= δ(δ(q₀,a),a^(n-1)b) = (poiche' δ(q₀,a)=q₀)
= δ(q₀,a^(n-1)b) = (per ipotesi induttiva)
= q₁