Lista 1 1 - Autômatos Finitos e Não-determinismo

Prévia do material em texto

Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da
Computação 2021/2
LISTA DE EXERCÍCIOS
Lista 1 - Parte 1
(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?
(b) O que é um autômato finito não-determińıstico (AFN)? O que é a linguagem reconhecida por um
AFN?
(c) Explique o que significa dizer que AFNs são equivalentes a AFDs.
(d) O que é uma linguagem regular?
Exerćıcios.
2. (Sipser 1.2) Dê a descrição formal das máquinas M1 e M2 do Exerćıcio 1.1. (Veja figura abaixo.)
3. (Sipser 1.3) A descrição formal de um AFD M é ({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}), onde δ é dada
pela tabela abaixo. Dê o diagrama d estados desta máquina.
u d
q1 q1 q2
q2 q1 q3
q3 q2 q4
q4 q3 q5
q5 q4 q5
1
4. (Sipser 1.4 - Itens (b) e (d)) Cada uma das linguagens abaixo é a interseção de duas linguagens mais
simples. Em cada item, construa AFDs para as linguagens mais simples e então combine-os usando a
construção discutida no livro-texto para prover um diagrama de estados de um AFD para a linguagem
dada. Em todos os itens, Σ = {a, b}.
(b) {w | w tem exatamente dois a’s e pelo menos dois b’s}.
(d) {w | w tem um número par de a’s e cada a é seguido por pelo menos um b}.
5. (Sipser 1.5 - Itens (a) e (b)) Cada uma das linguagens abaixo é o complemento de uma linguagem mais
simples. Em cada item, construa um AFD para a linguagem mais simples e então use-o para prover o
diagrama de estados de um AFD para a linguagem dada. Em todos os itens, Σ = {a, b}.
(a) {w | w não contém a subcadeia ab}.
(b) {w | w não contém a subcadeia baba}.
6. (Sipser 1.6 - Itens (a), (b), (g) e (i)) Dê o diagrama de estados de AFDs que reconheçam as linguagens
abaixo. Em todos os itens, o alfabeto é {0, 1}.
(a) {w | w começa com 1 e termina com 0}.
(b) {w | w contém pelo menos três 1’s}.
(g) {w | o comprimento de w é no máximo 5}.
(i) {w | toda posição ı́mpar de w contém um 1}.
7. (Sipser 1.7 - Itens (a) e (f)) Dê o diagrama de estados de AFNs com o número especificado de estados
que reconheçam as linguagens abaixo. Em todos os itens, o alfabeto é {0, 1}.
(a) A linguagem {w | w termina com 00}, usando três estados.
(f) A linguagem 1∗(001+)∗, usando três estados.
8. (Sipser 1.8 - Item (a)) Use a construção dada na prova do Teorema 1.45 para prover o diagrama de
estados de AFNs que reconheçam a união das linguagens descritas
(a) Nos exerćıcios 1.6(a) e 1.6(b), dadas acima.
9. (Sipser 1.9 - Item (a)) Use a construção dada na prova do Teorema 1.47 para prover o diagrama de
estados de AFNs que reconheçam a concatenação das linguagens descritas
(a) Nos exerćıcios 1.6(g) e 1.6(i), dadas acima.
10. (Sipser 1.10 - Item (a)) Use a construção dada na prova do Teorema 1.49 para prover o diagrama de
estados de AFNs que reconheçam o fecho de Kleene das linguagens descritas
(a) No exerćıcio 1.6(b), dada acima.
‘
11. (Sipser 1.11) Demonstre que todo AFN pode ser convertido em um AFN equivalente com um único
estado de aceitação.
12. (Sipser 1.13) Seja F a linguagem de todas as cadeias sobre o alfabeto {0, 1} que não contêm nenhum
par de 1’s separados por um número ı́mpar de śımbolos. Dê o diagrama de estados de um AFD com
5 estados que reconheça F . (Pode ser útil primeiro encontrar um diagrama de um AFN de 4 estados
para o complemento de F .)
2
13. (Sipser 1.16) Use a construção dada no Teorema 1.39 para converter os seguintes AFNs em AFDs
equivalentes.
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.
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.
3