Teoria da Computação, Notas de Aula 01 a 06 - Prof Júlio Silveira

Prévia do material em texto

CENTRO UNIVERSITÁRIO CARIOCA 
 
UNICARIOCA 
 
 
 
 
TEORIA 
DA 
COMPUTAÇÃO 
 
 
 
 
NOTAS DE AULA 
 
PROFESSOR: JÚLIO SILVEIRA 
 
 
 
 
VERSÃO: agosto de 2017
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 1 
 
 
I FUNDAMENTAÇÃO TEÓRICA 
I.1 DEFINIÇÕES 
Símbolo: menor unidade de informação a ser manipulada. 
Ex.: a, b, c, 0, 1, S, A, B, … 
OBS: Inicialmente, não consideraremos o caracter espaço em branco ' ' como símbolo válido. 
Alfabeto: conjunto finito e não vazio de símbolos. 
Ex: A = { a, b } B = { a, b, c, …, z } C = { 0, 1 } 
Sequência: (ou cadeia ou palavra) 
Concatenação de uma quantidade finita de símbolos de um dado alfabeto. 
Ex: sequências com símbolos do alfabeto A acima: a, ab, aaab, bbb, ababa, … 
Comprimento de uma sequência 
Número natural que indica a quantidade de (ou ocorrências de) símbolos existentes na sequência. 
NOTAÇÃO: o comprimento de uma sequência qualquer , é denotado por | | 
Ex:  = a  |  | = 1 
 = aaba  |  | = 4 ou também | aaba | = 4 
Sequência vazia:  
A sequência vazia, representada por , não contém nenhum símbolo. 
Desta forma,  tem COMPRIMENTO ZERO, ou seja: |  | = 0 
ATENÇÃO:  não é símbolo! 
Ou seja, não existe o símbolo . Esta letra grega (leia–se lâmbda) é reservada apenas para 
caracterizar a sequência vazia! 
Prefixo, sufixo e subpalavra 
Relações entre palavras. Como exemplo, seja a palavra  = aaba. Então: 
 , a, aa, aab, aaba são prefixos de  
, a, ba, aba, aaba são sufixos de  
, a, b, aa, ab, ba, aab, aba, aaba são subpalavras de . 
Observe que  é um prefixo, sufixo e subpalavra e qualquer palavra.! 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 2 
 
 
Concatenação de sequências 
A concatenação das sequências  e  produz a sequência . Notação:  · , ou simplesmente . 
Desta forma, |  | = |  | + |  | 
Ex: a · b = ab ab · b = abb  · abab = abab ·  = abab 
a · bb = abb abb ·  = abb ab ·  · ab = abab 
ATENÇÃO: No último exemplo acima, NÃO represente o resultado de ab··ab como abab, mas como 
abab. Como já dito, o símbolo  somente é utilizado para denotar a sequência vazia! 
Linguagens – conjuntos de sequências 
Uma linguagem é um conjunto de palavras sobre um alfabeto. Considerando o alfabeto { a, b }, 
temos as seguintes linguagens como exemplos: 
Ex: X = { a, ab, bbba } Y = {  } Z = { } 
W = { , bbbb } 
K = { a, ab, abb, abbb, abbbb, abbbbb,  } 
ATENÇÃO: as sequências pertencentes a um conjunto não precisam ter todas o mesmo comprimento. 
Cardinalidade de um conjunto de sequências (linguagem) 
Uma linguagem (conjunto de sequências) pode ter qualquer nº de elementos. Para os conjuntos 
anteriores, temos: 
Ex.: | X | = 3 | Y | = 1 | Z | = 0 | W | = 2 | K | =  
ATENÇÃO: Observar o contexto na utilização da notação | | 
CARDINALIDADE DE UM CONJUNTO: nº de elementos  | X | = 3 
COMPRIMENTO DE UMA SEQUÊNCIA: nº de símbolos  | bbba | = 4 
ATENÇÃO: Não confundir os conjuntos {  }  { }. Nos exemplos acima, Y  Z 
O conjunto Y acima é um conjunto unitário: seu único elemento é a sequência vazia. 
O conjunto vazio Z acima, também representado por , não tem elementos (sequências). 
Conjunto das sequências formadas por um alfabeto 
Para um dado alfabeto A, define-se o conjunto das sequências formadas por A como o conjunto de 
todas as sequências formadas por concatenações de símbolos de A, de qualquer comprimento. 
Por definição,  pertence ao conjunto das sequências formadas por qualquer alfabeto. 
Ex: Para o alfabeto { 0, 1 }, temos: { , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101,  } 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 3 
 
 
I.2 RELAÇÕES ENVOLVENDO CONJUNTOS DE SEQUÊNCIAS 
As relações  e  também se aplicam a conjuntos de sequências. Veja os exemplos a seguir: 
  { a, ab, bbba } 
  { , ab, bbba } 
a  { a, ab, bbba } 
ab  { a, ab, bbba } 
bb  { a, ab, bbba } 
  { , ab, bbba } 
  { , ab, bbba } 
{  }  { , ab, bbba } 
{ ab }  { , ab, bbba } 
{ bb }  { , ab, bbba } 
{ , ab }  { , ab, bbba } 
{ , ab, bb }  { , ab, aabb, aaabbb,  } 
 
I.3 OPERAÇÕES COM CONJUNTOS DE SEQUÊNCIAS 
União, Interseção, Diferença 
Estas operações usuais são bem definidas para conjuntos quaisquer, inclusive para dois conjuntos de 
sequências A e B: 
 A  B = { w | w  A OU w  B } 
 A  B = { w | w  A E w  B } 
 A – B = { w | w  A E w  B } 
Ex: { a, bbb }  { bb, a } = { a, bb, bbb } 
{ a, bbb }  { bb, a } = { a } 
{ a, bbb } – { bb, a } = { bbb } 
Concatenação 
Tal como com sequências, podemos concatenar dois conjuntos de sequências. A concatenação de 
dois conjuntos de sequências X e Y produz um terceiro conjunto, denotado por XY. 
O conjunto XY contém as sequências formadas pelas concatenações de todas as sequências de X com 
todas as sequências de Y, nesta ordem. 
Definindo formalmente: 
 XY = {  |   X E   Y } 
