Exercicios Resolvidos DFA NFA

Prévia do material em texto

UNIVERSIDADE ESTADUAL DE MARINGÁ – UEM 
CENTRO DE TECNOLOGIA – CTC 
DEPARTAMENTO DE INFORMÁTICA – DIN 
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
PROFESSOR: YANDRE MALDONADO E GOMES DA COSTA 
 
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} 
 
 
 
 
 
 
 
b. {w ∈ {a, b}* | o sufixo de w é aa} 
 
 
 
 
 
 
c. {w ∈{a, b}* | w possui uma quantidade ímpar de a e de b} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
S0 S1 
a 
S2 
a 
a, b 
S3 
a 
a, b 
S0 S1 
a 
S2 
a 
a, b 
S0 
S2 Sf 
S1 
b b b b 
a 
a 
a 
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} 
 
 
 
 
 
 
 
 
 
 
 
e. {w ∈{a, b}* | o quinto símbolo da direita para a esquerda de w é a} 
 
 
 
 
 
 
 
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) 
 
 
 
 
 
 
 
 
Renomeando os estados: 
 
 
 
 
 
 
 
 
 
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. 
S0 
S2 S3 
S1 
b b b b 
a 
a 
a 
a 
S0 S1 
a 
S2 
a, b 
a, b 
S3 S4 S5 
a, b a, b a, b 
S0 S01 
a 
b 
b 
a 
S012 
a 
b 
S0123 
a 
a 
S03 
b 
b 
S013 
a 
b 
SA SB 
a 
b 
b 
a 
SC 
a 
b 
SD 
a 
a 
SE 
b 
b 
SF 
a 
b 
SB ⊗ 
SC ⊗ ⊗ 
SD X X X 
SE X X X 
SF X X X 
 SA SB SC SD SE 
 
 
 
 
 
 
 
 
 
b) 
 
 
 
 
 
 
 
Renomeando os estados: 
 
 
 
 
 
 
 
 
SB ⊗ 
SC X X 
 SA SB 
 
O autômato já se encontra minimizado! 
 
 
 
 
 
 
 
SA SB 
a 
b 
b 
SC 
a 
b 
SDEF 
a 
a, b 
S0 
a 
b 
b 
S01 
a 
S012 
b 
a 
SA 
a 
b 
b 
SB 
a 
SC 
b 
a 
3. Minimize os autômatos mostrados nos diagramas a seguir: 
 
a) 
 
 
 
 
 
 
 
 
 
S1 ⊗ 
S2 ⊗ 
S3 X X X 
S4 X X X 
 S0 S1 S2 S3 
 
 
 
 
 
 
 
b) 
 
 
 
 
 
 
 
S1 
S2 X X 
S3 X X 
S4 X X 
S5 ⊗ ⊗ X X X 
 S0 S1 S2 S3 S4 
 
 
 
 
 
 
S0 
S3 
S1 
S2 
S4 
a 
a 
b 
b 
a 
b 
a 
b 
a 
S0 S34 S12 a 
a 
a 
b 
b 
S0 
S3 S1 S5 
S4 
a 
a 
b 
b 
a 
b 
a S2 
b 
a 
b 
a, b 
Para aplicar o algoritmo de minimização 
estudado, o autômato deve ter função 
de transição total. Para isto, 
acrescentou-se estas transições, já que 
S5 não é estado final e não tem outras 
transições que partem dele. 
S01 S5 
b 
a 
S234 b a, b 
a 
S5 é um estado morto, se a função do 
autômato for considerada parcial, este 
estado poderia ser excluído. 
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’.