Todos slides juntos

Prévia do material em texto

Teoria da Computação 
Profs. Júlio Silveira 
e 
Sérgio Monteiro 
Apresentação 
• Objetivos 
– Aprofundar o conceito de computação algorítmica, a partir do estudo 
dos conceitos e modelos teóricos dos autômatos. 
– Fornecer uma base para o estudo de linguagens formais. 
 
Apresentação 
• Ementa 
– Autômatos finitos 
– Expressões regulares. 
– Teorema de Kleene. 
– Conjuntos não regulares. 
– Autômatos de pilha. 
– Máquina de Turing. 
Bibliografia 
• Básica 
– GERSTING, J. L. Fundamentos matemáticos para a ciência da 
computação. 5ª ed., Rio de Janeiro: LTC, 2004. 
– HOPCROFT, John E; MOTWANI, Rajeev; ULMAN, Jeffrey D. Introdução 
à teoria dos autômatos, linguagens e computação. 
Rio de Janeiro: Elsevier, 2002. 
– MENEZES, Paulo B. Linguagens Formais e Autômatos. Série Livros 
Didáticos, nº 3. 4ª ed., Porto Alegre: Sagra Luzzato, 2005. 
Bibliografia 
• Complementar 
• SIPSER, M. Introdução à Teoria da Computação. Cengage Learning, 2007. 
• RAMOS, M.V.M., NETO, J.J., VEGA, I.S. Linguagens Formais: Teoria, 
Modelagem e Implementação. Porto Alegre: Bookman, 2009. 
• ROSA, J.L.G. Linguagens Formais e Autômatos. Rio de Janeiro: LTC, 2010. 
• AHO, Alfred V. Compiladores: princípios, técnicas e ferramentas. 2 ed. São 
Paulo: Pearson Addison-Weslwy, 2008. 
• DIVERIO, T.A., MENEZES, P.B. Teoria da Computação: Máquinas Universais e 
Computabilidade. Porto Alegre: Bookman, 2011. 
Aula 1 
• Conceitos e Definições 
– Símbolos 
– Alfabetos 
– Sequências 
• Operações 
– Linguagens 
• Conjuntos de sequências 
• Relações e Operações 
Conceitos básicos 
• Autômato 
– Processamento 
• Entrada: sequência de símbolos 
• Saída: sequência de símbolos 
Autômato
Entrada Saída
Conceitos básicos 
• Símbolo 
a, b, c, 0, 1, S, A, B, … 
 
• Alfabeto: conjunto finito e não vazio de símbolos. 
• A = { a, b } 
• B = { a, b, c, …, z } 
• C = { 0, 1 } 
 
A princípio não consideraremos o “espaço” como símbolo! 
 
Conceitos básicos 
• Sequência, palavra, ou cadeia 
– Concatenação de símbolos de um alfabeto 
a, ab, aaab, bbb, ababa, … 
• Comprimento de uma sequência 
| a | = 1 
| aaba | = 4 
 
• Letras gregas  = a  |  | = 1 
  = aaba  |  | = 4 
Conceitos básicos 
• Sequência vazia:  
– Sequência “sem” símbolos 
– Tem comprimento ZERO 
|  | = 0 
 
• Atenção! 
–  NÃO é símbolo! 
É uma notação para uma sequência “sem símbolos” 
Conceitos básicos 
• Prefixos, sufixos, subpalavras (ou subsequências) 
 
– Exemplo para  = aaba, temos: 
• , a, aa, aab, aaba são prefixos de aaba (ou seja, de ) 
• , a, ba, aba, aaba são sufixos de  
• , a, b, aa, ab, ba, aab, aba, aaba são subsequências de  
 
– Observe: 
•  é prefixo, sufixo e subsequência de qualquer palavra 
 
 
Conceitos básicos 
• Concatenação de sequências: · (ou simplesmente ) 
 
a·b = ab ab·b = abb ·abab = abab· = abab 
a·bb = abb abb· = abb abab = abab 
 
– Observe: |·| = || = || + || 
 
• ATENÇÃO! 
• abab não é uma sequência, e sim uma operação 
 
 |abab| = ? Resp.: |abab| = |abab| = 4 
Conceitos básicos 
• Linguagem 
– Conjunto de sequências de um dado alfabeto 
– Exemplos de linguagens, considerando o alfabeto { a, b } 
X = { a, ab, bbba } 
Y = {  } 
Z = { } 
W = { , bbbb } 
K = { a, ab, abb, abbb, abbbb, abbbbb,  } 
Conceitos básicos 
• Linguagem = conjunto de sequências 
– Todo conjunto tem cardinalidade 
 
X = { a, ab, bbba } |X| = 3 
Y = {  } |Y| = 1 
Z = { } =  |Z| = 0 
W = { , bbbb } |W| = 2 
K = { a, ab, abb, abbb, abbbb, abbbbb,  } |K| =  
Conceitos básicos 
• Linguagem = conjunto de sequências 
• Não confundir 
 
 CARDINALIDADE (conjunto) com COMPRIMENTO (sequência) 
 
| { bbba } | = 1 | bbba | = 4 
 
| { } | = 0 
 
| {  } | = 1 |  | = 0 
 
 
 
Conceitos básicos 
• Conjunto das sequências formadas por um alfabeto 
– Exemplo: sequências formadas pelo alfabeto A = { 0, 1 } 
 
A* = { , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101,  } 
Conceitos básicos 
• Relações envolvendo linguagens (conjuntos de sequências) 
  { 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,  } 
Conceitos básicos 
• Operações envolvendo linguagens (conjuntos de sequências) 
 
1. União { a, bbb }  { bb, a } = { a, bb, bbb } 
 
2. Interseção { a, bbb }  { bb, a } = { a } 
 
3. Diferença { a, bbb } – { bb, a } = { bbb } 
 