Isto significa que o conjunto XY é formado por todas as sequências obtidas por uma sequência 
qualquer de X concatenada com uma sequência qualquer de Y. 
Observe que os conjuntos XY e YX normalmente serão diferentes, pois seus elementos são gerados 
na ordem específica, qual seja: sequências   X concatenadas com sequências   Y. 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 4 
 
 
Veja os exemplos a seguir: 
 { a, bbb } { bb, a } = { aa, abb, bbbbb, bbba } 
{ a, bbb } { a, bbb } = { aa, abbb, bbba, bbbbbb } 
{ a } { b, bb, bbb } = { ab, abb, abbb } 
{ , a } { b, bb, bbb } = { b, bb, bbb, ab, abb, abbb } 
Note que podemos ter XY  YX: 
 { a, aa } { b, bb } = { ab, abb, aab, aabb } 
{ b, bb } { a, aa } = { ba, baa, bba, bbaa } 
ATENÇÃO – Observe que, para qualquer conjunto X, temos: 
{  } X = X {  } = X e  X = { } X =   Não existe   ! 
Notação: X
n
 
Se X é um conjunto de sequências (linguagem), definimos X
n
 como a concatenação do conjunto X com 
ele mesmo, n vezes. Por definição, X
0
 = {  }. Como exemplo, se X = { a, bbb }, então: 
X
0
 = {  } 
X
1
 = X = { a, bbb } 
X
2
 = XX = { a, bbb } { a, bbb } = { aa, abbb, bbba, bbbbbb } 
X
3
 = XXX = … = { aaa, aabbb, abbba, abbbbbb, bbbaa, bbbabbb, bbbbbba, bbbbbbbbb } 
e assim por diante. 
Fechamento (ou Fechamento de Kleene, ou estrela de Kleene) 
Formalmente, se X é um conjunto de sequências (linguagem), definimos o fechamento de X como o 
conjunto: 
X* = X
0
  X
1
  X
2
  X
3
  X
4
 … 
Em outras palavras, X* é o conjunto das sequências formadas por todas as concatenações de 
quantidades quaisquer de elementos de X, em qualquer ordem. 
Por quantidade qualquer, entenda-se inclusive ZERO, o que inclui a sequência vazia . 
Ex.: X = { a, bbb } 
X* = { , a, bbb, aa, abbb, bbba, bbbbbb, aaa, aabbb, abbba, bbbaa, abbbbbb, … } 
Observe que, se X for um alfabeto, X* é conjunto de todas as sequências formadas por X. 
Ex.: X = { a, b } 
X* = { , a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, … } 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 5 
 
 
Outros exemplos: 
Se X = { a } e Y = { b } temos: 
 X* = { , a, aa, aaa, aaaa, … } 
 Y* = { , b, bb, bbb, bbbb, … } 
Expressões contendo vários operadores (operações): 
Para os mesmos conjuntos X = { a } e Y = { b }, observe os exemplos a seguir. 
 X* = { , a, aa, aaa, aaaa, … } 
Y* = { , b, bb, bbb, bbbb, … } 
X*  Y* = { , a, b, aa, bb, aaa, bbb, aaaa, bbbb, aaaaa, … } 
X*  Y* = {  } 
X* – Y* = resolva! 
ATENÇÃO: Novamente não confundir os conjuntos {  } e { } 
{ , aa }  { , bb } = {  } 
{ a, aa }  { b, bb } = { } =  
Outros exemplos: 
X Y = { a } { b } = { ab } 
X Y* = { a} { , b, bb, bbb, bbbb, … } = { a, ab, abb, abbb, abbbb, … } 
Y* X = { , b, bb, bbb, bbbb, … } { a } = { a, ba, bba, bbba, bbbba, … } 
X* Y = { , a, aa, aaa, aaaa, … } { b } = { b, ab, aab, aaab, aaaab, … } 
Y X* = resolva! 
X* Y* = resolva! 
( X Y )* = resolva! 
I.4 EXERCÍCIOS 
Sejam os seguintes conjuntos: 
A = { a, b } 
B = { a } 
C = { b } 
D = { aa } 
E = { bb } 
F = { aa, bb } 
G = { aab } 
H = {  } 
I =  
J = { 0 } 
K = { 0, 110 } 
L = { , 0 } 
1) Caracterize, por enumeração, os conjuntos a seguir (enumere alguns dos seus elementos). 
a) A* = 
b) B* = 
c) D* = 
d) F* = 
e) G* = 
f) H* = 
g) I* = 
h) K* = 
i) L* = 
j) B*  C* = 
k) B*  C* = 
l) A*  B* = 
m) D*  E* = 
n) D*  E* = 
o) B* – C* = 
p) A2 = 
q) AB = 
r) BA = 
s) B2 = 
t) AD = 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 6 
 
 
u) DE = 
v) HG = 
w) B E* = 
x) D* E* = 
y) H B* = 
z) I B* = 
2) Verdadeiro ou Falso 
a) a  A* V ( ) F ( ) 
b) a  B* V ( ) F ( ) 
c) a  D* V ( ) F ( ) 
d) aa  D*  E* V ( ) F ( ) 
e) aa  F* V ( ) F ( ) 
f) aabb  D* V ( ) F ( ) 
g) aabb  D*  E* V ( ) F ( ) 
h) aabb  F* V ( ) F ( ) 
i) bbaa  F* V ( ) F ( ) 
j) A* = B*  C* V ( ) F ( ) 
k) F* = D*  E* V ( ) F ( ) 
l) B*  A* V ( ) F ( ) 
m) B*  D* V ( ) F ( ) 
n) D*  B* V ( ) F ( ) 
o) D*  F* V ( ) F ( ) 
p) F* = { bb, aa }* V ( ) F ( ) 
q) J* = L* V ( ) F ( ) 
r) H = H* V ( ) F ( ) 
s) I = I* V ( ) F ( ) 
t) H* = I* V ( ) F ( ) 
3) Verdadeiro ou Falso, justificando sua resposta. Observe os exemplos abaixo. 
a) { ab }*  { abab }* FALSO 
Justificativa: 
Observemos que ababab  { ab }*, mas ababab  { abab }*. 
Ou seja, a sequência ababab é um elemento de { ab }* que não pertence a { abab }*. 
Desta forma, { ab }*  { abab }*. 
b) ababaab  { a, ab }* VERDADEIRO 
Justificativa: 
O conjunto { a, ab } tem dois elementos: a e ab. O fechamento deste conjunto certamente inclui a 
sequência formada por concatenações destes dois elementos na seguinte ordem: ab·ab·a·ab. 
c) aabbaa  { aa, bb }* 
d) aabbbaa  { aa, bb }* 
e) aabbbaa  { aa, b }* 
f) abbba  { aa, b }* 
g) abbba  { ab, ba }* 
4) Enumere as sequências pertencentes aos conjuntos abaixo, de acordo com as especificações: 
a) { b, ab, aba }*  Todas as sequências de comprimento QUATRO 
Resposta: bbbb, abab, bbab, babb, abbb, baba, abab 
b) { ab, aba }*  Todas as sequências de comprimento SETE 
Resposta: abababa, ababaab, abaabab 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 7 
 
 
c) { b, ab, aba }*  Todas as sequências de comprimento menor ou igual a QUATRO 
Resposta: 
d) { b, ab, bbb }*  Todas as sequências de comprimento TRÊS ou QUATRO 
Resposta: 
e) { a, bbb }*  Todas as sequências de comprimento SETE 
Resposta: 
f) { a, bbb }*  Todas as sequências de comprimento menor que SEIS e ÍMPAR 
Resposta: 
g) { a, bbb }*  Todas as sequências de comprimento menor que SEIS e PAR 
Resposta: 
h) { aa, bbb }*  Todas as sequências de comprimento menor que SEIS e ÍMPAR 
Resposta: 
i) { a, bb }*  Todas as sequências de comprimento SEIS 
Resposta: 
I.5 GABARITO DE ALGUNS EXERCÍCIOS 
1) 
a) A* = { , a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, … } 
b) B* = { , a, aa, aaa, aaaa, … } 
c) D* = { , aa, aaaa, aaaaaa, … } 
d) F* = { , aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, aaaabb, aabbaa, aabbbb, bbaaaa, … } 
e) G* = { , aab, aabaab, aabaabaab, … } 
f) H* = {  } 
g) I* = {  } 
h) K* = { , 0, 00, 000, 110, 0000 , 0110, 1100, 00000, 00110, 01100, 11000, … } 
i) L* = J* = { , 0, 00, 000, 00000, 000000, … } 
j) B*  C* = { , a, b, aa, bb, aaa, bbb, aaaa, bbbb, … } 
k) B*  C* = {  } 
l) A*  B* = A* (veja acima) 
m) D*  E* = { , aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, … } 
n) D*  E* = {  } 
o) B* – C* = { a, aa, aaa, aaaa, … } 
p) A2 = AA = { aa, ab, ba, bb } 
q) AB = 
r) BA = { aa, ab } 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 8 
 
 
s) B2 = BB = 
t) AD = { aaa, baa } 
u) DE = { aabb } 
v) HG = 
w) B E* = { a } { , bb, bbbb, bbbbbb, … } = continue! 
x) D*E* = { , aa, aaaa, aaaaaa, … } { , bb, bbbb, bbbbbb, … } 
 = { , aa, bb, aaaa, aabb, bbbb, aaaaaa, aaaabb, aabbbb, bbbbbb, aaaaaaaa, … } 
