Lista1 1_AFDs-AFNs[solucao] FTC UFMG LISTA

Prévia do material em texto

Área de Teoria DCC/UFMG Fundamentos de Teoria da Computação 2020/01
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 1 - Parte 1/3
(Linguagens Regulares: Autômatos Finitos e Não-determinismo)
Leitura necessária:
• Introdução à Teoria da Computação, 2a Edição (Michael Sipser):
– Caṕıtulo 1.1: Autômatos Finitos
– Caṕıtulo 1.2: Não-determinismo
• Material suplementar:
– Conjunto de slides: Aula 1.1 - Autômatos Finitos e Não-determinismo.
Revisão.
1. Responda formalmente às seguintes perguntas:
(a) O que é um autômato finito determińıstico (AFD)? O que é a linguagem reconhecida por um
AFD?
Solução do professor: Um autômato finito determińıstico é uma 5-tupla (Q,Σ, δ, q0, F ), onde:
1. Q é um conjunto finito de estados,
2. Σ é um conjunto finito chamado de alfabeto,
3. δ : Q× Σ→ Q é uma função de transição,
4. q0 ∈ Q é o estado inicial, e
5. F ⊆ Q é o conjunto de estados de aceitação (ou estados finais).
A linguagem L(M) reconhecida por um AFD M é o conjunto de todas as cadeias que podem ser
formadas com o alfabeto de entrada Σ tais que, ao iniciar o processamento no estado inicial q0,
a máquina M executa transições de acordo com a função de transição δ e termina de consumir a
palavra parando num estado de aceitação qi ∈ F .
(b) O que é um autômato finito não-determińıstico (AFN)? O que é a linguagem reconhecida por um
AFN?
Solução do professor: Um autômato finito não-determińıstico é uma 5-tupla (Q,Σ, δ, q0, F ),
onde:
1. Q é um conjunto finito de estados,
2. Σ é um conjunto finito chamado de alfabeto,
3. δ : Q× Σ� → P(Q) é uma função de transição, onde Σ� = Σ ∪ {�},
4. q0 ∈ Q é o estado inicial, e
5. F ⊆ Q é o conjunto de estados de aceitação (ou estados finais).
A linguagem L(N) reconhecida por um AFN N é o conjunto de todas as cadeias que podem ser
formadas com o alfabeto de entrada Σ tais que, ao iniciar o processamento no estado inicial q0,
a máquina N executa transições de acordo com a função de transição δ, e existe ao menos uma
computação que termina de consumir a palavra parando num estado de aceitação qi ∈ F .
(c) Explique o que significa dizer que AFNs são equivalentes a AFDs.
1
Solução do professor: Dizer que AFDs e AFNs são equivalentes significa dizer que: (i) se
exite um AFD que reconhece uma linguagem, então também existe um AFN que reconhece a
mesma linguagem; e (ii) se exite um AFN que reconhece uma linguagem, então também existe
um AFD que reconhece a mesma linguagem.
(d) O que é uma linguagem regular?
Solução do professor: Uma linguagem regular é uma linguagem que pode ser reconhecida por
um autômato finito determińıstico.
Exerćıcios.
2. (Sipser 1.2)
Solução do professor: Dada no livro-texto.
3. (Sipser 1.3)
Solução do exerćıcio 1.3
4. (Sipser 1.4 - Itens (b) e (d))
Solução do professor: Dada no livro-texto.
5. (Sipser 1.5 - Itens (a) e (b))
Solução do professor: Dada no livro-texto.
6. (Sipser 1.6 - Itens (a), (b), (g) e (i))
7. (Sipser 1.7 - Itens (a) e (f))
Solução do professor: Dada no livro-texto.
8. (Sipser 1.8 - Item (a))
2
Solução do exerćıcio 1.6 (a)
Solução do exerćıcio 1.6 (b)
Solução do exerćıcio 1.6 (g)
Solução do exerćıcio 1.6 (i)
Solução do professor:
Solução do exerćıcio 1.8 (a)
9. (Sipser 1.9 - Item (a))
3
Solução do professor:
Solução do exerćıcio 1.9 (a)
10. (Sipser 1.10 - Item (a))
Solução do professor:
Solução do exerćıcio 1.10 (a)
11. (Sipser 1.11)
Solução do professor: Dada no livro-texto.
12. (Sipser 1.13)
Solução do professor: Para resolver este problema, seguimos os 4 passos a seguir.
Passo 1 Constrúımos um AFN N para a linguagem F de todas as cadeias sobre {0, 1} que contenham
um par de śımbolos 1 que estejam separados porum número ı́mpar de śımbolos.
Solução do exerćıcio 1.13 - Passo 1: construção do AFN N para F
4
Solução do exerćıcio 1.13 - Passo 2: conversão do AFN N para AFD M para F
Solução do exerćıcio 1.13 - Passo 3: AFD M ′ para F
Passo 2 Transformamos o AFN N em um AFD M equivalente.
Passo 3 Transformamos o AFD M que reconehce F em um AFD M ′ que reconhece F .
Passo 3 Notamos que no AFD M ′ os estados {A,B,D}, {A,C,D} e {A,B,C,D} são equivalentes
entre si, e, na verdade, formam um estado de tragédia (uma vez atingido qualquer um destes
estados, a cadeia de entrada deve ser rejeitada com certeza). Minimizamos o AFD M ′ ao juntar
estes três estados em um só.
Solução do exerćıcio 1.13 - Passo 4: Minimização do AFD M ′ para F
13. (Sipser 1.16)
Solução do exerćıcio 1.16 (a)
5
Solução do exerćıcio 1.16 (b)
14. (Newton Vieira 2.2-10)
O AFD abaixo reconhece o conjunto das palavras binárias que começam com 0 ou terminam com 1.
AFD do exerćıcio (Newton) 2.2-10
Usando o algoritmo visto em sala de aula, minimize este AFD. Proveja todo seu racioćınio, demons-
trando como você determinou, passo a passo, quais estados são equivalentes neste AFD.
Solução do professor: A primeira partição dos estados separa os estados finais dos não-finais:
P0 = {{[�, �], [c1, t0]}, {[c0, t0], [c0, t1], [c1, t1]}}.
As partições seguintes são:
P1 = {{[�, �]}, {[c1, t0]}, {[c0, t0], [c0, t1]}, {[c1, t1]}}
e
P2 = {{[�, �]}, {[c1, t0]}, {[c0, t0], [c0, t1]}, {[c1, t1]}}.
Como P2 não se altera em relação a P1, sabemos que os estados equivalentes são aqueles representados
em P2.
Assim podemos construir um AFD mı́nimo equivalente como na figura abaixo.
6
Solução do exerćıcio exerćıcio (Newton) 2.2-10
7