Baixe o app para aproveitar ainda mais
Prévia do material em texto
Autoˆmatos e Computabilidade: Prova 1 1. Defina formalmente: (a) (0,25 ponto) Alfabeto Resposta: qualquer conjunto finito e na˜o vazio. (b) (0,25 ponto) Cadeia Resposta: qualquer sequeˆncia finita de elementos (s´ımbolos) de um alfabeto. (c) (0,25 ponto) Linguagem Resposta: qualquer conjunto de cadeias. (d) (1,25 pontos) Expressa˜o regular Resposta: uma expressa˜o regular sobre uma alfabeto Σ e´: (1) a, onde a ∈ Σ, (2) ε, (3) ∅, (4) R1 ∪ R2, onde R1 e R2 sa˜o expresso˜es regulares, (5) R1 ◦ R2, onde R1 e R2 sa˜o expresso˜es regulares, ou(4) R∗1, onde R1 e´ uma expressa˜o regular. 2. (1,5 ponto) Prove que a linguagem L = {anbabc2n|n > 0} na˜o e´ regular. Utilize o Lema do bombeamento. Resposta: Suponha L regular, e seja p seu comprimento de bombeamento. Considere a cadeia w = apbabc2p. Assim, w ∈ L e |w| = 3p + 3 ≥ p. Dividimos w na forma w = xyz. As condic¸o˜es |xy| ≤ p e |y| > 0 implicam que y esta´ contido na sequeˆncia inicial de as e que y = ak, com 0 < k ≤ p. Enta˜o, xyyz = ap+kbabc2p. Nesta cadeia, a quantidade de cs (2p) na˜o e´ igual ao duplo da quantidade da as (p+ k) na sequeˆncia inicial, portanto, xyyz /∈ L. Concluimos que L na˜o satisfaz o Lema e enta˜o deve ser na˜o regular. 3. (1,5 pontos) A diferenc¸a entre dois conjuntos A e B e´ definida como A − B = {x| x ∈ A e x /∈ B}. Se L1 e L2 sa˜o linguagens regulares, enta˜o L1 − L2 sempre e´ regular? Prove sua resposta. Resposta: note que L1 − L2 = {x| x ∈ L1 e x /∈ L2} = L1 ∩ L2. A classe das linguagens regulares e´ fechada sobre as operac¸o˜es de intersec¸a˜o e complementac¸a˜o, portanto, L1 − L2 sempre e´ regular. 4. Seja a seguinte linguagem TRIPLES = {a3n|n ≥ 0} (a) (1 ponto) Fornec¸a uma expressa˜o regular para TRIPLES Resposta: (aaa)∗. (b) (0,5 ponto) Considere agora a seguinte prova de que TRIPLES na˜o e´ regular: i. Suponha TRIPLES regular. Enta˜o, TRIPLES satisfaz o lema do bombeamento; seja p seu comprimento de bombeamento. ii. Escolha a cadeia de teste w = xyz = a3p. iii. O lema do bombeamento exige |xy| ≤ p e |y| > 0. Fac¸a, enta˜o, y = a. iv. Enta˜o, xy2z = a3p+1. v. 3p + 1 na˜o e´ mu´ltiplo de 3, enta˜o xy2z /∈ TRIPLES. Portanto, TRIPLES na˜o satisfaz o lema do bombeamento. vi. A contradic¸a˜o implica que TRIPLES na˜o e´ regular. Claramente, esta prova contradiz o item (a). O que esta´ errado? Resposta: A prova na˜o considera todas as poss´ıveis subdiviso˜es da cadeia de teste. (c) (0,5 ponto) Qual o comprimento mı´nimo de bombeamento de TRIPLES? Justifique sua resposta. Resposta: O comprimento mı´nimo e´ 1. Se w e´ uma cadeia de TRIPLES e |w| ≥ 1, enta˜o w = a3n, com n ≥ 1, e pode ser bombeada fazendo x = ε, y = aaa e z igual ao restante da cadeia. A cadeia vazia na˜o pode ser bombeada, pois na˜o poderia satisfazer |y| > 0. 5. (1 ponto) A expressa˜o regular Σ+@Σ+.Σ+, onde Σ conte´m todas as letras do alfabeto, descreve enderec¸os de e-mail da forma john@something.something. Desenhe o diagrama de estados de um autoˆmato finito na˜o determin´ıstico que reconhec¸a a linguagem descrita por essa expressa˜o. Nos ro´tulos das transic¸o˜es do autoˆmato, pode usar o s´ımbolo Σ para indicar qualquer s´ımbolo do alfabeto. Note que os s´ımbolos @ e . na˜o pertencem a Σ. Resposta: q0 q1 q2 q3 q4 q5 Σ Σ @ Σ Σ . Σ Σ 6. (2 pontos) Prove que para todo AFN existe um AFD equivalente. Na sua prova, considere somente o caso de AFNs sem transic¸o˜es-ε. Resposta: A prova e´ por construc¸a˜o. Seja um AFN N = (Q,Σ, δ, q0, F ) sem transic¸o˜es-ε. Constru´ımos um AFD equivalente M = (Q′,Σ, δ′, q′0, F ′) fazendo: Q′ = P(Q), δ′(R,a) = ⋃ r∈R δ(r,a), para R ∈ Q′ e a ∈ Σ, q′0 = {q0}, F ′ = {R|R ∈ Q′ e R conte´m um estado de aceitac¸a˜o de N}
Compartilhar