y) H B* = B* = { , a, aa, aaa, aaaa, … } 
z) I B* = 
2) 
a) V 
b) V 
c) F 
d) V 
e) V 
f) F 
g) F 
h) V 
i) V 
j) F 
k) F 
l) V 
m) F 
n) V 
o) V 
p) V 
q) V 
r) V 
s) F 
t) V 
 
 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 9 
 
 
II AFD – AUTÔMATO FINITO (MÁQUINA DE ESTADO) DETERMINÍSTICO 
O conceito de autômato finito (ou máquina de estado finito) consiste na idealização de uma 
máquina abstrata, que durante todo o seu funcionamento, passa por várias “configurações” ou estados. 
Em cada instante, a máquina somente pode se encontrar em um destes estados, responsável por gerar 
alguma saída ao mundo exterior. 
Durante o seu processamento, o autômato finito lê uma entrada do mundo exterior, e esta 
entrada irá determinar o próximo estado da máquina, sempre dependendo do estado atual em que ela 
se encontra. Ou seja, uma determinada entrada pode fazer a máquina se comportar de uma forma 
específica por um dado estado, ou de uma forma distinta, se a máquina se encontra em outro de seus 
estados. 
Em um autômato finito determinístico, o número de estados é sempre finito, e que todas as 
entradas ou saídas serão símbolos. Os símbolos lidos durante o processamento formam a sequência 
de entrada lida pela máquina. Ao processar esta sequência, a máquina irá gerar uma sequência de 
saída, formada pela concatenação dos símbolos gerados por cada estado percorrido em cada instante 
do tempo. 
II.1 DEFINIÇÃO: AFD DE PROCESSAMENTO (AUTÔMATO FINITO DETERMINÍSTICO) – apostila, pág. 443 
 
Resumindo, um AFD M = [E, I, O, fE, fO], com: 
E conjunto finito de estados; 
I alfabeto de entrada; 
O alfabeto de saída; 
fO função saída, sendo: 
fO : E  O 
fE função próximo estado (ou função de transição de estados), sendo: 
fE : E  I  E 
CONVENÇÃO: E = { e0 , e1 , e2 , … , ek } Neste caso, E contém k+1 estados. 
e0 : estado inicial. 
EXEMPLO: (Exemplo 16 da apostila, pág 444) 
E = { e0 , e1 , e2 } 
I = { 0, 1 } 
O = { 0, 1 } 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 10 
 
 
Vejamos como caracterizar as funções fO e fE para o AFD deste exemplo: 
fO : E  O 
e
0
e
1
e
2
0
1
 
fE : E  I  E 
e
0
(e
0
,0)
(e
0
,1)
(e
1
,0)
(e
1
,1)
(e
2
,0)
(e
2
,1)
e
1
e
2
 
No exemplo 16: a sequência de entrada 01101 produz a sequência de saída 011110. 
 
 
Para o mesmo ADF, qual a sequência produzida pela entrada 1100011011? R.: 
Tempo t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 
Entrada 1 1 0 0 0 1 1 0 1 1 - 
Estado e0 
Saída 
II.2 GRAFO DE ESTADO: outra representação para o ADF do exemplo 16 (pág. 444): 
 ATENÇÃO: 
in
est / out
 
Símbolo de saída: indicado DENTRO do rótulo do nó 
Símbolo de entrada: indicado na SETA (transição) 
Por convenção, duas setas para o mesmo estado são representadas com uma seta com rótulo duplo: 
i1
ei / out
i2
i1 , i2
 est / out
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 11 
 
 
Importante verificar que um Autômato Finito Determinístico: 
 LÊ sequências  contendo símbolos do alfabeto de entrada I, ou seja,   I* 
 GERA sequências  contendo símbolos do alfabeto de saída O, ou seja,   O* 
Máquina de
Estado Finito
 *  *
 
II.3 EXERCÍCIOS(ALGUMAS RESPOSTAS NA SEÇÃO II.4) 
EXERCÍCIOS DA APOSTILA: a partir da pág. 460, do 1) ao 10). 
1) Seja AFD representado pela tabela a seguir, onde I = { 0, 1 } e O = { a, b }. 
Estado Atual Próximo Estado Saída 
 Entrada Atual 
 0 1 
