2013_2 - Lista 01

Prévia do material em texto

Fundamentos da Teoria da Computac¸a˜o 2o semestre de 2013
Professor: Jeroen Antonius Maria van de Graaf DCC/ICEx/UFMG
Lista de Exerc´ıcios Preparato´ria para a Primeira Prova
Fonte: Newton Jose´ Vieira – DCC/ICEx/UFMG
1. Fac¸a definic¸o˜es recursivas das seguintes linguagens, considerando a concatenac¸a˜o como a
operac¸a˜o ba´sica no passo recursivo:1
a) {0, 1}+.
b) {0, 1}∗{0}{0, 1}∗.
c) {0}{0, 1}∗{0}.
d) {0n13n |n ∈ N}.
e) {wwR |w ∈ {0, 1}∗}.
f) {x1 + · · · + xn |n ≥ 1 e xi ∈ {0, 1}
+ para i = 1, . . . , n}. Dica: Fac¸a duas definic¸o˜es
recursivas separadas, a primeira definindo o que pode ser cada xi.
2. Perguntinhas:
(a) Que palavras tem cada uma das linguagens a seguir?
∅∗; ∅+; {λ}∗; {λ}+; {0}∗; {0}+;{λ, 0}∗; {λ, 0}+.
(b) Em que situac¸o˜es L∗ e L+ sa˜o finitas?
(c) Seja Σ um alfabeto. Explique que palavras pertencem a cada uma das linguagens:
• Σn para cada n ≥ 0; que valor tem |Σn|?
• (Σ ∪ {λ})n para cada n ≥ 0; que valor tem |(Σ ∪ {λ})n|?
(d) Sejam Σ = {a, b}, A = {a}Σ+ e B = Σ∗{b}. Apresente uma condic¸a˜o necessa´ria e
suficiente para que uma palavra de Σ∗ pertenc¸a a AA, AB, BB, A ∩ B, A − B e
B −A.
3. Descreva as linguagens a seguir, todas sobre o alfabeto {0, 1}, usando apenas conjuntos
finitos e operac¸o˜es de unia˜o, intersec¸a˜o, complementac¸a˜o, concatenac¸a˜o e fecho de Kleene.
Procure obter uma descric¸a˜o bem concisa.
(a) O conjunto das palavras de prefixo 01.
(b) O conjunto das palavras que na˜o conteˆm 01 como sufixo.
(c) O conjunto das palavras que na˜o conteˆm 01 como subpalavra.
(d) O subconjunto das palavras de {0}∗{1}∗ com nu´mero par de 0s.
(e) O conjunto das palavras com no ma´ximo vinte s´ımbolos.
(f) O conjunto das palavras que conteˆm pelo menos um 0 e um 1.
(g) O conjunto das palavras em que todo 0 e´ seguido de pelo menos dois s´ımbolos.
(h) O conjunto das palavras que conteˆm pelo menos um 00, mas nenhum 11.
1Veja a Sec¸a˜o 1.7, pa´g. 28, do livro-texto.
1
4. Identifique as linguagens que sa˜o geradas pelas grama´ticas a seguir:
(a) G1 = ({P,X}, {a, b}, R1 , P ).
R1: P → aP |Xb |λ
X → aP
(b) G2 = ({P,X}, {a, b}, R2 , P ).
R2: P → aaP |Xb |λ
X → aP
(c) G3 = ({P,A}, {0, 1}, R3 , P ).
R3: P → aPa |A
A → bAb |λ
(d) G4 = ({A,X}, {0, 1}, R4 , A).
R4: A → XAX |X
X → 0X0 | 1X1 | 0 | 1
(e) G5 = ({X,B}, {a, b, c}, R5 ,X).
R5: X → aBX | abc
Ba → aB
Bb → bB
Bc → bcc
5. Obtenha grama´ticas para as linguagens da questa˜o 1.
6. Construa autoˆmatos finitos determin´ısticos (AFDs) que reconhec¸am as linguagens da
questa˜o 3. Apresente apenas os diagramas de estados.
7. Construa AFDs que reconhec¸am as linguagens a seguir. Apresente apenas os diagramas
de estados.
(a) {w ∈ {0, 1}∗ | |w| ≥ 2 e o primeiro e o penu´ltimo s´ımbolos de w sa˜o 1}.
(b) {w ∈ {0, 1}∗ | o u´ltimo s´ımbolo de w e´ diferente do primeiro}.
(c) {w ∈ {0, 1}∗ | os treˆs u´ltimos s´ımbolos de w na˜o sa˜o 000}.
(d) {x10n |n ≥ 0, x ∈ {0, 1}∗ e x tem nu´mero par de 0s}.
8. Fac¸a AFDs que reconhec¸am: X = {0}{0, 1}∗. e Y = {0, 1}∗{1}. Bastam apenas os
diagramas de estados. Em seguida, obtenha o produto dos dois AFDs e explicite que
estados finais ele deve ter para reconhecer:
(a) X ∩ Y .
(b) X ∪ Y .
(c) X − Y .
9. Explique porque se um AFD M reconhece uma palavra de tamanho maior ou igual ao
nu´mero de estados de M , enta˜o L(M) e´ infinita.
10. Construa AFNs para as seguintes linguagens, com o menor nu´mero de estados e de
transic¸o˜es que conseguir:
2
(a) O conjunto das palavras de {a, b, c}∗, de dois ou mais s´ımbolos, em que o u´ltimo
s´ımbolo seja diferente do primeiro.
(b) O conjunto das palavras de {a, b, c}∗ em que o u´ltimo s´ımbolo tenha ocorrido antes
no mı´nimo uma vez.
(c) O conjunto das palavras de {a, b, c}∗ em que o u´ltimo s´ımbolo tenha ocorrido antes
no ma´ximo duas vezes.
11. Seja o AFN com o diagrama de estados a seguir:
1 2
3 4
0
0
0
1
1
1
0 0
Construa um AFD equivalente usando o me´todo visto em aula (subset construction).
12. Seja o AFNλ M :
A B
C D E
λ
λλ
λ λ
a
b
c
d a
13. Construa um AFN N , equivalente a M , usando o me´todo visto em aula.
14. Encontre o AFD mı´nimo usando o me´todo visto em aula para os seguintes AFDs:
a)
0 1
1
0
0 1
b)
0 1
1
0
0 1
c)
0 1
2
1
0
0
1
1
0
3
15. Seja o AFD com o diagrama de estados a seguir:
1
2
3 5
4 6
7
8
0
0 1
1
0
0
1
0
1
0
1
0
1 0
1
1
(a) Descreva a linguagem reconhecida por este AFD.
(b) Minimize-o usando o me´todo visto em aula.
4