Notas de Aula 06 - Teoria da Computação VI

Prévia do material em texto

TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 29 
 
 
IV.4 TEOREMA DE KLEENE 
O principal objetivo para o estudo de expressões regulares e linguagens regulares é definido pelo 
Teorema de Kleene, enunciado abaixo. 
 
Denotamos por L(M) como a linguagem reconhecida pelo autômato finito M. O Teorema de 
Kleene afirma que: 
• Dado um autômato finito M, o conjunto L(M) é uma linguagem regular. Podemos então 
caracterizá–la formalmente, através de sua expressão regular; 
• Toda linguagem regular R admite um autômato finito que a reconheça; ou seja, existe um 
autômato finito M talque L(M) = R. 
Uma consequência imediata do Teorema de Kleene é que podemos mostrar que um conjunto de 
sequências C qualquer é uma linguagem regular de duas formas: 
• Através da expressão regular que o caracterize, ou 
• Construir um autômato finito M, e provar que L(M) = C. 
Ou seja, mostrar que M reconhece o conjunto C. 
EXEMPLOS RESOLVIDOS EM SALA: 
Para cada expressão regular R abaixo, construir um AFD que reconheça a linguagem regular L(R): 
a. a* 
 
 
 
 
b. aa* 
 
 
 
c. a*a 
 
 
d. a (a ∨ b)* 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 30 
 
 
e. (aa)* 
a
a,be2
b b
a
e1e0
 
 
f. (a ∨ b) (a ∨ b)* 
 
a,b
a,b
e1e0
 
 
 
g. (a ∨ b) a (a ∨ b)* 
 
 
h. ( (a ∨ b) (a ∨ b) ) * 
 
 
 
 
 
 
i. aa* ∨ bb* 
 
 
j. (a ∨ b)* a (a ∨ b) 
 
 
 
 
 
 
 
 
 