e0 e2 e1 a 
e1 e1 e0 b 
e2 e0 e1 b 
a) Desenhe o seu grafo de estados correspondente: 
b) Calcule a sequência de saída para as sequência de entrada 110010 (lida da esquerda para a direita). 
2) Seja a Máquina de Estado Finito representada pela tabela a seguir, onde I = { a, b, c } e O = { 0, 1 }. 
Est. Atual Próx. Estado Saída 
 Entrada Atual 
 a b c 
e0 e0 e0 e1 0 
e1 e2 e0 e1 0 
e2 e2 e1 e0 1 
a) Desenhe o seu grafo de estados correspondente 
b) Calcule a sequência de saída para as sequências de entrada a seguir, lidas da esquerda para a direita: 
abcabc bacabc bacaaa 
c) Enumere TODAS as sequências de entrada possíveis que produzam as seguintes saídas: 
010001 001010 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 12 
 
 
3) Seja a Máquina de Estado Finito representada pela tabela a seguir. 
Est. Atual Prox. Estado Saída 
 Entrada Atual 
 a b c 
e0 e0 e1 e2 0 
e1 e2 e1 e2 1 
e2 e0 e1 e1 1 
a) Desenhe o seu grafo de estados correspondente. 
b) Calcule a sequência de saída para as sequências de entrada a seguir, lidas da esquerda para a direita: 
aabcaa bbbccc bcabca 
c) Enumere TODAS as sequências de entrada possíveis que produzam as seguintes saídas: 
0101 0110 
4) Seja a Máquina de Estado Finito representada pelo grafo a seguir, onde I = { 0, 1 } e O = { 0, 1 }. 
e
0 
/ 1
0, 1
0
e
2 
/ 1
e
1 
/ 0
1
1
0
 
a) Preencha a tabela de estados correspondente: 
Estado Atual Próximo Estado Saída 
 Entrada Atual 
 0 1 
e0 
e1 
e2 
 
b) Calcule a sequência de saída para as sequências de entrada a seguir, lidas da esquerda para a direita: 
011101 110110 
5) Para o AFD representado pelo grafo a seguir, onde I = { a, b } e O = { 0, 1 }. 
e
0 
/ 0
a, b
a
e
1 
/ 1
e
2 
/ 0
a
b
b
 
a) Preencha a tabela de estados correspondente: 
Estado Atual Próximo Estado Saída 
 Entrada Atual 
 a b 
e0 
e1 
e2 
b) Calcule a sequência de saída para as sequências de entrada a seguir, lidas da esquerda para a direita: 
abbbab bbabba 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 13 
 
 
6) Para o AFD abaixo, onde I = { 0, 1 } e O = { a, b }: 
a) Complete o seu grafo de estados, sabendo que 
a sequência de entrada 111 gera a saída abba. 
b) Enumere TODAS as sequências de entrada que 
geram a saída abbb. 
e
0/
e
1/
e
2/
 
7) Para o AFD abaixo, onde I = { 0, 1 } e O = { a, b }:
a) Complete o seu grafo de estados, sabendo que 
a sequência de entrada 000 gera a saída abba. 
b) Enumere TODAS as sequências de entrada que 
geram a saída abbb. 
e
0 /
e
1 /
e
2 /
 
8) Para o alfabeto de entrada I = { ‘ ’, a, b }, e para o alfabeto de saída O = { ‘ ’, a, b, A, B } construir 
uma máquina de estado finito que leia uma “frase” contendo caracteres de I, e transforme esta frase 
colocando a primeira letra de cada palavra em maiúscula. 
Ex.: ENTRADA: " a aba baba a baba " 
SAÍDA: " A Aba Baba A Baba " 
 
II.4 GABARITO DE ALGUNS EXERCÍCIOS 
APOSTILA: pág. 460, 1.a. e 2.a. 
 
Resposta: 0001111110 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 14 
 
 
 
7º
0 1º Nível1
e0 / 0 e3 / 0 e0 / 0 e4 / 1
e3 / 0e0 / 0
e0 / 0
0 1 0
 2º Nível 
 3º Nível 
1
e1 / 1 e2 / 1 4º Nível 
e0 / 0
0 1
e4 / 1
e2 / 1 e1 / 1
e0 / 0 e4 / 1
e1 / 1 e2 / 1
e1 / 1
e0 / 0 e4 / 1
e2 / 1
e2 / 1 e1 / 1
e2 / 1
e2 / 1 e1 / 1
e1 / 1
e0 / 0 e4 / 1
5º N 
1
1
1
 6º N
0
0
0 0 0 0 01
10
111
1
0
1
0
 
Resposta: sequências 110100 e 111010 
1) a) Grafo de estados b) Processar a sequência de entrada  = 110010 
e0 / a
1
1
e1 / b
e2 / b
00
0
1
 
  = abababb 
 
 
6) a) Grafo de estados b) Entradas cujo processamento gera a saída  = abbb. 
 
e
1/ b
1
1
00
0
e
0/ a
e
2/ b
1
 
0 1
e
2
 / b
e
1
 / be
0
 / a
e
0
 / a
0 1
e
2
 / b
0 1
e
1
 / b
e
1
 / b
0
e
1
 / 1
1
e
0
 / a
 
Resposta: sequências 100, 101 e 110 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 15 
 
 
III AFD DE RECONHECIMENTO 
Além dos AFD’s de processamento, vistos na anterior, autômatos finitos também podem ser 
definidos para atuarem como “reconhecedores”. 
A definição de um AFD de reconhecimento não contém um alfabeto de saída, sendo 
especificado apenas o alfabeto de entrada I. Ao ler qualquer sequência   I*, o AFD reconhecedor 
irá reconhecer (ou aceitar) apenas algumas destas sequências, e não reconhecer (não aceitar ou 
rejeitar) outras. 
AFD
RECONHECEDOR
 * ACEITA 
REJEITA 
 
III.1 AFD´S RECONHECEDORES 
Um Autômato Finito Determinístico reconhecedor M terá as seguintes características: 
 Seus estados NÃO GERAM SAÍDA: apenas o alfabeto de entrada I é definido. 
 Seu conjunto de estados E é pode ser particionado em dois conjuntos E = EF  EF’, onde: 
EF : conjunto de ESTADOS FINAIS 
EF’: conjunto de ESTADOS NÃO–FINAIS 
 NOTAÇÃO GRÁFICA: 
 
efinal enão-final
 
 ESTADO FINAL ESTADO NÃO-FINAL 
 No processamento de uma sequência entrada   I*, M pode terminar em um estado: 
