Autômatos e Computabilidade - Exercícios Resolvidos sobre AFD, AFN e Linguagens Regulares

Prévia do material em texto

Linguagens regulares
1. Para cada uma das seguintes linguagens, construa um AFD que a reconhec¸a. Fornec¸a o diagrama de
estados do autoˆmato e tambe´m sua descric¸a˜o formal. Considere o alfabeto {0, 1}.
(a) {w|w na˜o conte´m a subcadeia 110}
(b) {w|w conte´m uma quantidade ı´mpar de 1s ou exatamente dois 0s}
(c) {w| o comprimento de w e´ pelos menos 3 e o terceiro s´ımbolo e´ um 0}
(d) {w| w conte´m um 0 em cada posic¸a˜o ı´mpar}
2. Seja um AFNs N = (Q,Σ, δ, q0, F ) com 10 estados (|Q| = 10), alfabeto de 5 s´ımbolos (|Σ| = 5) e 3 estados
de aceitac¸a˜o (|F | = 3). Qua´ntos elementos possui o domı´nio da func¸a˜o δ?
3. Para cada uma das seguintes linguagens, construa um AFN que a reconhec¸a. Fornec¸a o diagrama de
estados do autoˆmtao e tambe´m sua descric¸a˜o formal. Considere o alfabeto {0, 1}.
(a) L1 = {w|w termina com 10}
(b) L3 = {w|w conte´m pelo menos dois 1s e no ma´ximo dois 0s}
(c) L4 = {w| o comprimento de w e´ divis´ıvel por 3 ou w comec¸a com 0}
(d) L5 = L, onde L = {w| w tem comprimento 2 e termina com 0}
4. Para cada uma das seguintes linguagens, construa o diagrama de estados de um autoˆmato finito (deter-
min´ıstico ou na˜o) que a reconhec¸a. Fornec¸a o diagrama de estados do autoˆmato e tambe´m sua descric¸a˜o
formal. Considere o alfabeto {a, b}.
(a) {w| cada ocorreˆncia da subcadeia aa (se existe) em w e´ imediatamente seguida pela subcadeia bb}.
(b) {w| a quantidade de as em w e´ mu´ltiplo de 3 ou w na˜o conte´m a subcadeia bb}.
(c) {w| o penu´ltimo s´ımbolo de w na˜o e´ a}. Atenc¸a˜o: as cadeias ε, a e b pertencem a L.
(d) {w| a quantidade de as em w e´ par ou w na˜o conte´m a subcadeia bab}.
5. Verdadeiro ou falso?
(a) Se um AFD M tem k estados, enta˜o M deve aceitar alguma cadeia de comprimento pelo menos k−1.
(b) Se um AFN M aceita a cadeia vazia (ε), enta˜o o estado inicial de M necessariamente deve ser um
estado de aceitac¸a˜o.
(c) Para cada AFN com n estados, existe um AFD com um ma´ximo de 2n estados que reconhece a mesma
linguagem que o AFN.
(d) Se N = (Q,Σ, δ, q0, F ) e´ um AFN e F = Q enta˜o L(N) = Σ
∗.
6. Transforme os seguintes AFNs em AFDs equivalentes. Considere o alfabeto Σ = {a,b}.
(a)
1 2
3 4
5
ε,a
b ε,b
b
ε
a
a
ε,b
(b)
1 2
3 4
5
a
b
ε,b
b
ε,b
a
ε
a
7. 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.
1
8. Considere o seguinte AFN sobre o alfabeto Σ = {a,b}.
q0 q1 q2
a,b
a b
a
a
b
(a) Transforme o AFN em um AFD equivalente.
(b) Transforme o AFN em um AFNG equivalente.
(c) A partir do AFNG, obtenha uma expressa˜o regular para a linguagem reconhecida pelo autoˆmato.
9. Prove que as seguintes linguagens sa˜o regulares.
(a) L1 = {w|w = w1w2, onde w1,w2 ∈ L e w tem pelo menos dois a’s}, onde L e´ uma linguagem regular.
(b) L2 = {xyzy|x, y, z ∈ {0, 1}
+}.
10. Utilize o lema do bombeamento para provar que as seguintes linguagens na˜o sa˜o regulares.
(a) L1 = {a
ibjak| k > i+ j}
(b) L2 = {c
ibjai+j | i,j > 0}
(c) L3 = {a
ibjck| i, j, k ≥ 0 e i2 + j2 = k2}
(d) L4 = {w#xwy|x, y, w ∈ {a, b}
∗}
11. 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.
12. Seja a seguinte linguagem
TRIPLES = {a3n|n ≥ 0}
(a) Fornec¸a uma expressa˜o regular para TRIPLES
(b) 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?
13. Considere a linguagem regular L3 = L(R), onde R = 000(11)
∗1. Qual e´ o valor mı´nimo de seu compri-
mento de bombeamento? Justifique sua resposta.
14. Seja A uma linguagem finita, e n o comprimento ma´ximo das cadeias de A (i.e., |w| ≤ n para todo w ∈ A).
Prove que todo AFD que reconhec¸e A tem pelo menos n+ 1 estados. Dica: lembre de como foi escolhido
o comprimento de bombeamento na prova do Lema do Bombeamento.
15. Verdadeiro ou falso?
(a) Se o complemento de L e´ finito enta˜o L e´ regular.
(b) A unia˜o de infinitas linguagens regulares e´ regular.
(c) O conjunto de todas as linguagens regulares sobre o alfabeto Σ = {a} e´ finito.
(d) 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.
(e) Se L = L1 ∪ L2 e L e L1 sa˜o linguagens regulares, enta˜o L2 tambe´m e´ regular.
(f) Se L e´ uma linguagem regular e L′ ⊆ L, enta˜o L′ tambe´m e´ regular.
(g) A classe das linguagens regulares e´ fechada sobre a operac¸a˜o Impar(L) = {w|w ∈ L e |w| e´ impar}.
(h) Se a linguagem L e´ regular, enta˜o a linguagem L′ = {xy|x ∈ L e y /∈ L} tambe´m e´ regular.
(i) b∗a∗ ∩ a∗b∗ = a∗ ∪ b∗
(j) L ◦ LR = {wwR|w ∈ L}, onde L e´ uma linguagem qualquer.
2
Respostas
1. (a)
q0 q1 q2 q3
1
1 0
0 1 1,0
0
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1, q2} e δ : Q × Σ → Q e´
definida pela tabela
0 1
q0 q0 q1
q1 q0 q2
q2 q3 q2
q3 q3 q3
(b)
q0 q1 q2 q3
q4 q5 q6 q7
0 0 0
0
0 0 0
0
11 11 11 11
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, . . . , q8}, F = {q2, q4, q5, q6, q7} e δ : Q×Σ→
Q e´ definida pela tabela
0 1
q0 q1 q4
q1 q2 q5
q2 q3 q6
q3 q3 q7
q4 q5 q0
q5 q6 q1
q6 q7 q2
q7 q7 q3
(c)
q0 q1 q2 q3
q4
0,1 0,1 0 0,1
1
0,1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4}, F = {q3} e δ : Q × Σ → Q e´
definida pela tabela
0 1
q0 q1 q1
q1 q2 q2
q2 q3 q4
q3 q3 q3
q4 q4 q4
3
(d)
q0 q1
q2
0
0,1
1
0,1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2}, F = {q1} e δ : Q × Σ → Q e´ definida
pela tabela
0 1
q0 q1 q2
q1 q0 q0
q2 q2 q2
2. O domı´nio de δ e´ Q× Σε, cuja quantidade de elementos e´ |Q| × |Σε| = 10× (5 + 1) = 60.
3. (a)
q0 q1 q2
1 0
0,1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2}, F = {q2} e δ : Q × Σε → P(Q) e´
definida pela tabela
0 1 ε
q0 {q0} {q0, q1} ∅
q1 {q2} ∅ ∅
q2 ∅ ∅ ∅
(b)
q0 q1 q2
q3 q4 q5
q6 q7 q8
1 1
1
1 1
1
1 1
1
0 0 0
0 0 0
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, . . . , q8}, F = {q2, q5, q8} e δ : Q×Σtextttε →
P(Q) e´ definida pela tabela
0 1 ε
q0 {q3} {q1} ∅
q1 {q4} {q2} ∅
q2 {q5} {q2} ∅
q3 {q6} {q4} ∅
q4 {q7} {q5} ∅
0 1 ε
q5 {q8} {q5} ∅
q6 ∅ {q7} ∅
q7 ∅ {q8} ∅
q8 ∅ {q8} ∅
4
(c)
q0
q1 q2
q3 q4 q5
ε
0
0,1
ε
0, 1 0, 1
0, 1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5}, F = {q2, q3} e δ : Q × Σε →
P(Q) e´ definida pela tabela
0 1 ε
q0 ∅ ∅ {q1, q3}
q1 {q2} ∅ ∅
q2 {q2} {q2} ∅
q3 {q4} {q4} ∅
q4 {q5} {q5} ∅
q5 {q3} {q3} ∅
(d)
q0 q1 q2 q3
0, 1 0 0, 1
0, 1
1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1, q3} e δ : Q×Σε → P(Q)
e´ definida pela tabela
0 1 ε
q0 {q1} {q1} ∅
q1 {q2} {q3} ∅
q2 {q3} {q3} ∅
q3 {q3} {q3} ∅
4.
(a)
q0 q1 q2 q3
b
a
b
a b
b
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1} e δ : Q×Σε → P(Q) e´
definida pela tabela
a b ε
q0 {q1} {q0} ∅
q1 {q2} {q0} ∅q2 ∅ {q3} ∅
q3 ∅ {q0} ∅
5
(b)
q0
q1
q2
q3
ε
b
a
b
a
b
a
q4 q5 q6
ε
a
b
a
b a,b
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5, q6}, F = {q1, q4, q5} e δ :
Q× Σε → P(Q) e´ definida pela tabela
a b ε
q0 ∅ ∅ {q1, q4}
q1 {q2} {q1} ∅
q2 {q3} {q2} ∅
q3 {q1} {q3} ∅
q4 {q4} {q5} ∅
q5 {q4} {q6} ∅
q6 {q6} {q6} ∅
(c)
q0 q1 q2
q3
b
a a
a
b
b
b
a
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1} e δ : Q × Σ → Q e´
definida pela tabela
a b
q0 q1 q0
q1 q2 q3
q2 q2 q3
q3 q0 q0
(d)
q0
q1 q2ε
b
a
a
b
q3 q4 q5 q6
ε
a
b
b
a
a
b a,b
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5, q6}, F = {q1, q3, q4, q5} e
δ : Q× Σε → P(Q) e´ definida pela tabela
6
a b ε
q0 ∅ ∅ {q1, q3}
q1 {q2} {q1} ∅
q2 {q1} {q2} ∅
q3 {q3} {q4} ∅
q4 {q5} {q4} ∅
q5 {q3} {q6} ∅
q6 {q6} {q6} ∅
5. (a) 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) Falso. O seguinte AFN aceita (ε).
q1 q2
ε
(c) Verdadeiro. O me´todo para transformar um AFN em um AFD equivalente, visto em aula, produz um
AFD cujos estados sa˜o subconjuntos do AFN. A quantidade de subconjuntos de estados do AFN e´ 2n.
(d) Falso. Como contraexemplo, considere o AFN N = ({q0}, {0, 1}, δ, q0, {q0}), com δ(q0, a) = ∅ para
a ∈ {0, 1, ε}. Claramente, F = Q; no entanto, a linguagem reconhecida pelo autoˆmato e´ L(N) =
{ε} 6= Σ∗.
6. (a)
{1,2,3,4} {2,3,4,5}
{2,3,4}
a
b
b
a
a
b
(b)
{1} {2,3,4} {2,3,4,5}
a,b
a
b
b
a
7.
0 0,1
1
0,1
0,1
8. (aaa)∗(bbb)∗ ∪ (aaa)∗aab(bbb)∗ ∪ (aaa)∗abb(bbb)∗.
7
9. (a)
{q0}
{q0, q1} {q0, q1, q2}
{q1} {q2}
a
b
a
b
a
b
a
b
a
b
(b)
qi q0 q1 q2 qf
a ∪ bε
a b
a
a
b
ε
(c) Eliminando os estados intermedia´rios q2, q1 e q0, nessa ordem, obtemos
qi q0 q1 qf
a ∪ bε
a b ∪ aa
ab
ε
qi q0 qf
(a ∪ b)(b ∪ aa)∗ε
a ∪ (a ∪ b)(b ∪ aa)∗ab
qi qf
[a ∪ (a ∪ b)(b ∪ aa)∗ab]∗(a ∪ b)(b ∪ aa)∗
Portanto, uma expressa˜o regular que gera a linguagem reconhecida pelo autoˆmato e´
[a ∪ (a ∪ b)(b ∪ aa)∗ab]∗(a ∪ b)(b ∪ aa)∗
10. (a) A linguagem L1 e´ a intersec¸a˜o de duas linguagens, A = {w1w2|w1,w2 ∈ L} e B = {w|w tem
pelo menos dois a’s}. A linguagem A e´ a concatenac¸a˜o da linguagem regular L com L e, portanto,
e´ regular, pois a classe das linguagens regulares e´ fechada sobre a concatenac¸a˜o. A linguagem B
tambe´m e´ regular, pois pode ser descrita pela expressa˜o regular Σ∗aΣ∗aΣ∗, onde Σ e´ o alfabeto de
L. A classe das linguagens regulares tambe´m e´ fechada sobre a intersec¸a˜o e, portanto, L2 = A ∩B e´
regular.
(b) Para qualquer cadeia w ∈ L2, se w termina com 0 enta˜o y termina com 0. Como y esta´ repetido,
enta˜o w tera´ uma outra ocorreˆncia de 0 dentro dela. O mesmo acontece para qualquer cadeia em
L2 que termine com 1, essa cadeia tera´ um outra ocorreˆncia de 1 dentro dela. Assim, qualquer
cadeia em L2 pertence a` linguagem descrita pela expressa˜o regular R = (Σ
+0Σ+0) ∪ (Σ+1Σ+1),
onde Σ = {0, 1}. Tambe´m, qualquer cadeia em L(R) pertence a L2: fazemos y igual ao s´ımbolo
8
repetido (0 ou 1, conforme o caso) e x, z iguais a`s subcadeias correspondentes a`s duas cocorreˆncias
de Σ+, respectivamente. Enta˜o, L2 = L(R) e e´ regular.
11. (a) Suponha que L1 e´ regular, e que p e´ o comprimento de bombeamento. Considere 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 =ap+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.
(b) Suponha que L2 e´ regular, e que p e´ o comprimento de bombeamento. Considere a cadeia s =
cp bpa2p ∈ L2, 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 ∈ L2. No entanto,
xyyz =cn+p bpa2p. Como n + p + p 6= 2p, enta˜o xyyz /∈ L2. A contradic¸a˜o indica que L2 na˜o pode
ser regular.
(c) Suponha que L3 seja regular, e que p seja o comprimento de bombeamento. Considere w = a
3pb4pc5p.
Note que (5p)2 = (3p)2 + (4p)2, portanto w ∈ L3, e |w| ≥ p. Fazemos w = xyz, onde |xy| ≤ p e
|y| > 0. Enta˜o, xy = am, com m ≤ p, e y = an, com 0 < n ≤ m. Segundo o lema do bombeamento,
xz ∈ L3. No entanto, xz = a
3p−nb4pc5p, e (5p)2 6= (3p− n)2 + (4p)2. Enta˜o, xz /∈ L3. A contradic¸a˜o
implica que L3 na˜o e´ regular.
(d) Suponha L4 regular, e seja p seu comprimento de bombeamento. Considere s = a
p#bapb. Claramente,
s ∈ L4, com w = a
p, x = y = b. Tambe´m, |s| ≥ p. Fazemos s = s1s2s3, com |s1s2| ≤ p e |s2| > 0.
Enta˜o, s1s2 = a
k, com k ≤ p, e s2 = a
j , com 0 < j ≤ k. Bombeando para cima, obtemos
s1s2s2s3 = a
p+j#bapb. Verificamos agora se esta cadeia tem a forma exigida na definic¸a˜o de L4. A
subcadeia w e´ aquela que esta´ a` esquerda da ocorreˆncia de #, e enta˜o deve ser w = ap+j . No entanto,
essa subcadeia na˜o aparece a` direita de #. Concluimos que s1s2s2s3 /∈ L4. A contradic¸a˜o implica que
L4 na˜o e´ regular.
12. 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.
13. (a) (aaa)∗.
(b) A prova na˜o considera todas as poss´ıveis subdiviso˜es da cadeia de teste.
14. Toda cadeia de L3 conte´m treˆs 0s seguidos de uma quantidade ı´mpar de 1s. A menor cadeia e´ 0001, que
na˜o pode ser bombeada para baixo (na˜o podemos diminuir a quantidade de s´ımbolos). Qualquer outra
cadeia pode ser bombeada, fazendo x = 000, y igual a` primeira ocorreˆncia da subcadeia 11, e z igual ao
resto da cadeia. O comprimento mı´nimo de bombeamento e´, portanto, p = 5.
15. Conforme visto na demostrac¸a˜o do Lema do Bombeamento, se um AFD tem p estados, enta˜o p e´ um
comprimento de bombeamento para a linguagem do autoˆmato e as cadeias da linguagem que possuem
comprimento maior ou igual a p podem ser bombeadas. Se bombeamos uma cadeia “para cima”, obtemos
outras infinitas cadeias da linguagem, de comprimento maior que a cadeia original. Suponha, assim, que
um AFD que reconhece A tem uma quantidade de estados p ≤ n. Enta˜o, existe pelos menos uma cadeia
w ∈ A, de comprimento maior ou igual a p, que pode ser bombeada. Bombeando “para cima” essa cadeia
obtemos infinitas outras cadeias de A de comprimento maior que n. No entanto, isso contradiz a afirmac¸a˜o
inicial de que A e´ finita e de que n e´ o comprimento ma´ximo de suas cadeias. Portanto, nenhum AFD que
reconhec¸a A pode ter uma quantidade de estados p ≤ n.
16. (a) Verdadeiro. Se L′ = L e´ uma linguagem finita, enta˜o e´ regular. A classe das linguagens regulares e´
fechada sobre a complementac¸a˜o, portanto L′ = L tambe´m e´ regular.
(b) Falso. Como contraexemplo, considere a linguagem na˜o-regular L = {0n1n|n ≥ 0}. Esta linguagem
e´ a unia˜o de infinitas linguagens Li = {0
i1i}, com i = 0, 1, 2, . . . Cada Li e´ uma linguagem finita
(conte´m uma u´nica cadeia) e, portanto, regular.
(c) Falso. Os conjuntos {a}, {aa}, {aaa},...sa˜o linguagens regulares, e o conjunto delas, {{a}, {aa},
{aaa},. . . } e´ infinito.
(d) Verdadeiro. O conjunto de todas essas palavras e´ finito, e todo conjunto finito e´ uma linguagem
regular. Cada uma das palavras constitui uma linguagem 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
linguagens tambe´m e´ regular, pois a classe das linguagens regulares e´ fechada sobre essa operac¸a˜o.
(e) Falso. Se L1 e´ a linguagemregular Σ
∗ e L2 e´ qualquer linguagem na˜o regular sobre Σ, enta˜o
L = L1 ∪ L2 = Σ
∗, que e´ regular.
(f) Falso. Por exemplo, suponha que L e´ a linguagem regular Σ∗, e L′ e´ qualquer linguagem na˜o regular
sobre Σ. Enta˜o, L′ ⊆ L.
(g) Verdadeiro. A linguagem L′ = {w| |w| e´ impar} e´ regular, pois pode ser descrita pela expressa˜o
9
regular Σ(ΣΣ)∗, onde Σ e´ o alfabeto. A linguagem Impar(L) e´ a intersec¸a˜o das linguagens L e L′.
Sabemos que a classe das linguagens regulares e´ fechada sobre a intersec¸a˜o, portanto, L e´ regular.
(h) Verdadeiro. Note que L′ = L ◦ L, e que a classe das linguagens regulares e´ fechada sobre a concate-
nac¸a˜o e a complementac¸a˜o.
(i) Verdadeiro. Note que ambn = bpaq, onde m,n, p, q sa˜o inteiros positivos, se e somente se m = q e
n = p = 0, ou m = q = 0 e n = p.
(j) Falso. Como contraexemplo, considere L = {ab, aab}. Enta˜o, L◦LR = {abba, abbaa, aabba, aabbaa}
e {wwR|w ∈ L} = {abba, aabbaa}.
10