Παράδειγμα

Ορίζουμε ένα αυτόματο Μ = (Κ, Σ, Γ, δ, q₀, Z₀) ως εξής:

Κ

{Α}

Σ

{'(', ')'}

Γ

{Χ, I}

Δ

{

δ(Α, Ι, '(') = (ΒΑΛΕ(Ι))
δ(Α, Χ, '(') = (ΒΑΛΕ(Ι))
δ(Α, Ι, ')') = (ΒΓΑΛΕ)

}

q₀

A

Z₀

X

Το αυτόματο αυτό αναγνωρίζει ζυγισμένα ζευγάρια παρενθέσεων.