FINAL  M RECONHECE ou ACEITA  
NÃO-FINAL  M NÃO RECONHECE, NÃO ACEITA, ou REJEITA  
Exemplo: o AFD a seguir tem cinco estados sendo que e2 e e4 são estados finais. 
e0
1
e3
0
e4
e1
0
1e2
1
0
1
0
0
1
 
Processamento do AFD á esquerda: 
M ACEITA as sequências: 01, 011, 110,  
M REJEITA as sequências: 0, 00, 101,  
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 16 
 
 
III.2 LINGUAGENS RECONHECIDAS POR UM AFD 
Como já visto, um AFD M pode ler qualquer palavra   I*, reconhecendo algumas e 
rejeitando outras. Desta forma, M particiona o conjunto I* em dois subconjuntos: 
I* = S  S’ onde S = linguagem reconhecida por M; 
S’ = conjunto das sequências rejeitadas por M. 
Dizemos então que M reconhece a linguagem S. 
 
Formalmente, definimos a Linguagem reconhecida por M, notada por L(M), como: 
L(M) = {   I* | M reconhece  } 
Exercício: caracterize, EM PORTUGUÊS, as linguagens reconhecidas pelos AFD’s abaixo. 
Apostila I, PROBLEMA PRÁTICO 40, pág. 448 (Fig. 8.6), A SER RESOLVIDO EM AULA: 
 
 
PADRÃO DE RESPOSTAS: 
a. L(M) = { 0 } Resp.: Apenas a sequência 0 
b. L(M) = { 10, 010, 0010, 00010,  } Resp.: Sequências de sufixo 01 que contenham um 
único símbolo 1 
c. L(M) = { 0, 1 } Resp.: Apenas as sequências 0 e 1 
d. L(M) = { , 11, 1111, 111111,  } Resp.: Sequências de comprimento par que não 
contenham o símbolo 0 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 17 
 
 
EXERCÍCIOS RESOLVIDOS EM AULA: Caracterize L(M), em português, para cada AFD abaixo. 
(a) 
a,b
e
0
a,b
e
1
 
L(M): 
Apenas a sequência vazia, ou apenas . 
 
 
(b) 
b a,b
a
e
0
e
1
 
L(M): 
Sequências que não contenham o símbolo 1. 
 
(c) 
b
e
2
e
0
e
1
b a,b
a
a 
L(M): 
Sequências que contenham dois símbolos b’s 
consecutivos. 
 
(d) 
e
3
0
1
0
1
0,1
e
1
e
0
e
2
0
1
 
L(M): 
Sequências que não contenham nenhum símbolo 
sucedido por outro igual. 
 
(e) 
a,b
e
1
a,b
e
0
 
L(M): 
Sequências de comprimento par. 
 
 
(f) 
a
e
0
a,b
b
e
1
 
L(M): 
Conjunto vazio 
(M não reconhece nenhuma sequência) 
 
 
(g) 
b
e
2
e
0
e
1
b a,b
aa
 
L(M): 
Sequências que contenham dois símbolos b. 
 
 
(h) 
e
0
1
e
3
0
e
4
e
1
0
1e
2
1
0
1
0
0
1
 
L(M): 
Sequências em que o símbolo inicial seja 
diferente do último símbolo. 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 18 
 
 
III.3 CONSTRUINDO UM AFD DE RECONHECIMENTO 
Dada uma descrição da linguagem L(M), construiremos o AFD correspondente. Consideraremos 
implicitamenteo alfabeto de entrada I = { a, b }, ou então, quando for o caso, o alfabeto I = { 0, 1 }. 
EXEMPLOS RESOLVIDOS EM AULA: 
Para cada exemplo, vamos enumerar algumas das sequências que obedecem ou não à descrição 
dada. Desta forma, devemos construir um autômato que, ao ler qualquer sequência a ser reconhecida, 
termine seu processamento em um estado final; e o processamento de qualquer sequência que não deve 
ser reconhecida leva o autômato a um estado não-final. 
EXEMPLOS RESOLVIDOS EM SALA – Construir AFD’s que reconheçam as seguintes linguagens:
a. Sequências iniciadas com o símbolo ‘a’. 
 
  L(M): a, aa, ab, aaa, aab, aba, abb, aaaa,  
  L(M): , b, ba, bb, baa, bab, bba, bbb,  
 
a
e0
e2 a,b
b
a,be1
 
 
b. Seqs finalizadas pelo símbolo ‘a’. 
 
  L(M): a, aa, ba, aaa, aba, baa, bba, aaaa,  
  L(M): , b, ab, bb, aab, abb, bab, bbb,  
 
 
a
b
e0b ae1
 
 
 
c. Seqs iniciadas por dois símbolos iguais. 
 
  L(M): 
  L(M): 
 
e0
b
e2
e1
a
a,be4
a
a,b e3
b
a
b
 
 
d. Seqs terminadas com dois símbolos iguais. 
 
  L(M): 
  L(M): 
 
e0
b
e2
e1
a
be4
b
b
a e3 a
a
b
a
 
 
 
e. Seqs com a’s e b’s de comprimento par. 
 
  L(M): , aa, ab, ba, bb, aaaa, aaab,  
  L(M): a, b, aaa, aab, aba, abb, baa, bab,  
 
a,b
a,b
e0 e1
 
 
f. Seqs contendo um nº par de ‘a’s. 
 
  L(M): , b, aa, bb, aab, aba, bbb,  
  L(M): a, ab, ba, abb, bab, bba, aaa,  
 
a
a
e0 e1b b
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 19 
 
 
g. Seqs em que o 2º símbolo é ‘a’. 
 
  L(M): 
  L(M): 
a
e2
e0 e1
a,b
a,b
e1
b
a,b
 
 
h. Seqs em que o penúltimo símbolo é ‘a’. 
 
  L(M): 
  L(M): 
a
e2
e0 e1
a
a
b
e3
b b
a
b
 
 
i. Seqs que contenham dois ‘1’s consecutivos. 
 
  L(M): 
 
  L(M): 
 
1
e2e0 e1
1
0,1
0
0
 
 
j. Seqs terminadas com ‘101’. 
 
  L(M): 
 
  L(M): 
 
0
e3e0 e1
1
0
e2
1
1
0
1
0 
 
k. Seqs em que todo ‘a’ é sucedido por ‘b’. 
 
  L(M): , b, ab, bb, abb, bab, bbb, bbbb,  
 
  L(M): a, aa, ba, bba, aba, baa, aab, aaa,  
 
e0
e1
a
a
e3 a,b
b
b
 
 
l. Seqs de comprimento par finalizadas por ‘a’. 
 
  L(M): 
 
  L(M): 
 
a,b e2
e0 e1
a,b
b
a
a,b e3
 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 20 
 
 