Conceitos básicos 
• Operações envolvendo linguagens (conjuntos de sequências) 
 
4. Concatenação 
 
 X·Y = XY = {  |   X e   Y } 
 
 { 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 } 
Conceitos básicos 
4. Concatenação 
 
– Observe que normalmente XY  XY 
 
 { a, aa } { b, bb } = { ab, abb, aab, aabb } 
 { b, bb } { a, aa } = { ba, baa, bba, bbaa } 
 
– Ainda 
 {  } X = X {  } = X 
  X = { } X =  
 
Conceitos básicos 
4. Concatenação 
 
– Casos particulares 
 
 {  } { a, ab, bbb } = { a, ab, bbb } 
 
  { a, ab, bbb } = { } { a, ab, bbb } =      ? 
 
Conceitos básicos 
4. Concatenação 
Xn = XXXX (n vezes) 
 
Exemplo: X = { a, bbb } 
 
X0 = {  } 
X1 = X = { a, bbb } 
X2 = XX = { a, bbb } { a, bbb } = { aa, abbb, bbba, bbbbbb } 
X3 = … = { aaa, aabbb, abbba, abbbbbb, bbbaa, bbbabbb, bbbbbba, bbbbbbbbb } 
 
Conceitos básicos 
5. Fechamento 
– X*: concatenações de elementos (sequências) de X 
 
Exemplo: X = { a, bbb } 
 
X* = { , a, bbb, aa, abbb, bbba, bbbbbb, aaa, aabbb, abbba, 
 abbbbbb, bbbaa, bbbabbb, bbbbbba, bbbbbbbbb, aaaa, … } 
 
Conceitos básicos 
5. Fechamento 
– Exemplos: 
 
Se X = { a } e Y = { b } temos: 
 
 X* = { , a, aa, aaa, aaaa, … } 
 Y* = { , b, bb, bbb, bbbb, … } 
 
Conceitos básicos 
• Expressões envolvendo várias operações 
– Exemplos, para X = { a } e Y = { b } 
 
 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! 
 
Conceitos básicos 
• Expressões envolvendo várias operações 
– Exemplos, para X = { a } e Y = { b } 
 
 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! 
 
Conceitos básicos 
I.4 EXERCÍCIOS 
NOTAS DE AULA 
Obrigado! 
 
 
Obrigado! 
Aula 2
• Autômatos Finitos
– AFD – Autômatos Finitos Determinísticos
– AFD de Processamento
Autômatos Finitos
• Autômato Finito (ou Máquina de Estado Finito)
• Pode ser
– Autômato de Processamento Entrada →→→→ Saída
– Autômato de Reconhecimento Entrada →→→→ Sim/Não
• Quanto ao determinismo
– AFD Autômato Finito Determinístico
– AFN Autômato Finito Não-Determinístico
AFD de Processamento
• Processamento
– Sequência de entrada α é lida, um símbolo a cada passo
– Sequência de saída β, um símbolo gerado a cada passo
AFD – Autômato Finito Determinístico
• AFD de PROCESSAMENTO
– Conjunto finito de estados
– Alfabeto de entrada
– Alfabeto de saída
– Cada estado gera um símbolo de saída (sempre o mesmo)
– Processamento do AFD:
• Os estados geram os símbolos de saída
• Os símbolos lidos da entrada geram mudança de estado
AFD de Processamento
• AFD – Processamento passo a passo
• A cada passo,o AFD está em um dos estados – estado atual
• O estado atual gera um símbolo de saída
• Um símbolo (do alfabeto) de entrada é lido
• Estado atual + símbolo lido → próximo estado
• No próximo passo, o próximo estado será o estado atual
– O processamento termina quando a entrada foi consumida
• Todos os símbolos de entrada foram lidos
AFD de Processamento
• Definição
– M = [E, I, O, fE, fO]
• E conjunto finito de estados. E = { e0 , e1 , e2 , … , ek }
• I alfabeto de entrada
• O alfabeto de saída
• fO função saída. fO: E →→→→ O estado → out
• fE função próximo estado. fE : E ×××× I →→→→ E (estado, in) → próx estado
– Estado inicial
• Convenção: quando não estipulado, e0
AFD de Processamento
• Exemplo: Tabela
E = { e0 , e1 , e2 }
O = { 0, 1 }
I = { 0, 1 }
AFD de Processamento
• Saída
– fO(e0) = 0
– fO(e1) = 1
• Transição de estados
– fE(e0,0) = e1
– fE(e0,1) = e0
AFD de Processamento
• Exemplo: Grafo
 
AFD de Processamento
• Grafo
– Símbolo de entrada lido
• No arco do grafo
• Se in for lido, vai para estado indicado
– Símbolo de saída
• No rótulo, “dentro” do nó
• O estado est gera o símbolo out
AFD de Processamento
• Exemplo: estado inicial e0
– α = 01101
– β =
 
 
011110
AFD de Processamento
• Processamento
– |β| = |α| + 1 
AFD de Processamento
• Exemplo: estado inicial e0
– α = 1100011011
– β =
 
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
AFD de Processamento
• Exemplo: estado inicial e0
– α = 1100011011
– β = 00011100111
 
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 e0 e0 e1 e2 e2 e0 e0 e1 e1 e1
Saída 0 0 0 1 1 1 0 0 1 1 1
AFD de Processamento
• Exemplo: estado inicial e0
 
Tempo t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10
Entrada -
Estado e0
Saída
AFD de Processamento
• Exemplo: estado inicial e0
– α = λ
– β = 0
 
