Espressione regolare che denota L

(a+b)*b(a*b)

Grammatica che genera L

S--> XbY
X--> aX |  bX | epsilon
Y --> a | b

Automa NON deterministico che riconosce L

M = ({a, b}, {q₀, q₁, q₂}, delta, q₀, {q₂})
dove delta e' definita dalla seguente tabella

delta |   a      b
--------------------------
q0    |   q0     {q0,q1}
--------------------------
q1    |   q2     q2
--------------------------
q2    |   -      -
--------------------------

Automa deterministico che riconosce L

M = ({a, b}, {q₀, q₁, q₂, q₃}, delta, q₀, {q₂, q₃})
dove delta e' definita dalla seguente tabella

delta |   a      b
--------------------------
q0    |   q0     q1
--------------------------
q1    |   q2     q3
--------------------------
q2    |   q0     q1
--------------------------
q3    |   q2     q3
--------------------------