k. a* ∨ b* 
 
 
l. a*b* 
 
 
 
 
 
 
 
 
IV.5 EXERCÍCIOS 
a. Apostila: a partir da pág. 463, exercícios 22, 25–31, 33. 
1) Certo ou Errado. 
a) 010110 ∈ L[ ( 01 ∨ 10)* ] ( ) Certo ( ) Errado 
b) 010110 ∈ L[ 01* ∨ 0*1 ] ( ) Certo ( ) Errado 
c) 010110 ∈ L[ ( 01* ∨ 0*1)* ] ( ) Certo ( ) Errado 
d) 000011 ∈ L[ ( 01)* ∨ 0*1 ] ( ) Certo ( ) Errado 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 31 
 
 
e) 000011 ∈ L[ ( 01* ∨ 0*1)* ] ( ) Certo ( ) Errado 
f) 100001 ∈ L[ 01* ∨ 0*1 ] ( ) Certo ( ) Errado 
g) 100001 ∈ L[ ( 01)* ∨ ( 10)* ] ( ) Certo ( ) Errado 
h) 100001 ∈ L[ ( 01* ∨ 0*1)* ] ( ) Certo ( ) Errado 
i) 000001 ∈ L[ ( 01)* ∨ ( 00)* ] ( ) Certo ( ) Errado 
j) 000001 ∈ L[ ( 01 ∨ 00)* ] ( ) Certo ( ) Errado 
k) (01* ∨ 0*1)* = L[ ( 01 ∨ 10)* ] ( ) Certo ( ) Errado 
l) (01* ∨ 0*1)* = L[ ( 0 ∨ 1)* ] ( ) Certo ( ) Errado 
2) Certo ou errado. 
a) λ ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
b) 000001 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
c) 000011 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
d) 000111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
e) 001111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
f) 011111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
g) 111111 ∈ L[ (0*11)* ] ( ) Certo ( ) Errado 
h) λ ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado 
i) 001111 ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado 
j) 011100 ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado 
k) 111100 ∈ L[ (0*11 0*)* ] ( ) Certo ( ) Errado 
l) λ ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado 
m) 000110 ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado 
n) 011010 ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado 
o) 101010 ∈ L[ 0* 1 (10)* ] ( ) Certo ( ) Errado 
3) Certo ou errado. 
a) 011010 ∈ L[ (011)* ∨ (010)* ] ( ) Certo ( ) Errado 
b) 010010 ∈ L[ (011)* ∨ (010)* ] ( ) Certo ( ) Errado 
c) 011010 ∈ L[ (011 ∨ 010)* ] ( ) Certo ( ) Errado 
d) 010010 ∈ L[ (011 ∨ 010)* ] ( ) Certo ( ) Errado 
e) 011010011 ∈ L[ (011 ∨ 010)* ] ( ) Certo ( ) Errado 
f) 010001 ∈ L[ (00)* ∨ (01)* ] ( ) Certo ( ) Errado 
g) 010001 ∈ L[ ( 0 (1 ∨ 0) )* ] ( ) Certo ( ) Errado 
h) 010001 ∈ L[ ( 0 (1 ∨ 0) (1 ∨ 0) )* ] ( ) Certo ( ) Errado 
i) 010001 ∈ L[ ( 0 (1 ∨ 0) (1 ∨ 0) (1 ∨ 0) )* ] ( ) Certo ( ) Errado 
j) 010001 ∈ L[ (0 ∨ 1)* ] ( ) Certo ( ) Errado 
4) Certo ou errado. 
a) 00110011 ∈ L[ 0* (11)* ] ( ) Certo ( ) Errado 
b) 00110011 ∈ L[ 00 (11)* ] ( ) Certo ( ) Errado 
c) 00110011 ∈ L[ (00)* (11)* ] ( ) Certo ( ) Errado 
d) 00 ∈ L[ (00)* (11)* ] ( ) Certo ( ) Errado 
e) 00 ∈ L[ (11)* (00)* ] ( ) Certo ( ) Errado 
f) 0011 ∈ L[ (00)* (11)* ] ( ) Certo ( ) Errado 
g) 0011 ∈ L[ (11)* (00)* ] ( ) Certo ( ) Errado 
h) 0110 ∈ L[ (0*1)* ] ( ) Certo ( ) Errado 
i) 0110 ∈ L[ ( 0 1*)* ] ( ) Certo ( ) Errado 
j) 0110 ∈ L[ ( 0*1*)* ] ( ) Certo ( ) Errado 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 32 
 
 
5) Enumere as 10 menores sequências pertencentes às linguagens regulares abaixo: 
a) L[ a*b* ] 
b) L[ (ab*)* ] 
c) L[ (a*b)* ] 
d) L[ (aa)* ∨ (bb)* ] 
e) L[ (aa ∨ bb)* ] 
f) L[ a*ba* ] 
g) L[ (aa)* (bb)* ] 
h) L[ a* ba* ] 
i) L[ a b*a ] 
j) L[ a*b ∨ b*a ] 
k) L[ a*b ∨ a b* ] 
l) L[ a*b* ∨ b*a* ] 
 
6) Escreva uma AFD que reconheça cada linguagem regular da questão acima. 
7) Para cada AFD M a seguir, forneça uma descrição do conjunto L(M): 
 a) em português; e b) por uma expressão regular. 
a) 
a,b
e
0
e
1
a,b 
b) 
e
0
a
b
e
1
a
b
 
c) 
e
0
a
a,b
e
1
b
 
d) 
e0
a
b a
e
1
b
 
e) 
e
0
0,1
e
1
e
2
0,1
0,1 
f) 
a
e
1
a
bbb
a
e
0
e
2
 
i) 
e
0
0
e
1
e
2
1
0,1
0,1
e
1
1 0
 
j) 
e0
0
0,1
1
e3
0,10,1
e
1
e
2
 
k) 
e
0
a
a
b
e
3
a,bb
e
1
e
2
b
a
 
l) 
0
1
0,1
e1
e
0
00
1
e
2
e
3
1
 
o) 
e
0
1
0,1
e
2
0,1
e
1
0
 
p) 
e
0
1
e
2
0,1
e
1
0,1
0
 
q) 
e0
0,1
e2
0
e1
 0,1
1
 
r) 
e
0
0
1
e
1
e
3 0,1
e
2
0
0,11
 
g) 
e
3
e
1
e
2
0
0
1
0
1
1
0,1
e
0
 
h) 
e
3
e
1
e
2
0
0
1
0
1
1
0,1
e
0
 
m) 
a
b
a
b
b
e
2e1
e
0
a
a
b
e
3
e
4
a
b
 
n) 
e
3
e
1
e2
0
1
1
1
e4
0
0
1
0
0
1
e
0
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 33 
 
 
t) 
e
0
0
1
1
e
1
e
5 0,1
e
2
0
0
e
3
e
4
0
1
0
1
1
 
