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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 1
1. Indique se cada uma das seguintes afirmac¸o˜es e´ verdadeira ou falsa, e justifique sua resposta.
Atenc¸a˜o: respostas corretas sem uma justificativa adequada na˜o recebera˜o pontos. Na˜o e´
necessa´rio fazer provas formais.
(a) Se um AFD M tem k estados, enta˜o M deve aceitar alguma cadeia de comprimento
pelo menos k − 1.
Resposta: Falso. O conjunto de estados de aceitac¸a˜o de um autoˆmato pode ser
vazio, em cujo caso o autoˆmato na˜o aceita nenhuma cadeia.
(b) O conjunto de todas as linguagens regulares sobre o alfabeto Σ = {a} e´ finito.
Resposta: Falso. Os conjuntos {a}, {aa}, {aaa},...sa˜o linguagens regulares, e o
conjunto delas, {{a},{aa},{aaa,. . . } e´ infinito.
(c) A linguagem gerada pela expressa˜o regular ∅∗a∗ e´ vazia.
Resposta: Falso. ∅∗ = {ε}; portanto, ∅∗a∗ =a∗.
(d) Se L = L1 ∪ L2 e L e L1 sa˜o linguagens regulares, enta˜o L2 tambe´m e´ regular.
Resposta: Falso. Se L1 e´ a linguagem regular Σ
∗ e L2 e´ qualquer linguagem na˜o
regular sobre Σ, enta˜o L = L1 ∪ L2 = Σ
∗, que e´ regular.
(e) Se L e´ uma linguagem regular sobre um alfabeto Σ, enta˜o L′ = {aw|w ∈ L}, onde
a ∈ Σ, tambe´m e´ regular.
Resposta: Verdadeiro. Considere a linguagem regular L′′ = {a}. Enta˜o,
L′ = L′′ ◦ L, que e´ regular, pois a classe das linguagens regulares e´ fechada sobre a
concatenac¸a˜o.
(f) O conjunto de todas as palavras que esta˜o em todos os livros da Biblioteca Central
da UnB, nas quais a quantidade de vogais e´ a mesma que a de consoantes, e´ uma
linguagem regular.
Resposta: Verdadeiro. O conjunto de todas essas palavras e´ finito, e todo con-
junto finito e´ uma linguagem regular. Cada uma das palavras constitui uma lin-
guagem regular com uma u´nica cadeia, pois podemos construir um AFD que aceite
unicamente essa cadeia e rejeite qualquer outra. A unia˜o de todas essas lingua-
gens tambe´m e´ regular, pois a classe das linguagens regulares e´ fechada sobre essa
operac¸a˜o.
(g) Se um AFN M aceita a cadeia vazia (ε), enta˜o o estado inicial de M necessariamente
deve ser um estado de aceitac¸a˜o.
Resposta: Falso. O seguinte AFN aceita (ε).
q1 q2
ε
(h) Toda linguagem finita e´ regular.
Resposta: Verdadeiro. Cada uma das cadeias da linguagem constitui uma lin-
guagem regular com uma u´nica cadeia, pois podemos construir um AFD que aceite
unicamente essa cadeia e rejeite qualquer outra. A unia˜o de todas essas lingua-
gens tambe´m e´ regular, pois a classe das linguagens regulares e´ fechada sobre essa
operac¸a˜o.
(i) Para cada linguagem regular L, e´ poss´ıvel construir um AFN que reconhec¸a L e que
tenha um u´nico estado de aceitac¸a˜o.
Resposta: Verdadeiro. Se L e´ regular, e´ reconhecida por algum AFD, que pode
ser transformado em um AFN M1. Para ter um u´nico estado de aceitac¸a˜o, cons-
tru´ımos um novo AFN M , equivalente ao anterior, adicionando setas ε dos estados
de aceitac¸a˜o de M1 a um novo estado de aceitac¸a˜o u´nico, como mostra o seguinte
diagrama.
M1
ε
ε
M
(j) A linguagem gerada pela expressa˜o regular ∅a∗(a ∪ b) e´ vazia.
Resposta: Verdadeiro. Concatenar ∅ a qualquer linguagem produz a linguagem
vazia.
(k) Se L e´ uma linguagem regular e L′ ⊆ L, enta˜o L′ tambe´m e´ regular.
Resposta: Falso. Por exemplo, suponha que L e´ a linguagem regular Σ∗, e L′ e´
qualquer linguagem na˜o regular sobre Σ. Enta˜o, L′ ⊆ L.
(l) Para cada AFN com n estados, existe um AFD com um ma´ximo de 2n estados que
reconhece a mesma linguagem que o AFN.
Resposta: Verdadeiro. O me´todo para transformar um AFN em um AFD equi-
valente, visto em aula, produz um AFD cujos estados sa˜o subconjuntos do AFN. A
quantidade de subconjuntos de estados do AFN e´ 2n.
2. Considere o seguinte AFN sobre o alfabeto Σ = {a,b}.
1 2
3 4
5
ε,a
b ε,b
b
ε
a
a
ε,b
(a) Transforme o AFN em um AFD que reconhec¸a a mesma linguagem. Nomeie cada estado
do AFD apropriadamente para indicar a quais estados do AFN corresponde. Atenc¸a˜o:
Na˜o e´ necessa´rio mostrar os estados inalcanc¸a´veis desde o estado inicial.
Resposta:
{1,2,3,4} {2,3,4,5}
{2,3,4}
a
b
b
a
a
b
(b) Qual a linguagem reconhecida pelo AFD? Fornec¸a uma expressa˜o regular simples.
Resposta: O AFD reconhece a linguagem (a ∪ b)∗. Note que todos os estados sa˜o
estados de aceitac¸a˜o.
3. Considere o seguinte AFN sobre o alfabeto Σ = {a,b}.
1 2
3 4
5
a
b
ε,b
b
ε,b
a
ε
a
(a) Transforme o AFN em um AFD que reconhec¸a a mesma linguagem. Nomeie cada estado
do AFD apropriadamente para indicar a quais estados do AFN corresponde. Atenc¸a˜o:
Na˜o e´ necessa´rio mostrar os estados inalcanc¸a´veis desde o estado inicial.
Resposta:
{1} {2,3,4} {2,3,4,5}
a,b
a
b
b
a
(b) Qual a linguagem reconhecida pelo AFD? Fornec¸a uma expressa˜o regular simples.
Resposta: O AFD reconhece a linguagem (a ∪ b)(a ∪ b)∗. Note que aceita qualquer
cadeia, exceto a cadeia vazia.
4. Seja um AFN M que reconhece a linguagem L sobre o alfabeto {a,b}. Construa um novo
AFN que reconhece a linguagem L′ = {xwx|w ∈ L, x ∈ Σ}. Por exemplo, se aab ∈ L, enta˜o
aaaba ∈ L′ e baabb ∈ L′.
Resposta: Verdadeiro. A partir do AFN M , constru´ımos o novo AFN, M ′, como
mostra o seguinte diagrama.
M
b
b
a
a
a
b
M ′
5. Escreva uma expressa˜o regular para a linguagem L que conte´m todas as cadeias em a∗b∗
cujo comprimento e´ um mu´ltiplo de 3. Por exemplo, L conte´m aaaabb, mas na˜o conte´m
ababab ou aaabb.
Resposta: (aaa)∗(bbb)∗ ∪ (aaa)∗aab(bbb)∗ ∪ (aaa)∗abb(bbb)∗.
6. Utilize o lema do bombeamento para provar que a linguagem L1 = {a
ibjak| k > i+ j} na˜o
e´ regular.
Resposta: Suponha que L1 e´ regular, e que p e´ o comprimento de bombeamento. Con-
sidere a cadeia s =ap bap+2 ∈ L1, cujo comprimento e´ |s| > p. Fazemos s = xyz, onde
|xy| ≤ p e |y| > 0. Enta˜o, y deve conter somente as; assim, y =an, onde 0 < n ≤ p0.
Segundo o lema, xyyz ∈ L1. No entanto, xyyz =a
p+n bap+2. Como p+2 na˜o e´ maior que
p+ n+ 1, enta˜o xyyz /∈ L1. A contradic¸a˜o indica que L1 na˜o pode ser regular.
7. Utilize o lema do bombeamento para provar que a linguagem L1 = {c
ibjai+j| i,j > 0} na˜o
e´ regular.
Resposta: Suponha que L1 e´ regular, e que p e´ o comprimento de bombeamento. Con-
sidere a cadeia s =cp bpa2p ∈ L1, cujo comprimento e´ |s| > p. Fazemos s = xyz, onde
|xy| ≤ p e |y| > 0. Enta˜o, y deve conter somente cs; assim, y =cn, onde 0 < n ≤ p.
Segundo o lema, xyyz ∈ L1. No entanto, xyyz =c
n+p bpa2p. Como n+ p+ p 6= 2p, enta˜o
xyyz /∈ L1. A contradic¸a˜o indica que L1 na˜o pode ser regular.