Considere um autômato não determinístico NFA ܰN = (Q, ∑, δ, a, F), onde Q = {a, b, c, d, e, g} representa os estados, ∑ = {0,1} é o alfabeto, δ é a função de transição, ܽa é o estado inicial e F = {c, ƒ} os estados de aceitação, representados pelo diagrama a seguir
A linguagem desse autômato pode ser descrita como
- A {w ∈ ∑*|w contém exatamente dois 1s e pelo menos dois 0s}
- B {w ∈ ∑*|w contém exatamente dois 1s ou exatamente dois 0s}
- C {w ∈ ∑*|w contém exatamente dois 1s ou pelo menos dois 0s}
- D {w ∈ ∑*|w contém pelo menos dois 1s ou exatamente dois 0s}
- E {w ∈ ∑*|w contém pelo menos dois 1s ou pelo menos dois 0s}