M = (Q, S, q₀, A, d) é um AFD onde: Q≠Æ, S≠Æ, q₀ÎQ, AÎQ e d: Q ´S*® Q.

Seja M = (Q, S, q₀, A, d) um AFD. d*: Q ´S*® Q - definição recursiva:

1. d*(q, L) = q, para qualquer qÎQ

2. d*(q,xa) = d(d*(q,x),a), para qualquer qÎQ, xÎS*e aÎS

Seja M = (Q, S, q₀, A, d) um AFD. xÎS* é aceite por M sse d*(q₀,x)ÎA.

LR - definição indutiva:

1. ÆÎLR, {L}Î LR, Se aÎS, então {a}ÎLR;

2. Se L₁ÎLR e L₂ÎLR, entãoL₁ÈL₂ÎLR, L₁L₂ÎLR, L₁^*ÎLR.