III.4 EXERCÍCIOS 
APOSTILA: pág. 463 em diante: 
 para os exercícios 19) (menos item b), 20), e 32) construir AFD reconhecedores das 
linguagens descritas em cada item; 
 caracterizar as linguagens reconhecidas pelos ADF’s dos exercícios do 25) ao 30); 
 
9) Descreva, em português, a linguagem L(M) para cada AFD M, a seguir. 
a) 
e
0
e
1
0,1
0,1 
 
 
d) 
0,1
e
1
1,0
e
0
 
 
 
g) 
0
1,0
e
2
1
e
0
0
1
e
1
 
 
b) 
a
b
b
e
1
a
e
0
 
 
 
e) 
e
0
e
1
1,0
1
0
 
 
h) 
0
1,0
e
1
e
2
1
e
0
0
1 
 
c) 
1
e
1
1,0
e
0
0
 
 
 
f) 
e
0
e
1
1,0
0,1
 
 
 
i) 
0
1,0
e
2
1e
1
0
1
e
0
 
 
j) 
1
0,1
e
2
0
e
0
e
1
0,1
 
 
 
 
k) 
1
0,1
0
e
1
e
0
e
2
0,1
 
 
 
l) 
e0
0
1
1
0
1
e1 e2
0
1
e4e3
0
0
1
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 21 
 
 
m) 
0
1,0
e
2
1
e
0
0
1
e
1
 
 
 
 
n) 
0
1
1
0
e
1
e
2
e
3
e
0
1
0
0,
1
 
 
o) 
1
1
e
0
0,1
e
1
00
e
2
 
 
 
10) Para o AFD M, representado a seguir: 
a) Dê 5 exemplos de palavras reconhecidas por M. 
b) Descreva L(M) em português 
c) Em que implicaria o fato de e0 não ser um estado final? 
e
4
0
e
1
e
0
e
3
1
1
e
2
0
0
1
0
1
1
0
 
11) Para o AFD M, representado a seguir: 
a) Dê 5 exemplos de palavras reconhecidas por M. 
b) Descreva L(M) em português 
c) O que implicaria o fato de e0 também ser um estado final? e0
e
1
e
2
e
5
e
3
e
4
0
1
0
0
1
1
1
1
0
0
0,1
 
12) Para o AFD M, representado a seguir: 
a) Dê 5 exemplos de palavras reconhecidas por M. 
b) Descreva L(M) em português 
c) O que implicaria o fato de e0 não ser um estado final? 
e
3
0 1
0
1
0,1
e
1
e
0
e
2
0
1
 
13) Para I = { a, b }, construir os grafos de AFD’s que reconheçam as seguintes linguagens: 
a) Palavras de comprimento par. 
b) Palavras de comprimento par E terminadas com a. 
c) Palavras de comprimento ímpar E terminadas com a. 
d) Palavras que possuam mais de um a E mais de um b. 
e) Palavras que possuam mais de um a OU mais de um b. 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 22 
 
 
f) Palavras em que TODO b é precedido de a. 
g) Palavras em que TODO b é sucedido por a. 
h) Palavras em que o símbolo inicial seja igual ao símbolo final. 
i) Palavras em que o símbolo inicial seja diferente do símbolo final. 
j) Palavras que possuam dois símbolos a’s consecutivos. 
k) Palavras que NÃO possuam dois símbolos a’s consecutivos. 
l) Palavras que NÃO possuam repetição consecutiva de um mesmo símbolo. 
m) Palavras que NÃO terminem com dois a’s consecutivos. 
n) Palavras com 3 ou mais símbolos, sendo que ambos – a e b – deverão estão presentes. 
o) Palavras que NÃO tenham a’s isolados. Ou seja, TODO símbolo a tem um vizinho igual a ele. 
14) Para o alfabeto I = { 0, 1 }, construir AFD’s que reconheçam as seguintes linguagens: 
a) Palavras com quantidade par de 0’s. 
b) Palavras em que o penúltimo dígito seja 0. 
c) Palavras em que o 2º símbolo seja igual ao 4º símbolo. 
d) Palavras que tenham o sufixo ‘101’. 
e) Palavras que tenham o sufixo por ‘110’. 
f) Palavras terminadas por dois símbolos diferentes. 
g) Palavras em que a “soma dos seus bits” não seja maior do que 3. 
h) Palavras que não possuam três 1’s consecutivos. 
15) Para o alfabeto de entrada I = { a, b, c, d, e }, construir um AFD’s que reconheçam as linguagens: 
a) Palavras iniciadas por vogal. 
b) Palavras que NÃO comecem com consoante. 
c) Qual a diferença dos conjuntos definidos nos itens a) e b)? 
16) Construir um AFD que reconheça a linguagem formadas pelas palavras do alfabeto I = { a, b } que 
contenham um n° par de a’s E um n° par de b’s (não necessariamente o mesmo n° de a’s e b’s). 
III.5 RESPOSTAS DE ALGUNS EXERCÍCIOS: 
9) Assumindo o alfabeto de entrada { 0, 1 } ou { a, b }, dependendo de cada MEF, temos: 
a) Seqs de comprimento ímpar. 
b) Seqs: vazia e sequências terminadas com ‘b’. OU TAMBÉM : Seqs que não terminem com ‘a’. 
c) Seqs que não contenham o símbolo ‘1’. 
d) Apenas a sequência vazia. 
e) Conjunto vazio ou seja: nenhuma sequência é reconhecida. 
f) Conjunto vazio ou seja: nenhuma sequência é reconhecida. 
g) Seqs que contenham o (ao menos um) símbolo ‘1’. 
h) Seqs não vazias contendo apenas símbolos ‘0’ (um ou vários). 
i) Apenas a sequência vazia. 
j) Seqs iniciadas com o símbolo ‘1’. 
k) Seqs que não iniciem com o símbolo 1. 
l) Seqs em que os dois últimos símbolos são diferentes. 
m) Qualquer seq não vazia. 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 23 
 
 
n) Seqs que contenham ambos os símbolos ‘0’ e ‘1’. 
o) Seqs que não contenham dois ‘1’s consecutivos. 
12) 
a) , 0, 1, 01, 10, 010, 101, 0101, 1010, … 
b) Seqs que não tenham repetição consecutiva de nenhum símbolo 
c) O conjunto de sequências reconhecido não incluiria a seq vazia. 
13) 
b) 
a
b
s
2
s
2
a,b
a,b
s
0
s
1
a,b
 
c) 
a
b
s
1
s
2
a,b
a,b
s
0
 
f) 
a
b
a
s
1
s
2
s
0
b
a,b
 
n) 
s
0
b
s
3
b
s
6
b
s
1
s
4
s
2
a
a
a
s
5
b
a
b
a
a,b
a,b
 