u) 
0 0
1
0
1
0,1
e0 e1
e
2
e3
1
 
8) Para I = { a, b }, seja S o conjunto de sequências que comecem dois símbolos iguais E terminem 
com dois símbolos iguais, sendo que os dois primeiros são diferentes dos dois últimos. 
a) Escreva as CINCO menores sequências que pertencem a S. 
b) Escreva as SETE menores sequências que NÃO pertencem a S. 
c) Escreva a expressão regular que caracterize S. 
d) Desenhe um autômato finito (MEF) que reconheça o conjunto S. 
9) Para cada expressão regular R abaixo, escreva um ADF que reconheça a linguagem L(R). 
a) aa* 
b) a*ba* 
c) ab*a 
d) ab*a 
e) (a ∨ b)*b 
g) (abb)* 
h) (aa)*b* 
10) Para cada expressão regular R abaixo, escreva um ADF que reconheça a linguagem L(R). 
a) (00)*1 
b) 1(00)* 
c) (01)* 
d) (010)* 
e) (00 ∨ 11)* 
f) (00)* ∨ (11)* 
g) (01)* ∨ (10)* 
h) 00* ∨ 11* 
i) (00)*(11)* 
j) (1 ∨ 00)* 
k) 1* ∨ (00)* 
l) 0 (0 ∨ 1)* 0 
m) (0 ∨ 1) 0 (0 ∨ 1)* 0 (0 ∨ 1) 
11) Escreva uma AFD que reconheça L [ (aa)* b aa (aa)* ] 
12) Escreva uma AFD que reconheça L [ a*b* ∨ b*a* ] 
 
IV.6 GABARITO 
1) 
a) C 
g) E 
b) E 
h) C 
c) C 
i) E 
d) E 
j) C 
e) C 
k) E 
f) E 
l) C 
2) 
a) C 
i) C 
b) E 
j) E 
c) C 
k) C 
d) E 
l) E 
e) C 
m) C 
f) E 
n) C 
g) C 
o) E 
h) C 
5) 
a) a*b* = { λ, a, b, aa, ab, bb, aaa, aab, abb, bbb, aaaa, aaab, aabb, abbb, bbbb, … } 
c) (a*b)* = { λ, b, ab, bb, aab, abb, bab, bbb, aaab, aabb, abab, abbb, baab, babb, bbab, bbbb, … } 
e) (aa ∨ bb)* = { λ, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, aaaabb, aabbaa, aabbbb, bbaaaa, … } 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 34 
 
 
h) a*ba* = { λ, b, ab, ba, aab, aba, baa, aaab, aaba, abaa, baaa, aaaab, aaaba, aabaa, abaaa, … } 
6) h) 
s
0
a
b
a
b
s
2
s
1
a,b 
7) 
a) Sequências de comprimento ímpar ................................................... (a ∨ b) ( (a ∨ b) (a ∨ b) )* 
b) Sequências terminadas com ‘a’ ......................................................... (a ∨ b)* a ou b*a (b*a)* 
c) Sequências que não tenham o símbolo ‘a’ ........................................ b* 
d) Sequências que não terminem com o símbolo ‘a’ ............................ (a*b)* ou λ ∨ (a ∨ b)* b 
e) Sequências com pelo menosdois símbolos. ...................................... (0 ∨1) (0 ∨1) (0 ∨1)* 
f) Sequências em que o n° de ‘a’s é múltiplo de 3 ............................... ( b ∨ a b*ab*a )* 
i) Sequências que comecem com ‘01’ .................................................. 01 (0 ∨1)* 
j) Sequências formadas por apenas um símbolo ................................... 0 ∨1 
k) Sequências não vazias em que o 1° símbolo não se repete mais ...... ab* ∨ ba* 
m) Conjunto vazio: nenhuma sequência é reconhecida. ......................... ∅ 
8) Sendo I = { a, b }, temos S ⊆ I*, e definimos S’ = I* – S. 
a) S = { aabb, bbaa, aaabb, aabbb, bbaaa, bbbaa, aaaabb, aaabbb, aababb, aabbbb, … } 
b) S’ = { λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, abaa, … } 
c) aa (a ∨ b)* bb ∨ bb (a ∨ b)* aa 
d) 
s
0
s
1
a
s
2
a
s
5
b
b
s
3
s
4
b
b
a
a
b
s
6
s
7
s
8
b
a
a
b
a
a
b
s
9
b
a
a,b