Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (xx)*(y + z)z*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados (Ricarte, 2008).
Autômato Finito com Movimentos Vazios (AFε)
M = ({x, y, z}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19, q20}, δ, q0, {q20})
δ |
x |
y |
z |
ε |
q0 |
- |
- |
- |
{q1} |
q1 |
- |
- |
- |
{q2, q7} |
q2 |
- |
- |
- |
{q3} |
q3 |
{q4} |
- |
- |
- |
q4 |
{q5} |
- |
- |
- |
q5 |
- |
- |
- |
{q6} |
q6 |
- |
- |
- |
{q2, q7} |
q7 |
- |
- |
- |
{q8} |
q8 |
- |
- |
- |
{q9, q11} |
q9 |
- |
{q10} |
- |
- |
q10 |
- |
- |
- |
{q13} |
q11 |
- |
- |
{q12} |
- |
q12 |
- |
- |
- |
{q13} |
q13 |
- |
- |
- |
{q14} |
q14 |
- |
- |
- |
{q15, q19} |
q15 |
- |
- |
- |
{q16} |
q16 |
- |
- |
{q17} |
- |
q17 |
- |
- |
- |
{q18} |
q18 |
- |
- |
- |
{q15, q19} |
q19 |
- |
- |
- |
{q20} |
q20 |
- |
- |
- |
- |
Autômato Finito Determinístico (AFD)
M = ({x, y, z}, {s0, s1, s2, s3, s4, s5}, δ, s0, {s2, s3, s5})
δ |
x |
y |
z |
s0 |
s1 |
s2 |
s3 |
s1 |
s4 |
- |
- |
s2 |
- |
- |
s5 |
s3 |
- |
- |
s5 |
s4 |
s1 |
s2 |
s3 |
s5 |
- |
- |
s5 |
Autômato Finito Determinístico (AFD) Simplificado
M = ({x, y, z}, {C0, C1, C2}, δ, C2, {C0})
δ |
x |
y |
z |
C0 |
- |
- |
C0 |
C1 |
C2 |
- |
- |
C2 |
C1 |
C0 |
C0 |