Tempo t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10
Entrada -
Estado e0
Saída 0
AFD de Processamento
• Notas de aula II.3 – Exercícios
1) a) Desenhe o grafo b) Processe α = 110010
Estado
Atual
Próximo Estado Saída
Entrada Atual
0 1
e0 e2 e1 a
e1 e1 e0 b
e2 e0 e1 b
AFD de Processamento
• Notas de aula II.3 – Exercícios
1) a) Desenhe o grafo b) Processe α = 110010
Estado
Atual
Próximo Estado Saída
Entrada Atual
0 1
e0 e2 e1 a
e1 e1 e0 b
e2 e0 e1 b
β = abababb
AFD de Processamento
• Apostila I, pág. 460
1) a) indique a saída gerada pelo processamento de
α = 011011010
β = 0001111110
AFD de Processamento
• Exercício
Indique a saída gerada pelo processamento de
α = 110 β =
α = 111 β =
0011
0011
Duas sequências de 
entrada produziram a 
mesma saída!
AFD de Processamento
• Apostila I, pág. 460
2) a) Sequências de entrada α cujo processamento produziram 
β = 0011110
AFD de Processamento
• Apostila I, pág. 460
2) a) β = 0011110
AFD de Processamento
• Apostila I, pág. 460 - exercício
2) a) β = 0011110 Resposta:
α = 110100
e
α = 111010
AFD de Processamento
• Notas de aula II.3 – Exercícios
6) a) Complete o grafo do AFD abaixo I = { 0, 1 } O = { a, b }
α = 111 β = abba
b) β = abbb
α = ???
Resposta nas Notas de Aula
AFD de Processamento
• Praticar!
– Notas de aula II.3 – Exercícios 
Obrigado!
• Autômatos Finitos Determinísticos
– AFD reconhecedor (ou AFD de reconhecimento)
Aula 3
AFD’s de reconhecimento
• AFD reconhecedor M
– Alfabeto de entrada I
– Estados não geram saída: não existe alfabeto de saída O
– Conjunto de Estados E particionado em:
• Estados FINAIS
• Estados NÃO-FINAIS
– M processa α
• Termina em estado final: ACEITA α
• Termina em estado não final: REJEITA α
AFD’s de reconhecimento
• Exemplo
– AFD de reconhecimento M
• Estados FINAIS: e2 e e4
• M ACEITA as sequências
– 01, 011, 110, …
• M REJEITA as sequências
– 0, 00, 101, …
AFD’s de reconhecimento
• L(M) – Linguagem reconhecida por um AFD M
– M processa todas as sequências do conjunto I*
– Partição do conjunto I*
• I* = S ∪∪∪∪ S’
• S = linguagem reconhecida por M ⇒ Notação: L(M)
• S’ = conjunto das sequências rejeitadas por M
AFD’s de reconhecimento
• Apostila I, PROBLEMA PRÁTICO 40, pág. 448
– Caracterizar L(M) em português
– L(M) = 
– Resposta: 
{ 0 }
Apenas a sequência 0
AFD’s de reconhecimento
• Apostila I, PROBLEMA PRÁTICO 40, pág. 448
– Caracterizar L(M) em português
– L(M) = 
– Resposta: 
{ 0, 1 }
Apenas as sequências 0 e 1, ou
Sequências de comprimento um
AFD’s de reconhecimento
• Apostila I, PROBLEMA PRÁTICO 40, pág. 448
– Caracterizar L(M) em português
– L(M) = 
– Resposta: 
{ 10, 010, 0010, 00010, … }
Sequências de sufixo 01 que contenham 
um único símbolo 1
AFD’s de reconhecimento
• Apostila I, PROBLEMA PRÁTICO 40, pág. 448
– Caracterizar L(M) em português
– L(M) = 
– Resposta: 
{ λ, 11, 1111, 111111, … }
Sequências de comprimento par que 
não contenham o símbolo 0
AFD’s de reconhecimento
• Exercícios
– Caracterizar L(M) em português
a)
– L(M) = Apenas a sequência vazia.
AFD’s de reconhecimento
• Exercícios
e)
– L(M) = Sequências de comprimento par.
AFD’s de reconhecimento
• Exercícios
b)
– L(M) = Sequências que não contenham o símbolo 1.
AFD’s de reconhecimento
• Exercícios
f)
– L(M) = Conjunto vazio.
(M não reconhece nenhuma sequência)
AFD’s de reconhecimento
• Exercícios
c)
– L(M) = Sequências que contenham dois 
símbolos b’s consecutivos.
AFD’s de reconhecimento
• Exercícios
g)
– L(M) = Sequências que contenham dois símbolos b. 
ou
Sequências que contenham dois ou mais b’s.
AFD’s de reconhecimento
• Exercícios
d)
– L(M) = Sequências que não contenham nenhum 
símbolo sucedido por outro igual.
AFD’s de reconhecimento
• Exercícios
h)
– L(M) = Sequências em que o símbolo inicial seja 
diferente do último símbolo.
AFD’s de reconhecimento
• Notas de aula
– III.4 EXERCÍCIOS
• APOSTILA: pág. 463 em diante, ver enunciado nas notas de aula
• Questões: 9 a 12
Obrigado!
• Construindo um AFD de reconhecimento
– AFD deve:
• Reconhecer α ∈ L(M) ⇒ terminar em um estado final
• Não reconhecer α ∉ L(M) ⇒ terminar em um estado não-final
Aula 4
a) L(M): Sequências iniciadas com o símbolo ‘a’.
Construindo um AFD reconhecedor
b) L(M): Sequências finalizadas por ‘a’.
Construindo um AFD reconhecedor
c) L(M): Seqs iniciadas por dois símbolos iguais.
Construindo um AFD reconhecedor
d) L(M): Seqs terminadas com dois símbolos iguais.
Construindo um AFD reconhecedor
e) L(M): Seqs com a’s e b’s de comprimento par.
Construindo um AFD reconhecedor
f) L(M): Seqs contendo um nº par de ‘a’s.
Construindo um AFD reconhecedor
g) L(M): Seqs em que o 2º símbolo é ‘a’.
Construindo um AFD reconhecedor
h) L(M): Seqs em que o penúltimo símbolo é ‘a’.
Construindo um AFD reconhecedor
i) L(M): Seqs que contenham dois ‘1’s consecutivos.
Construindo um AFD reconhecedor
j) Seqs terminadas com ‘101’.
Construindo um AFD reconhecedor
k) Seqs em que todo ‘a’ é sucedido por ‘b’.
Construindo um AFD reconhecedor
l) Seqs de comprimento par finalizadas por ‘a’.
Construindo um AFD reconhecedor
Construindo um AFD reconhecedor
• Notas de aula
– III.4 EXERCÍCIOS
• Questões: 13 a 16
Obrigado!
• Expressões regulares
• Linguagens regulares
– Conjuntos regulares (caracterizados por expressões regulares)
Aula 5
• Expressões regulares formadas por um alfabeto I
– Os símbolos ∅∅∅∅ e λλλλ
– Todo símbolo i ∈ I
• E mais: se A e B são expressões regulares, então
– Concatenação: AB é uma expressão regular (pode-se escrever A⋅⋅⋅⋅B)
– Ou: A ∨∨∨∨ B é uma expressão regular (lê-se A ou B)
– Estrela: A* é uma expressão regular (lê-se A estrela)
Expressões regulares
• Exemplos, para I = { a, b }
∅ λ
a expressões elementares
b
aa concatenação das expressões a e a
ab ba bb outras concatenações
a ∨∨∨∨ b a ou b
a* a estrela
Expressões regulares
• Expressões compostas
a(a*) a concatenada com a*
(aa)* estrela da expressãoaa
aa* ?
a ∨∨∨∨ (b*) a ou b*
(a ∨∨∨∨ b)* estrela da expressão a ∨∨∨∨ b
a ∨∨∨∨ b* ? 
Expressões regulares
• Precedência de operações
1. * Estrela
2. ⋅⋅⋅⋅ Concatenação
3. ∨∨∨∨ Ou
Expressões regulares
• Exemplos
aa* ⇔ a(a)* a concatenada com a*
a ∨ b* ⇔ a ∨ (b*) ou da expressão a com b* 
aa ∨ b ⇔ (aa) ∨ b ou de aa com b
a(a ∨ b) a concatenada com a ∨∨∨∨ b 
a(a ∨ b)* ⇔ a⋅[(a ∨ b)*] a concatenada com (a∨∨∨∨b)*
Expressões regulares
• Expressões regulares caracterizam as linguagens regulares
• Notação
– Se X é uma expressão regular
– L(X) denota a linguagem regular caracterizada por X
• Conjunto de sequências caracterizado pela expressão regular
Linguagens regulares
• Linguagens definidas por expressões regulares elementares
– L ( ∅∅∅∅ ) = { }
– L ( λλλλ ) = { λλλλ }
• Para todo i ∈ I
– L ( i ) = { i }
Linguagens regulares
• Exemplos para I = { a, b }
L ( a ) = { a }
L ( b ) = { b }
Linguagens regulares
• Linguagens definidas por expressões regulares compostas
• se A e B são expressões regulares, então
– L ( AB ) = L(A) ⋅⋅⋅⋅ L(B) concatenação de L(A) com L(B)
– L ( A ∨∨∨∨ B ) = L(A) U L(B) união de L(A) com L(B)
– L ( A* ) = ( L(A) )* fechamento do conjunto L(A)
Linguagens regulares
• Exemplos para I = { a, b }
L ( aa ) =
L ( ab ) =
L ( a∨∨∨∨b ) =
L ( a* ) =
L(a)⋅L(a) = {a} {a} = { aa }
= {a} {b} = { aa }
L(a) U L(b) = {a} U {b} = { a,b }
(L(a))* = {a}* = { λ, a, aa, aaa, … }
Linguagens regulares
• Exemplos para I = { a, b }
L ( aa* ) =
L ( (aa)* ) =
{a} {a}* = {a} { λ, a, aa, aaa, … }
= { a, aa, aaa, aaaa, … }
{aa}* = { λ, aa, aaaa, aaaaaa, … }
Linguagens regulares
{aa} U {b} = { a, bb }
{a} {a,b} = { aa, ab }
{ a,b } { a,b }
= {aa, ab, ba, bb }
• Exemplos para I = { a, b }
L ( aa∨∨∨∨b ) =
L (a(a∨∨∨∨b)) =
L ((a∨∨∨∨b)(a∨∨∨∨b)) =
Linguagens regulares
• Exemplos (solução nas notas de aula)
L ( ab* ) =
L ( a*∨∨∨∨ b*) =
L ( aa*∨∨∨∨ bb*) =
Linguagens regulares
• Exercícios (solução nas notas de aula)
Descreva em português 
L ( (aa)*∨∨∨∨ (bb)*) =
L ( (aa ∨∨∨∨ bb)*) =
L ( (a ∨∨∨∨ b)*) =
L ( a(a ∨∨∨∨ b)*) =
L ( (a ∨∨∨∨ b)*a) =
Linguagens regulares
• Exercícios (solução nas notas de aula)
Descreva em português 
L ( (a ∨∨∨∨ b) (a ∨∨∨∨ b)*) =
L ( (a ∨∨∨∨ b) a (a ∨∨∨∨ b)*) =
L ( (a ∨∨∨∨ b)* a (a ∨∨∨∨ b)) =
L ( ( (a ∨∨∨∨ b) (a ∨∨∨∨ b) )* ) =
Linguagens regulares
• Exercícios (solução nas notas de aula)
Descreva em português 
L ( (ab*)*) =
L ( (a*b)*) =
Linguagens regulares
• Exercícios (solução nas notas de aula)
Escreva as expressões regulares que caracterizem as linguagens
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
Linguagens regulares
• Exercícios (solução nas notas de aula)
Escreva as expressões regulares que caracterizem as linguagens
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.
Linguagens regulares
Obrigado!
• Teorema de Kleene
Aula 6
• Teorema de Kleene
Teorema de Kleene
• Exercícios
– Construir um AFD que reconheça as linguagens a seguir:
a. L(a*)
Teorema de Kleene
• Exercícios
– Construir um AFD que reconheça as linguagens a seguir:
b. L(aa*)
Teorema de Kleene
• Exercícios
– Construir um AFD que reconheça as linguagens a seguir:
c. L(a*a) = L(aa*)
Teorema de Kleene
• Exercícios
– Construir um AFD que reconheça as linguagens a seguir:
d. L [ a(avb)* ]
Teorema de Kleene
• Exercícios
– Construir um AFD que reconheça as linguagens a seguir:
e. L [ (aa)* ]
Teorema de Kleene
• Exercícios
– Construir um AFD que reconheça as linguagens a seguir:
f. L [ (avb) (avb)* ]
g. L [ (avb)* a (avb) ]
h. L [ ( (avb) (avb) )* ]
i. L [ aa* v bb* ]
j. L [ (avb)* a (avb) ]
k. L (a* v b*)
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
a
e1
a
bbb
a
e0 e2
• Exercícios
– Escrever as expressões regulares das linguagens reconhecidas pelos 
autômatos a seguir:
Teorema de Kleene
Respostas nas Notas de Aula
• Exercícios
– Notas de aula, IV.5 – Exercícios
Teorema de Kleene
Obrigado!
• Relações e operações envolvendo linguagens regulares
• AFN – Autômatos Finitos Não-determinísticos
Aula 7
• Relações de pertinência
i. a ∈ L ( a(avb)* )
ii. aa ∈ L ( a(avb)* )
iii. λ ∉ L ( a(avb)* )
iv. ab ∈ L ( a(avb)* )
v. ba ∉ L ( a(avb)* )
Relações envolvendo Linguagens Regulares
• Relações de inclusão
vi. L( a* ) ⊂ L( aa* ) ?
vii. L( aa* ) ⊂ L( a* ) ?
viii. L( a* ) ⊂ L( a(avb) * ) ? 
ix. L( aa* ) ⊂ L( a(avb)* ) ?
x. L( a(avb)* ) ⊂ L( aa* ) ?
Relações envolvendo Linguagens Regulares
• Relações de inclusão – respostas
vi. L( a* ) ⊄ L( aa* ), pois λ ∈ L( a* ) mas λ ∉ L( aa* )
vii. L( aa* ) ⊂ L( a* )
viii. L( a* ) ⊄ L( a(avb) * ), pois λ ∈ L( a* ) mas λ ∉ L( a(avb) * )
ix. L( aa* ) ⊂ L( a(avb)* )
x. L( a(avb)* ) ⊄ L( aa* ), pois ab ∈ L( a(avb)* ) mas ab ∉ L( aa* )
Relembrando:
L( a* ) = { λ, a, aa, aaa, aaaa, … }
L( aa* ) = { a, aa, aaa, aaaa, … }
Relações envolvendo Linguagens Regulares
• A partir do Teorema de Kleene, pode-se provar que
– O conjunto das linguagens regulares é fechado sobre as operações
• União, Interseção
• Diferença, Complemento
– Em outras palavras
• As operações de união, interseção, diferença e complemento
envolvendo linguagens regulares resultam em conjuntos que
também são linguagens regulares
Operações envolvendo Linguagens Regulares
• Exemplos
i. L ( a* ) ∪ L ( b* ) =
ii. L ( a* ) ∩ L ( b* ) =
iii. L ( a* ) – L ( λ ) =
Operações envolvendo Linguagens Regulares
L ( a* v b* )
L ( λ )
L ( aa* )
• Exercícios
– Caracterize por expressão regular os conjuntos resultantes
das operações a seguir:
iv. L ( a* ) – L ( b* ) =
v. L ( (a v b)* ) – L ( λ ) =
vi. L ( a* v b* ) – L ( λ ) =
vii. L ( a* ) – L ( (aa)* ) =
viii. L ( a(avb) )* ) – L ( a* ) =
Operações envolvendo Linguagens Regulares
• Exercícios
– Respostas:
iv. L ( a* ) – L ( b* ) =
v. L ( (a v b)* ) – L ( λ ) =
vi. L ( a* v b* ) – L ( λ ) =
vii. L ( a* ) – L ( (aa)* ) =
viii. L ( a(avb) )* ) – L ( a* ) =
Operações envolvendo Linguagens Regulares
L ( aa* )
L ( (a v b)(a v b)* )
L ( aa* v bb* )
L ( a(aa)* )
L ( a*b(avb)* ) ou
L ( (avb)*b(avb)* )
• Exemplos
1. M1
AFN – Autômatos Finitos Não-determinísticos
Marca de estado inicial
q0 q1
a,b
a
• Autômatos Finitos Não-determinísticos*
– Um estado, ao ler uma entrada, tem várias opções de transição
– Um estado, ao ler uma entrada, pode não ir a estado nenhum
– Um estado, ao não ler nenhuma entrada, pode ir para outros estados
AFN – Autômatos Finitos Não-determinísticos
*Em inglês: NFA – Nondeterministic Finite Automaton
• Processamento de sequências
1. M1
M1 reconhece
a sequênciaaaa
AFN – Autômatos Finitos Não-determinísticos
a a a aaa é processada por M1
q0 q0 q0 q0 M1 não termina em estado final
a a a aaa não é inteiramente
q0 q0 q1 ? processada por M1
a a a aaa é processada por M1
q0 q0 q0 q1 M1 termina em estado final
q0 q1
a,b
a
• Processamento de sequências
1. M1
M1 não reconhece
a sequência ab
AFN – Autômatos Finitos Não-determinísticos
a b ab é processada por M1
q0 q0 q0 M1 não termina em estado final
a b ab não é não é inteiramente
q0 q0 ? processada por M1
q0 q1
a,b
a
• Processamento de sequências
– Um AFN M reconhece uma sequência de entrada α
se existe alguma linha de processamento tal que M
leia toda a sequência e termine em um estado final
AFN – Autômatos Finitos Não-determinísticos
• Linguagens reconhecidas por AFN’s
1. M1
Notação: L(M1) = L( (avb)*a )
AFN – Autômatos Finitos Não-determinísticos
q0 q1
a,b
a
• Linguagens reconhecidas por AFN’s
– Equivalência entre os AFN’s e os AFD’s
• Os AFD’s possuem a mesma capacidade de processamento dos AFD’s.
Ou seja:
• Os AFN’s reconhecem linguagens regulares
– Prova
• Todo AFN pode ser convertido em um AFD
AFN – Autômatos Finitos Não-determinísticos
• Convertendo AFN’s em AFD’s
– 1º Passo: grafo → tabela do AFN
• Exemplo: M1 → M1’
AFN – Autômatos Finitos Não-determinísticos
q0 q1
a,b
a
AFN a b
> q0 {q0,q1} {q0}
* q1 ∅ ∅
Marca de estado final
• Convertendo AFN’s em AFD’s
– 2º Passo: tabela do AFN → tabela do AFD
• Exemplo: M1 → M1’
AFN – Autômatos Finitos Não-determinísticos
AFN a b
> q0 {q0,q1} {q0}
* q1 ∅ ∅
AFD a b
> e0 = {q0} e1 = {q0,q1} e0 = {q0}
* e1 = {q0,q1} e1 = {q0,q1} e0 = {q0}
Estado final do AFD:
contém q1 (estado final do AFN)
• Convertendo AFN’s em AFD’s
– 3º Passo: tabela do AFD → grafo do AFD 
• Exemplo: M1 → M1’
L(M1’) = L ( (avb)*a )
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 e1 e0
* e1 e1 e0
M1’
• Processamento de sequências
2. M2
M2 reconhece
a sequência baa
AFN – Autômatos Finitos Não-determinísticos
b a a baa é processada por M2
q0 q0 q0 q1 M1 não termina em estado final
b a a aaa é processada por M2
q0 q0 q1 q2 M1 termina em estado final
q0
a,b
a
q2q1
a
• Convertendo AFN’s em AFD’s
– 1º Passo: grafo → tabela do AFN
• Exemplo: M2 → M2’
AFN – Autômatos Finitos Não-determinísticos
q0
a,b
a
q2q1
a
AFN a b
> q0 {q0,q1} {q0}
q1 {q2} ∅
* q2 ∅ ∅
• Convertendo AFN’s em AFD’s
– 2º Passo: tabela do AFN → tabela do AFD
• Exemplo: M2 → M2’
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 = {q0} e1 = {q0,q1} e0 = {q0}
e1 = {q0,q1} e2 = {q0,q1,q2} e0 = {q0}
* e2 = {q0,q1,q2} e2 = {q0,q1,q2} e0 = {q0}
AFN a b
> q0 {q0,q1} {q0}
q1 {q2} ∅
* q2 ∅ ∅
• Convertendo AFN’s em AFD’s
– 3º Passo: tabela do AFD → grafo do AFD 
• Exemplo: M2 → M2’
L(M2’) = L ( (avb)*aa )
AFN – Autômatos Finitos Não-determinísticos
AFD a b
> e0 e1 e0
e1 e2 e0
* e2 e2 e0
M2’
• Exercícios
– Converta os AFN’s abaixo para seus AFD’s equivalentes
a) M3 b) M4
AFN – Autômatos Finitos Não-determinísticos
AFN – Autômatos Finitos Não-determinísticos
• Referência
– HOPCROFT, John E; MOTWANI, Rajeev; ULMAN, Jeffrey D. Introdução 
à teoria dos autômatos, linguagens e computação.
Rio de Janeiro: Elsevier, 2002.
Obrigado!
• Linguagens Não–Regulares
• Autômatos de Pilha (Máquinas de pilha)
Aula 8
• Linguagem regular
– Caracterizada por expressão regular
– Reconhecida por um AFD (e também por AFN)
• Linguagens não–regulares
– Existem linguagens que não são regulares?
Linguagens Não–regulares
• Exemplos
Linguagens Não–regulares
L1 é regular ⇒ a(avb)* ou AFD
L2 é regular ⇒ a(ab)* ou AFD
L3 é regular ⇒ expr. regular
ou AFD
L4 não é regular, ou L4 é não–regular
‒ L1 = Sequências iniciadas por a
‒ L3 = Sequências com quantidade par
de a’s e quantidade par de b’s
‒ L2 = { a, aab, aabab, aababab, ... }
‒ L4 = { λ, ab, aabb , aaabbb, aaaabbbb, ... }
• L = { λ, ab, aabb , aaabbb, aaaabbb, ... } = { anbn | n ≥≥≥≥ 0 }
ou simplesmente,
L = anbn
onde a0 = λ
a1 = a
a5 = aaaaa
Linguagens Não–regulares
‒ Definição
a0 = λ
an = a⋅an–1para n ∈∈∈∈ IN*
• A linguagem anbn é não–regular
– Não existe expressão regular que a caracterize
– Não existe AFD que a reconheça
Linguagens Não–regulares
• A linguagem anbn é não–regular
– Não existe 
AFD que a
reconheça!
Linguagens Não–regulares
Seria necessário um número 
infinito de estados!
• Limitação dos Autômatos Finitos
– A “memória” está nos estados
– Conjunto finito de estados = memória finita
• Toda linguagem que necessite de
memória indeterminada não pode ser
reconhecida por autômatos finitos
Linguagens Não–regulares
• Exemplos
Linguagens Não–regulares
L1 é não–regular
L2 é não–regular
‒ L1 = a
nbn = { anbn | n ≥≥≥≥ 0 }
‒ L2 = a
nbn+1 = { b, abb, aabbb, aaabbbb, ... }
‒ L3 = a
nb2n = { λ, abb, aabbbb, ... } L3 é não–regular
‒ L5 = Sequências com quantidade de a’s
igual à quantidade de b’s
L4 = (ab)* é regular‒ L4 = (ab)
n = { λ, ab, abab, ababab, ... }
L5 é não–regular
• Exemplos
Linguagens Não–regulares
L6 = a*b* é regular
L7 é não–regular
‒ L6 = { a
nbm | n,m ≥≥≥≥ 0 }
‒ L7 = Palíndromos com a’s e/ou b’s
Exemplos: λ, a, bb, aba, abba, babbab, ... }
‒ L9 = Sequências com mais a’s do que b’s
L8 = a*(bb)* é regular‒ L8 = { a
nb2m | n,m ≥≥≥≥ 0 }... }
L9 é não–regular
• Limitação dos autômatos finitos
– Memória limitada
• Solução
– Adicionar memória “externa” aos estados
Autômatos de Pilha
• Autômato de pilha
– Conjunto finito de estados
– Pilha como memória auxiliar
• Estrutura linear “LIFO”
• Símbolo Z0: início da pilha
Autômatos de Pilha
topo → b
b
a
Z0
• Autômato de pilha
– A cada passo, o estado atual
• Lê um símbolo da entrada
• Manipula a pilha
• Vai para próximo estado
Autômatos de Pilha
topo → b
b
a
Z0
• Exemplo
– Reconhecer linguagem anbn
processar aaaabbbb
• Estado q0 lê símbolo a
empilha símbolo a
• Estado q1 lê símbolo b
desempilha símbolo a
• Fim do processamento
Pilha vazia! ⇒ sequência reconhecida!
Autômatos de Pilha
Z0
a
a
a
a
• Resumo: reconhecer linguagem anbn
– Estado q0 empilha a’s
Estado q1 desempilha a’s
• Simplificação no autômato de pilha
– A cada passo, o estado atual qatual
– Lê símbolo i da entrada
– Desempilha um símbolo d
– Empilha um símbolo e
– Vai para próximo estado qprox
Autômatos de Pilha
• Reconhecimento da linguagem anbn
• Estado q0 apenas empilha a’s ⇒ antes desempilha alguma coisa
tem que empilhar de volta
Estado q1 apenas desempilha a’s ⇒ depois empilha “nada” (ε)
• Solução
Autômatos de Pilha
• Examinando o autômato que reconhece a linguagem anbn
• q0 , lendo a, se desempilhar Z0
empilha Z0 depois a
e continua em q0
• q0 , lendo a, se desempilhar a
empilha a depois a
e continua em q0
• q0 , lendo b, se desempilhar a
empilha ε
e vai para q1
Autômatos de Pilha
• Examinando o autômato que reconhece a linguagem anbn
• q1 , lendo b, se desempilhar a
empilha ε
e continua em q1
• q1 , lendo ε, se desempilhar Z0
empilha Z0
e continua em q0
• q0 , lendo ε, se desempilhar Z0
empilha Z0
e vai para q2 (estado final)
Autômatos de Pilha
• Reconhecimento da linguagem anbn
– Processando aabb
– Último estado: q2 →→→→ sequência reconhecida
Autômatos de Pilha
ESTADO
ATUAL
ENTRADA TRANSIÇÃO
PILHA APÓS
TRANSIÇÃO
q0 aabb (q0,a,Z0)→(q0,aZ0) aZ0
q0 abb (q0,a,a)→(q0,aa) aaZ0
q0 bb (q0,b,a)→(q1,ε) aZ0
q1 b (q1,b,a)→(q1,ε) Z0
q1 λ (q1,ε,Z0)→(q2,Z0) Z0
• Reconhecimento da linguagem anbn
– Transições: (qatual, i, d) →→→→ (qprox,e)
• i símbolo lido
• d símbolo desempilhado
• e sequência empilhada, símbolo após símbolo
Autômatos de Pilha
• Reconhecimento da linguagem anbn a,x,ax
– Processando aab
– Estado final: q1 →→→→ sequência não reconhecida
Autômatos de Pilha
ESTADO
ATUAL
ENTRADA TRANSIÇÃO
PILHA APÓS
TRANSIÇÃO
q0 aab (q0,a,Z0)→(q0,aZ0) aZ0
q0 ab (q0,a,a)→(q0,aa) aaZ0
q0 b (q0,b,a)→(q1,ε) aZ0
q1 λ (q1,ε,a)→ ??? aZ0
• Reconhecimento da linguagem anbn
– Processandoλ
– Último estado: q2 →→→→ sequência reconhecida
Autômatos de Pilha
ESTADO
ATUAL
ENTRADA TRANSIÇÃO
PILHA APÓS
TRANSIÇÃO
q0 λ (q0,ε,Z0)→(q2, Z0) Z0
• Exercícios
– Desenhar autômatos de pilha que reconheçam as linguagens
anbn+1 anb2n anb2n anban
Sequências que tenham mais a’s do que b’s
Palíndromos 
– Para estudar
• HOPCROFT, John E; MOTWANI, Rajeev; ULMAN, Jeffrey D. Introdução à teoria 
dos autômatos, linguagens e computação.
Rio de Janeiro: Elsevier, 2002.
Autômatos de Pilha
Obrigado!
• Linguagens Não–Regulares
• Máquina de Turing
– Referência
• MIDIATECA do AVA: Apostila II – Máquina de Turing,
que é um trecho do livro:
GERSTING, J. L. Fundamentos matemáticos para a ciência da 
computação. 5ª ed., Rio de Janeiro: LTC, 2004. 
Aula 9
• Limitações do Autômato de pilha
– A linguagem { anbnan | n ≥≥≥≥ 0 } não pode ser reconhecida
pela Máquina de Pilha*
• A limitação reside na inserção/remoção apenas no topo da pilha
– Solução
Máquina de Turing
*A adoção de duas pilhas resolveria o problema, mas este
seria outro autômato, equivalente à MT
Linguagens Não-regulares
• Características da Turing Machine
– Memória auxiliar
• Bidirecionalmente infinita
• Cabeça de Leitura/Escrita: Acesso sequencial – movimentação da cabeça 
Leitura/Escrita em qualquer posição
Máquina de Turing
. . . b a b b a b b b . . .
↑↑↑↑
Cabeça de Leitura/Escrita
• Características da Turing Machine
– Conjunto finito de estados
• E = { 0, 1, 2, 3, ..., k }
• Estado inicial: se não indicado, será o estado 0
• Durante o processamento, a MT vai mudando de estados
Máquina de Turing
Estado atual
. . . b a b b a b b b . . .
↑↑↑↑
2
. . . b a b b a b b b . . .
↑↑↑↑
0
• Características da Turing Machine
– Antes do processamento
• No início, a memória é “zerada” com espaço em branco b
• A sequência de entrada é colocada na memória, em qualquer posição
• Cabeça de leitura/gravação posicionada no símbolo mais a esquerda
• Estado atual = no estado inicial
Máquina de Turing
Estado inicial
• Transições em uma MT
– Formato das instruções
• Estado atual
• Símbolo lido da memória
• Símbolo escrito na memória
• Movimento da cabeça para Esquerda ou Direita
• No próximo passo, a MT vai para próximo estado
Máquina de Turing
• Exemplo
– Sendo o estado atual 2
• Se símbolo a for lido
escreve x
movimenta cabeça para Direita
vai para estado 3
• Se símbolo b for lido
escreve y
movimenta cabeça para Esquerda
vai para estado 4
Máquina de Turing
• Exemplo
– Notação por quíntuplas
(e, i, i’, e’, d)
• e: estado atual
• i: símbolo lido
• i’, símbolo escrito
• e’: próximo estado
• d: deslocamento
Máquina de Turing
(2,a,x,3,D)
(2,b,y,4,E)
• Exemplo
– Passo atual
– Próximo passo
Máquina de Turing
(2,a,x,3,D)
(2,b,y,4,E)
. . . b a b b a b b b . . .
↑↑↑↑
2
. . . b a y b a b b b . . .
↑↑↑↑
4
• Exemplo 27
– Apostila II – Máquina de Turing,
pág. 471 e i i’ e’ d
Máquina de Turing
• Processamento
– Apostila II – Máquina de Turing, pág. 472
sequência de entrada 0110
– Configuração inicial
Máquina de Turing
. . . b 0 1 1 0 b b b . . .
↑↑↑↑
0
• Exemplo
– Configuração inicial
– Configuração final
Máquina de Turing
. . . b 0 1 1 0 b b b . . .
↑↑↑↑
0
. . . . . .. . . b 1 0 0 0 0 b b . . .
↑↑↑↑
1
• Processamento
– Configuração inicial: sequência de entrada α = 0110
– Configuração final: sequência de saída β = 10000
Máquina de Turing
. . . b 0 1 1 0 b b b . . .
↑↑↑↑
0
. . . b 1 0 0 0 0 b b . . .
↑↑↑↑
1
• Exercício: Qual a função efetuada pela MT?
– Configuração inicial: α = 1011
– Configuração final: β =
Máquina de Turing
. . . b 1 0 1 1 b b b . . .
↑↑↑↑
0
. . . . . .
10110
MT: (0,0,0,0,D)
(0,1,1,0,D)
(0,b,0,1,D)
. . . b 1 0 1 1 0 b b . . .
↑↑↑↑
1
• Qual a função efetuada pela MT?
– Configuração inicial: α = 1011
– Configuração final: β = 10110
– Qual a função efetuada por esta MT?
Máquina de Turing
= (11)10
= (22)10
R.: f(x) = 2x, ou seja
computa o dobro do valor da entrada
(em formato binário)
MT: (0,0,0,0,D)
(0,1,1,0,D)
(0,b,0,1,D)
• Exercício: Qual a função efetuada pela MT?
– Configuração inicial: α = 10110
– Configuração final: β =
Máquina de Turing
. . . b 1 0 1 1 0 b b . . .
↑↑↑↑
0
. . . . . .
10110I
MT: (0,0,0,0,D)
(0,1,1,1,D)
(1,0,0,1,D)
(1,1,1,0,D)
(0,b,P,2,D)
(1,b,I,2,D)
. . . b 1 0 1 1 0 I b . . .
↑↑↑↑
2
• Qual a função efetuada pela MT?
– Configuração inicial: α = 10110
– Configuração final: β =
– Resposta: verifica a paridade dos 1’s,
acrescentado ao final da
sequência: P = paridade par
I = paridade ímpar
Máquina de Turing
10110I
MT: (0,0,0,0,D)
(0,1,1,1,D)
(1,0,0,1,D)
(1,1,1,0,D)
(0,b,P,2,D)
(1,b,I,2,D)
• Exercícios 8.3
– Apostila II – Máquina de Turing, pág. 483 em diante
– Para estudar
• MIDIATECA do AVA: Apostila II – Máquina de Turing,
que é um trecho do livro:
GERSTING, J. L. Fundamentos matemáticos para a ciência da 
computação. 5ª ed., Rio de Janeiro: LTC, 2004. 
Máquina de Turing
Obrigado!