Baixe o app para aproveitar ainda mais
Prévia do material em texto
Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da Computação 2021/2 SOLUÇÃO DE 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? 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). 1 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. 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) Dê a descrição formal das máquinas M1 e M2 do Exerćıcio 1.1. (Veja figura abaixo.) Solução do professor: Dada no livro-texto. 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 Solução do professor: 2 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}. Solução do professor: Dada no livro-texto. 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}. Solução do professor: Dada no livro-texto. 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}. Solução do professor: (a) (b) (g) (i) 3 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. Solução do professor: Dada no livro-texto. 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. Solução do professor: 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. Solução do professor: 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. 4 Solução do professor: ‘ 11. (Sipser 1.11) Demonstre que todo AFN pode ser convertido em um AFN equivalente com um único estado de aceitação. Solução do professor: Dada no livro-texto. 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 .) 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. 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ó. 5 13. (Sipser 1.16) Use a construção dada no Teorema 1.39 para converter os seguintes AFNs em AFDs equivalentes. Solução do professor: (a) (b) 6 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. 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. 7
Compartilhar