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}
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’.
a
b
S1
S4
a
b
b
S2
b
⊗
⊗
X
X
S0
S1
S2
S3
S4
X
X
S1
X
X
S2
S3
a
a
a
S0
S34
S12
b
b
b)
b
S0
a
S2
S4
a
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.
b
a a
b
a
b
S1
b
S3
S1
S2
S3
S4
S5
X
X
X
⊗
S0
a, b
X
X
X
⊗
S1
X
S2
X
S3
X
S4
a
a
S01
S5
b
S234
b
S5
a, b
S5 é um estado morto, se a função do
autômato for considerada parcial, este
estado poderia ser excluído.