Prévia do material em texto
Universidade Federal de Roraima Centro de Ciência e Tecnologia Departamento de Ciência da Computação ______________________________________________________________________________________________ 1a. Lista de Exercícios de Fundamentos da Computação 1) Escreva todos os prefixos, sufixos e subpalavras para as palavras a seguir: a. aaa b. abcb c. aaba 2) É possível generalizar e responder qual é o número de prefixos, sufixos e subpalavras de uma palavra de tamanho n? 3) Explique a diferença entre Σ= {0,1} e Σ1={0,1}. 4) Considerando um alfabeto ∑, explique o que representa ∑* - {ε}. Dê um exemplo. 5) Dados os AFD M1 e M2, responda às seguintes questões sobre cada um deles: a. Qual é o estado inicial? b. Qual é o conjunto de estados de aceitação? c. Por qual sequência de estados a máquina passa para a entrada aabb? d. A máquina aceita a cadeia aabb? e. A máquina aceita a cadeia ε? f. Dê a descrição formal das máquinas M1 e M2. 6) A descrição formal de um AFD M é ({q 1, q2, q3, q4, q5}, {u,d}, δ, q3, {q3}), onde δ é dada pela tabela a seguir. Dê o diagrama de estados dessa máquina. δ u d q1 q1 q2 q2 q1 q3 q3 q2 q4 q4 q3 q5 q5 q4 q5 7) Construa AFDs (dê o diagrama de estados) para as seguintes linguagens sobre o alfabeto {0,1}: a. O conjunto das palavras de tamanho 3. b. O conjunto das palavras com no máximo três 1's. c. O conjunto das palavras de tamanho múltiplo de 3. d. O conjunto de palavras que começam com um 1 e terminam com um 0. e. O conjunto de palavras que contém a subcadeia 0101. f. O conjunto das palavras que contêm exatamente dois 1's e um número ímpar de 0's. g. O conjunto das palavras que têm a forma {10}n com n ≥ 0. h. O conjunto das palavras que não termina em 01. 8) Construa AFNs reconhecendo cada uma das linguagens a seguir. a. A linguagem {ε} com 1 estado. b. A linguagem {w | w termina com 00} com 3 estados. c. A linguagem que tem bb ou não tem aa para o alfabeto {a,b}. d. A linguagem {w є {a, b, c}* | o último símbolo de w seja idêntico ao primeiro}. 9) Seja o AFN M = ({q1, q2, q3}, {a,b}, δ, {q1}, {q1, q2, q3}), onde δ é dada pela tabela a seguir. δ a b q1 {q2} {} q2 {q3} {} q3 {} {q3} Obtenha um AFN com um único estado final equivalente a M. 10) Converta os AFNs abaixo em AFDs: 11) Dado o AFN M = ({q0, q1}, {0, 1}, δ, q0, {q1}) e: δ 0 1 q0 {q0,q1} {q1} q1 {} {q0,q1} Construir o AFD equivalente. 12) Minimize o seguinte AFD: 13) Especifique um AFD mínimo que, dentre as palavras que se escrevem com os símbolos 0, 1 e 2, aceite apenas aquelas cujo somatório dos símbolos, interpretados como números, seja divisível por 3. 14) A descrição formal de um AFD M é ({q 0, q1, q2, q3, q4}, {0,1}, δ, q0, {q2, q4}), onde δ é dada pela tabela a seguir. Minimize M. δ 0 1 q0 q3 q1 q1 q4 q1 q2 q3 q0 q3 q2 q3 q4 q1 q0 15) Formalize as linguagens abaixo usando apenas operações básicas sobre conjuntos (concatenação, união, fechos de Kleene, etc.). a. {p ∈ {a, b}* | p começa com aa e termina com bb}. b. {p ∈ {a, b}* | p começa com aa ou termina com bb}. c. {p ∈ {a, b}* | p possui tamanho par}. d. {p ∈ {a, b}* | p possui tamanho ímpar}. e. {p ∈ {a, b}* | p começa e termina com a e contém pelo menos um b}. f. {p ∈ {a, b}* | p contém exatamente dois b's}. g. {p ∈ {0,1}* | todo 0 em p é seguido de 11}. h. {p ∈ {0,1}* | p tem tamanho par e começa com 0 ou termina com 0}. i. {p ∈ {0,1}* | p termina com 0 seguido de um número ímpar de 1's}. 16) Dada a seguinte linguagem, faça: L={p ∈ {a, b, c}* | p contém ao menos um a e ao menos um b} a. Faça uma GR que gere L (sem converter AFD em GR); b. Faça uma ER que represente L; c. Faça um AFN que reconheça L; d. Converta o AFN encontrado em (c) em uma GR e compare com a GR encontrada em (a); e. Converta a GR encontrada em (a) em um AFN e compare com o AFN encontrado em (c), f. Converta o AFN encontrado em (c) em uma ER e compare com a ER encontrada em (b); g. Converta a ER encontrada em (b) em um AFN e compare com o AFN encontrado em (c). 17) Para as linguagens abaixo, se forem regulares, apresente uma GR e uma ER, caso contrário use o lema do bombeamento para provar que não são regulares (todas as variáveis apresentadas pertencem aos naturais): a. {(ab)nak | n > k, k >= 0)} b. {aibmcn | i > 0, 0 < m < n} c. {aibmc2m | i, m, n ≥ 0} d. {aibmcn | i ,m ≥ 0} e. {anbmcn | n < 3 ,m ≥ 0}