1ª Prova de Autômatos e Computabilidade - 1º/2015 - Lucero - UnB

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
Prof. Jorge C. Lucero
13 de abril de 2015
Nome: Matr´ıcula:
1. (2 pontos) Prove que a classe das linguagens regulares e´ fechada sobre a operac¸a˜o de inter-
sec¸a˜o. Fac¸a uma prova por construc¸a˜o.
2. (2 pontos) Sejam os AFNs N1 = (Q1,Σ, δ1, q1, F1) e N2 = (Q2,Σ, δ2, q2, F2). Defina formal-
mente um AFN que reconhec¸a a linguagem L(N1) ◦ L(N2).
3. (1 ponto) Seja o AFD mostrado no diagrama abaixo. Usando a definic¸a˜o de n-equivaleˆncia
de estados, mostre que os estados 4 e 5 sa˜o 2-equivalentes.
4. (a) (1 ponto) Desenhe o diagrama de estados de um autoˆmato finito que reconhec¸a a
linguagem ((ab)∗ ∪ (bc)∗)ab.
(b) (1 ponto) Qual e´ o comprimento mı´nimo de bombeamento dessa linguagem? Explique
sua resposta.
5. (1 ponto) Toda linguagem finita e´ regular. A afirmac¸a˜o e´ verdadeira ou falsa? Justifique
sua resposta.
6. (2 pontos) Prove que a linguagem L = {ww|w ∈ {a, b}∗} na˜o e´ regular, onde w e´ a
cadeia obtida a partir de w trocando todos os as por bs e vice-versa. Utilize o Lema do
bombeamento. Explique claramente a aplicac¸a˜o do Lema.