AFD, AFND, Transformação AFND-AFD, Minimização
507 palavras
3 páginas
Lista de Exercícios no 3 – AFD, AFND, Transformação AFND-AFD,Minimização
1. Desenvolva autômatos que reconheçam as seguintes linguagens:
a. {w ∈ {a, b}* | aaa é subpalavra de w} a, b
a, b a S0
a
S1
a
S2
S3
b. {w ∈ {a, b}* | o sufixo de w é aa} a, b a S0
a
S1
S2
c. {w ∈{a, b}* | w possui uma quantidade ímpar de a e de b}
a
S0
S1
a b b
b
b a S2
Sf
a
d. {w ∈{a, b}* | w possui uma quantidade par de a e ímpar de b ou uma quantidade ímpar de a e par de b}
a
S0
S1
a b b
b
b a S2
S3
a
e. {w ∈{a, b}* | o quinto símbolo da direita para a esquerda de w é a} a, b a S0
a, b
S1
a, b
a, b
S2
a, b
S3
S4
S5
2. A partir de AFNDs para as linguagens descritas nos itens a e b do exercício anterior, descreva AFDs (mostrando o processo de transformação) e encontre os autômatos mínimos para os mesmos.
a)
b
a a S0
a
S01
b
a b S012
b
a
S0123
S03
b
b
b
a a a
SB
b
a
A renomeação dos estados não é obrigatória, mas é recomendável em algumas situações para que os estados resultantes das fusões de outros estados, no processo de minimização, não tenham nomes muito confusos.
Renomeando os estados:
SA
S013
b
a b SC
b
SD
a
SE
SF b a
⊗
⊗
X
X
X
SA
SB
SC
SD
SE
SF
⊗
X
X
X
SB
X
X
X
SC
SD
SE
b
a, b a a
SA
SB
a
SC
b
b
b) b a a a
S01
S0
S012 b b
Renomeando os estados: b a a a
SB
SA
SC b b
SB
SC
⊗
X
SA
X
SB
O autômato já se encontra minimizado!
SDEF
3. Minimize os autômatos mostrados nos diagramas a seguir:
a)
a
S3
a a S0
Este item pode ser resolvido sem a introdução de saída com o símbolo ‘b’ a partir do estado S0, pois, pode-se identificar a não-equivalência entre S0 e todos os demais estados trivialmente a partir do símbolo ‘a’.