i) 
s
a
b
s
3
a
s
4
s
b
a
bs
2
b
a
b
a
a
b
 
 
 
14) b) 
s
0
s
3
s
1
0
s
2
0
1
0
1
1
1
0
 
 
 
 
 
 
 
 
 
 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 24 
 
 
IV EXPRESSÕES REGULARES E LINGUAGENS REGULARES (CONJUNTOS REGULARES) 
Um dos problemas que estudamos em Máquinas de Estado Finito é a caracterização da 
linguagem reconhecida por um AFD, que deve ser exata, ou seja, “incluir” todas as sequênciasreconhecidas e “excluir” todas as que serão rejeitadas pelo autômato. Em muitos casos, a descrição 
exata de um conjunto de sequências em uma linguagem natural, como o português, pode não ser muito 
simples, além de não ser universal. 
Uma solução para este problema é a utilização de outro tipo de linguagem, simbólica e universal, 
que facilita a correta caracterização de determinadas linguagens de um dado alfabeto. 
Este capítulo descreve as expressões regulares, que caracterizam as chamadas linguagens 
regulares: conjuntos de sequências reconhecidos por autômatos finitos, o que é provado pelo 
Teorema de Kleene, que será visto adiante. 
IV.1 DEFINIÇÃO: EXPRESSÕES REGULARES 
Expressões regulares são expressões formadas a partir de um dado alfabeto I, e conterão os 
símbolos deste alfabeto, além de operadores específicos. Para diferentes alfabetos, temos novas 
expressões regulares com símbolos do alfabeto considerado. O texto abaixo (apostila, pág. 443) define 
as expressões regulares com os símbolos de um alfabeto I: 
 
 Os itens 1. e 2. compõem a base da definição por recorrência, e definem as expressões 
regulares “simples” ou “elementares”: 
1. Os símbolos  e  são expressões regulares. Esta definição vale para qualquer alfabeto I. 
2. Cada símbolo i pertencente ao alfabeto I é, por si só, uma expressão regular. 
 O item 3. é o passo da recorrência, e define expressões regulares complexas, formadas a 
partir de outras expressões regulares mais simples: 
(a) AB é formada pela concatenação da expressão regular A com a expressão regular B; 
(b) A  B é formada pela “operação” ou entre as expressões regulares A e B; 
(c) A* é formada pela “operação” estrela aplicada sobre uma única expressão regular A. 
Temos então alguns exemplos de expressões regulares formadas pelo alfabeto I = { a, b }: 
  a b expressões básicas 
aa ab ba bb item 3a – concatenação 
 a  b b  a item 3b – ou 
 a* b* item 3c – estrela 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 25 
 
 
As expressões regulares “geradas” pelo item 3 podem ser “recombinadas” da mesma forma, 
gerando expressões mais complexas. Temos, por exemplo, as expressões regulares: 
 (a  b)* item 3c: operação estrela aplicada sobre a expressão regular a  b 
 a  (b*) item 3b: operação ou aplicada às expressões regulares a e b* 
Interessante notar que, na definição de alguma linguagem simbólica, a utilização de parênteses 
visa estabelecer a ordem de avaliação dos operadores, como nos exemplos acima. Além disso, 
geralmente é estabelecida uma convenção para a precedência de operadores, visando diminuir uma 
quantidade excessiva de parênteses. Com expressões regulares isso também acontece, e a convenção 
universalmente aceita estabelece a seguinte precedência: 
1. maior precedência – operador * (estrela) 
2. média precedência – operador de concatenação 
3. menor precedência – operador  (ou) 
Vejamos mais exemplos de expressões regulares formadas por I = { a, b }, aplicando a convenção 
de precedência estabelecida (ou seja, sem parênteses desnecessários): 
 (a  b)* estrela aplicada à expressão regular a  b 
 a  b* operação ou entre a expressão regular a e a expressão regular b* 
 
 aa  b operação ou entre a expressão regular aa e a expressão regular b 
 a (a  b) concatenação de a com a  b 
 
 aa* concatenação de a com a* 
 (aa)* estrela aplicada à expressão regular aa 
 
 aa  b* ou entre as expressões regulares aa e b* 
 a (a  b*) concatenação da expressão regular a com a expressão regular a  b* 
 a (a  b)* concatenação da expressão regular a com a expressão regular (a b)* 
 (aa  b)* estrela aplicada à expressão regular aa b 
 
 aa*  bb* ou entre a expressão regular aa* e a expressão regular bb* 
(aa)*  (bb)* ou entre a expressão regular (aa)* e a expressão regular (bb)* 
 (aa  bb)* estrela aplicada à expressão regular aa  bb 
 
 ( ab* )* estrela aplicada à expressão regular ab* 
IV.2 DEFINIÇÃO: LINGUAGENS REGULARES 
Vamos agora estudar como cada expressão regular formada por I pode caracterizar um conjunto 
contendo sequências formadas por símbolos do alfabeto I. Os conjuntos definidos desta forma são 
chamados linguagens regulares. 
Formalmente: seja uma expressão regular R, definida sobre um alfabeto I. Definiremos L(R) 
como a linguagem regular (ou conjunto regular) associada à expressão R. 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 26 
 
 
 
 Os itens 1 a 3 compõem a base da definição por recorrência, e definem os conjuntos 
regulares “simples” ou “elementares”: 
1. L() = { } a expressão regular  caracteriza a linguagem vazia (conjunto vazio); 
2. L() = {  } a expressão regular  caracteriza a linguagem regular composta apenas 
pela sequência vazia; 
3. L(i) = { i } sendo i um símbolo do alfabeto I, a expressão regular i caracteriza a 
linguagem regular contendo apenas a sequência i (de comprimento um). 
Como exemplo, temos então as linguagens regulares elementares formados por I = { a, b }: 
L() = { } 
L() = {  } 
L(a) = { a } 
L(b) = { b } 
 O item 4 é o passo da recorrência, e define linguagens regulares mais complexas, formadas a 
partir de outros conjuntos regulares mais simples, através das operações de concatenção, 
união, e fechamento. 
(a) L(AB) = L(A)·L(B) a linguagem regular L(AB) é formada pela concatenação 
 dos conjuntos regulares L(A) e L(B); 
(b) L(A  B) = L(A) L(B) a linguagem regular L(AB) é formada pela união entre os 
 os conjuntos regulares L(A) e L(B); 
(c) L(A*) = L(A) * a linguagem regular L(A*) é formada pelo fechamento do 
 conjunto regular L(A). 
