La definizione della funzione delta segnato e' nei testi.

Indichiamo con D il simbolo delta e con D' il simbolo delta segnato.
Con e indichiamo la stringa vuota epsilon.

Allora, cerchiamo di dimostrare che, per qualsiasi stato q e stringhe x e y, e' vero che

D'(q,xy) = D'(D'(q,x),y)

Lo facciamo per induzione sulla lunghezza della stringa y.

Caso base:  |y|=0

Se |y|=0 vuol dire che y=. e quindi dobbiamo dimostrare che
D'(q,x.) = D'(D'(q,x),e)

   D'(q,xe) =         poiche'   xe=x
= D'(q,x)  =         [completare!]


Caso induttivo:  |y|=n+1   con n>=0

In questo caso y ha necessariamente la seguente forma: y=za
Dobbiamo quindi dimostrare che
D'(q,xza) = D'(D'(q,x),za)
supponendo che quel che vogliamo dimostrare valga per tutte le stringhe di lunghezza n.
In particolare, poiche' |y|=n+1 avremo che |z|=n, e quindi
l'ipotesi induttiva che possiamo utilizzare e' che
D'(q,xz) = D'(D'(q,x),z)

    D'(q,xza)      =      per definizione di D'
= D(D'(q,xz),a) =      per ipotesi induttiva
= [continuare]


Completate la dimostrazione.