Exemplo:
Seja a gramática G = (Σ,Q,δ,q0,F,V,Γ) tal que:
Σ = {a,b,λ}
Q = {q0,q1,q2}
F = q2
V = {0,1}
Γ = 0
δ(q0,a,0) → (q0,10)
δ(q0,a,1) → (q0,11)
δ(q0,b,1) → (q1,λ)
δ(q1,b,1) → (q1,λ)
δ(q1,λ,0) → (q2,λ)
(q0,aabb,0) → (q0,abb,10) → (q0,bb,110) → (q1,b,10) → (q1,λ,0) → (q2,λ,λ):.
Cadeia 'aabb' aceita.