Vejamos exemplos de linguagens regulares formadas pelo alfabeto I = { a, b }: 
L(aa) = { aa } linguagem regular formada pela concatenação: { a } { a } 
L(ab) = { ab } linguagem regular formada pela concatenação: { a } { b } 
L(a  b) = { a , b } linguagem regular a  b formada pela união: { a }  { b } 
L(a*) = {  , a , aa , aaa , aaaa ,  } linguagem regular a* formada pelo fechamento: { a } * 
L(b*) = {  , b , bb , bbb , bbbb ,  } linguagem regular b* formada pelo fechamento: { b } * 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 27 
 
 
Podemos continuar aplicando as operações entre os conjuntos exemplificados acima, formando 
linguagens regulares mais complexas. Vejamos mais exemplos: 
L( aa  b ) = { aa , b } união: { aa }  { b } 
L( a (a  b) ) = { aa , ab } concatenação: { a } { a,b } 
L( (a  b) (a  b) ) = { aa , ab , ba , bb } concatenação: { a,b } { a,b } 
 
L(aa*) = { a , aa , aaa , aaaa ,  } contatenação: { a } {  , a , aa , aaa , aaaa ,  } 
L(ab*) = { a , ab , abb , abbb ,  } contatenação: { a } {  , b , bb , bbb , bbbb ,  } 
L( (aa)* ) = {  , aa , aaaa , aaaaaa ,  } fechamento: { aa } * 
 
L(a*  b* ) = {  , a , b , aa , bb , aaa , bbb ,  } {  , a , aa , aaa ,  }  {  , b , bb , bbb ,  } 
L(aa*  bb* ) = { a , b , aa , bb , aaa , bbb ,  } { a , aa , aaa ,  }  { b , bb , bbb ,  } 
 
L( (aa)*  (bb)* ) = {  , aa , bb , aaaa , bbbb , aaaa ,  } {  , aa , aaaa ,  }  {  , bb , bbbb ,  } 
 
L( (aa  bb)* ) = {  , aa , bb , aaaa , aabb , bbaa , bbbb , aaaaaa , aaaabb ,  } 
 
L( (a  b)* ) = {  , a , b , aa , ab , ba , bb , aaa , aab , aba , abb , baa , baa , bba ,  } 
L(a(a  b)* ) = { a , aa , ab , aaa , aab , aba , abb , aaaa , aaab , aaba ,  } 
IV.3 EXERCÍCIOS RESOLVIDOS EM AULA 
1) Para o alfabeto I = { a, b }, descreva em português as linguagens regulares abaixo: 
a) L( a (a  b) ) Resp. Sequências formadas por dois símbolos, e iniciadas por a. 
b) L( (a  b) (a  b) ) Resp. Sequências formadas por dois símbolos (de comprimento dois). 
c) L( a* ) Resp. Sequências que não contenham o símbolo b. 
d) L( aa* ) Resp. Sequências não vazias que só contenham o símboloa. 
e) L( ab* ) Resp. Sequências iniciadas por a em que os demais símbolos sejam b. 
f) L( (aa)* ) Resp. Sequências de comprimento par que não contenham o símbolo b. 
g) L( a*  b* ) Resp. Sequência vazia, e sequências formadas pelo mesmo símbolo. 
h) L( aa*  bb* ) Resp. Sequências não vazias formadas pelo mesmo símbolo. 
i) L( (aa)*  (bb)* ) Resp. Sequências de comprimento par formadas pelo mesmo símbolo. 
j) L( (aa  bb)* ) Resp. 
k) L( (a  b)* ) Resp. Todas as sequências com os símbolos a e b, incluindo . 
l) L( a (a  b)* ) Resp. Sequências iniciadas por a. 
m) L( (a  b) (a  b)* ) Resp. Sequências não vazias. 
n) L( (a  b) a (a  b)* ) Resp. Sequências em que o 2º símbolo é a. 
o) L( (a  b)* a (a  b) ) Resp. Sequências em que o penúltimo símbolo é a. 
p) L( ( (a  b) (a  b) ) * ) Resp. Sequências de comprimento par. 
q) L( (ab*) * ) Resp. Sequências que não sejam iniciadas por b. 
r) L( (a*b) * ) Resp. Sequências que não sejam finalizadas por a. 
 
TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA 
 NOTAS DE AULA 28 
 
 
2) Escreva as expressões regulares que caracterizem as linguagens a seguir. 
Considere o alfabeto { a, b }, ou quando for o caso, o alfabeto { 0, 1}. 
a) Sequências iniciadas com dois símbolos iguais. 
b) Sequências finalizadas por dois símbolos diferentes. 
c) Sequências que tenham comprimento ímpar. 
d) Sequências que tenham no mínimo um símbolo a. 
e) Sequências que tenham dois a’s consecutivos 
f) Sequências que tenham exatamente dois símbolos a. 
g) Sequências com uma quantidade par de a’s. 
h) Sequências em que o 2º símbolo é a, e o 4º símbolo é b. 
i) Sequências que contenham no mínimo dois símbolos. 
j) Sequências contendo no máximo três símbolos. 
 GABARITO: 
a) (aa  bb) (a  b)* 
aa (a  b)*  bb (a  b)* 
b) (a  b)* (ab  ba) 
(a  b)*ab  (a  b)* ba 
c) (a  b) ( (a  b) (a  b) )* 
d) (a  b)* a (a  b)* 
b*a (a  b)* 
e) (a  b)* aa (a  b)* 
f) b* a b*a b* 
g) (ab*a  b)* 
b*(ab*a b*)* 
h) (a  b) a (a  b) b (a  b)* 
i) (a  b) (a  b) (a  b)* 
j) λ  (a  b)  (a  b) (a  b)  (a  b) (a  b) (a  b) 
 
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
e0
a,b
e1
a
 
 
 
b. aa* 
 
a
a
a,b
e0 e1
e2
b b
 
 
c. a*a 
a
a
a,b
e0 e1
e2
b b
 
 
d. a (a  b)* 
a
a,b
a,b
e0
e1
e2
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)* 
a,b
a,b
a,b
e0
e2
e3
b
e1
a
 
 
h. ( (a  b) (a  b) ) * 
 
 
a,b
a,b
e1e0
 
 
 
 
i. aa*  bb* 
a
a
b
e0
e1
b
a,b
e3
b
a
e2
 
 
j. (a  b)* a (a  b) 
 
 
 
 
 
 
 
 
 
k. a*  b* 
a
a
b
e1
b
a,b
e3
b
a
e0
e2
 
 
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) 
e
0
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) 
e
0
0
0,1
1
e
3
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
e
1
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) 
e
0
0,1
e
2
0
e
1
 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
ab
 
n) 
e
3
e
1
e
2
0
1
1
1
e
4
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
e
0
e
1
e
2
e
3
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 menos dois 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