Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a*(b + c)c*. 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.
Autômato Finito com Movimentos Vazios (AFε)
M = ({a, b, c}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19}, δ, q0, {q19})
δ |
a |
b |
c |
ε |
q0 |
- |
- |
- |
{q1} |
q1 |
- |
- |
- |
{q2, q6} |
q2 |
- |
- |
- |
{q3} |
q3 |
{q4} |
- |
- |
- |
q4 |
- |
- |
- |
{q5} |
q5 |
- |
- |
- |
{q2, q6} |
q6 |
- |
- |
- |
{q7} |
q7 |
- |
- |
- |
{q8, q10} |
q8 |
- |
{q9} |
- |
- |
q9 |
- |
- |
- |
{q12} |
q10 |
- |
- |
{q11} |
- |
q11 |
- |
- |
- |
{q12} |
q12 |
- |
- |
- |
{q13} |
q13 |
- |
- |
- |
{q14, q18} |
q14 |
- |
- |
- |
{q15} |
q15 |
- |
- |
{q16} |
- |
q16 |
- |
- |
- |
{q17} |
q17 |
- |
- |
- |
{q14, q18} |
q18 |
- |
- |
- |
{q19} |
q19 |
- |
- |
- |
- |
Autômato Finito Determinístico (AFD)
M = ({a, b, c}, {s0, s1, s2, s3, s4}, δ, s0, {s2, s3, s4})
δ |
a |
b |
c |
s0 |
s1 |
s2 |
s3 |
s1 |
s1 |
s2 |
s3 |
s2 |
- |
- |
s4 |
s3 |
- |
- |
s4 |
s4 |
- |
- |
s4 |
Autômato Finito Determinístico (AFD) Simplificado
M = ({a, b, c}, {C0, C1}, δ, C1, {C0})
δ |
a |
b |
c |
C0 |
C1 |
C0 |
C0 |
C1 |
- |
- |
C0 |