Resumo de Autômatos e Computabilidade

Prévia do material em texto

Capítulo 0 
 
Teoria da Complexidade: 
Classificar os problemas em fáceis e difíceis. 
 
Teoria da Computabilidade: 
Classificar os problemas em solúveis ou não. 
 
Conjunto: 
É um grupo de objetos representados como uma unidade. Podem conter qualquer tipo 
de objeto e até mesmo outros conjuntos. 
● 7 ∈ {7,21,57} = 7 pertence ao conjunto. 
● 8 ∉ {7,21,57} = 8 não pertence ao conjunto. 
● A ⊆ B = A é subconjunto de B se todos os elementos de A pertencerem a B. 
● A ⊊ B = A é subconjunto próprio de B se A é subconjunto de B e não é igual a B. 
● Ø = Conjunto vazio. 
● AUB = Combinação de todos elementos de A e B em um único conjunto. 
● A∩B = Conjunto de elementos presentes em A e B. 
● AxB = Produto Cartesiano ou Produto Cruzado = Conjunto de todos os pares onde o 
primeiro elemento é membro de A e o segundo é membro de B. 
 
Elementos / Membros: 
São os objetos em um conjunto. 
 
Multiconjunto: 
Leva­se em consideração o número de ocorrências dos membros. Em um conjunto, o 
número de ocorrências não muda o conjunto. 
 
 
Sequência: 
É uma lista de objetos na mesma ordem. Em um conjunto, a ordem não importa, mas na 
sequência sim. Usualmente, se escreve entre parênteses.  
● (7,21,57) ≠ (21,7,57) 
● {7,21,57} = {7,7,7,21,57} 
 
Uplas: 
São sequências finitas. Uma sequência com k elementos é uma k­upla. Então (7,21,57) 
é uma 3­upla. Uma 2­upla também é chamada de ​par​. 
 
 
 
 
Conjunto das Partes: 
O conjunto das partes de A é o conjunto de todos os subconjuntos de A.  
Se A = {0,1}, o conjunto das partes de A = {Ø, {0}, {1}, {0,1}}. 
O conjunto com todos os pares cujos elementos são 0s e 1s = {(0,0), (0,1), (1,0), (1,1)}. 
 
 
Função / Mapeamento: 
Um objeto que estabelece uma relação entrada­saída. Também é chamada de 
mapeamento. Se ​�​(a) = b, dizemos que ​�​ mapeia a para b. 
● Domínio = Conjunto das possíveis entradas. 
● Contradomínio = Conjunto das saídas 
● �​: D⟶C = ​�​ é uma função com domínio D e contradomínio C 
● add​: ​ƶ x ƶ ​⟶ ​ƶ 
○ add​(2,2) = 4 
● Uma função que usa todos os elementos do contradomínio é dita ser ​sobre ​ o 
contradomínio. 
● Uma função com ​k​ argumentos é chamada função k­ária, e ​k​ é a ​aridade​ da função. 
Para k = 1, função unária; k = 2, função binária. 
● Notação infixa, o símbolo da função fica entre os argumentos: a + b. 
● Notação prefixa, o símbolo da função precede os argumentos: adi(a,b). 
 
 
Propriedade / Predicado: 
Função cujo contradomínio é {Verdadeiro,Falso}. 
 
 
Relação de Equivalência: 
É um tipo especial de relação binária que captura a noção de 2 objetos sendo iguais em 
algum aspecto. Uma relação binária R só é de equivalência se: 
 
1. R é ​reflexiva para todo x, xRx;        
2. R é ​simétrica​ para todo x e y, xRy implica yRx  
3. R é ​transitiva ​para todo x, y, z, zRy e yRz implica xRz. 
 
 
Grafos: 
É um conjunto de pontos com linhas ligando alguns dos pontos. 
● Se V é o conjunto de nós de G e E é o conjunto de arestas, G = (V,E). 
 
Nós / Vértices: 
São os pontos. 
 
Arestas: 
São as linhas. 
 
Grau do nó: 
É o número de arestas em um nó. Entre dois nós só é permitido no máximo uma aresta. 
O par (i,j) representa a aresta que conecta i e j. (i,j) e (j,i) são a mesma coisa. 
 
Subgrafo: 
G é um subgrafo de do grafo H se os nós de G formam um subconjunto dos nós de H 
juntamente com as arestas correspondentes. 
 
Caminho: 
É uma seqüência de nós conectados por arestas. 
 
Caminho simples: 
Um caminho que não repete nenhum nó. 
 
Caminho direcionado: 
Todas as setas apontam na mesma direção que seus passos. Um grafo direcionado é 
fortemente conexo ​se um caminho direcionado conecta cada dois nós. 
 
Grafo Conexo: 
Cada dois nós têm um caminho entre eles. 
 
Ciclo: 
Caminho que começa e termina no mesmo nó. 
 
● Ciclo Simples: 
○ Possui pelo menos 3 nós e repete somente o primeiro e o último nós. 
 
Grafo direcionado: 
Se possui setas ao invés de linhas. O número de setas apontando a partir de um dado 
nós é o ​grau de saída ​desse nó. O número de setas apontando para o nó é o ​grau de 
entrada​. 
 
 
Árvore: 
Um grafo é uma árvore se ele é conexo e não tem ciclos simples. 
 
Raiz: 
Nós de grau 1 em uma árvore, exceto a raiz, são as folhas. 
Cadeias e Linguagens: 
Cadeias de caracteres são blocos básicos fundamentais em ciência da computação. 
 
Alfabeto: 
É qualquer conjunto finito não­vazio. 
 
Símbolos: 
São membros do alfabeto. 
 
Cadeia sobre um alfabeto: 
É uma sequência finita de símbolos daquele alfabeto. Por exemplo, Se ∑1= {0,1}, então 
01001 é uma cadeia sobre ∑1. 
∑* = conjunto de todas as cadeias sobre ∑, incluindo ε. 
 
Linguagem: 
É um conjunto de cadeias sobre um alfabeto. 
● L(M) = A: A é a Linguagem da máquina M/ M reconhece A. 
 
Comprimento: 
Se w é uma cadeia sobre ∑2, o comprimento de w, “|w|”, é o número de símbolos que 
ele contém. Cadeia de comprimento zero é chamada ​cadeia vazia ​e é escrita “ε”. 
 
Reverso: 
É a cadeia obtida escrevendo w na ordem inversa (i.e., wn, wn­1, …, w1). 
 
Subcadeia: 
z é subcadeia de w se z aparece consecutivamente dentro de w. Por exemplo, lele é 
uma subcadeia de paralelepipedo. 
 
Concatenação: 
Temos a cadeia x de comprimento m e a cadeia y de comprimento n. A concatenação 
seria: x1...xmy1...yn. Uma concatenação de uma cadeia com si própria várias vezes é 
denotada com expoente, xˆk = xxxx... (k vezes). 
 
Ordenação Lexicográfica: 
a ordenação de todas as cadeias sobre o alfabeto {0,1} é (ε, 0, 1, 00, 01, 11, 000, …). 
 
P(∑*) = Conjunto de todas as linguagens sobre um alfabeto ∑.  
 
 
Lógica Booleana 
 
● Conjunção (e) = ∩ 
● Disjunção (ou) = U 
● Operandos: P∩Q, P e Q são operandos da operação. 
● XOR = ⊕ 
● Igualdade = ↔ 
● Implicação = → 
 
● P ∨ Q = ¬(¬P ∧ ¬Q) 
● P → Q = ¬P ∨ Q 
● P ↔ Q = (P → Q) ∧ (Q → P ) 
● P ⊕ Q = ¬(P ↔ Q) 
 
Lei distributiva:  
P ∧(Q∨R) = (P ∧Q)∨(P ∧R) 
 
 
Definições, Teoremas e Provas 
Uma prova bem escrita é uma seqüência de enunciados. 
 
Definições: 
Descrevem os objetos e noções que usamos. Precisão na definição é essencial, 
deixando claro o que constitui um objeto e o que não o constitui ao definí­lo. 
 
Enunciados Matemáticos: 
Expressa que algum objeto tem uma certa propriedade. Pode ou não ser verdadeiro, 
mas deve ser preciso, sem haver ambiguidade sobre seu significado. 
 
Prova: 
É um argumento lógico convincente de que o enunciado é verdadeiro. Um matemático 
requer prova além de qualquer dúvida. 
 
Teorema: 
É um enunciado matemático demonstrado verdadeiro. 
 
Lema: 
Enunciados que provamos que são interessantes somente por ajudar na prova de um 
outro enunciado mais significativo. 
 
Corolário: 
Enunciado deduzido a partir de um outra (anteriormente) demonstrada, fazendo com 
que um conhecimento seja acrescentado a mesma. 
 
Capítulo 1 
 
1.1 Autômatos Finitos 
 
● Estado Inicial: ​Indicado pela seta que aponta a partir do nada. 
● Estado de Aceitação: ​ Duplo círculo. 
● Transições: ​Setas saindo de um estado para outro. 
● Saída Aceita: ​Se ao ler o último símbolo, o autômato está no estado de aceitação. 
● Saída Rejeita: ​Se não está no estado de aceitação. 
● Função de Transição (​δ​): ​Define as regras de movimentação. 
○ ઠ(x,1) = y :  Se o autômato está em x quando lê 1, ele vai para y. 
 
Definição Formal de AFD: 
É uma 5­upla (Conjunto de estados, alfabeto de entrada, regras para movimentação, 
estado inicial e estados de aceitação; (Q,∑,δ,q0,F)) onde: 
● Q = o conjunto finito conhecido como os ​estados​; 
● ∑ = conjunto finito chamado de ​alfabeto; 
● δ : Q x ∑ → Q = ​função de transição; 
● q0 ∈ Q = ​estado inicial; 
● F ⊆ Q = ​conjunto de estados de aceitação; 
 
Um autômato pode reconhecer várias cadeias, mas sempre reconhece somenteuma 
linguagem. Mesmo não aceitando cadeia nenhuma, ela vai reconhecer a linguagem vazia Ø. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de Computação: 
Se M = (Q,∑,δ,q0,F)), suponha que ​w = w1w2w3...wn​ seja uma cadeia onde cada ​wi​ é 
membro do alfabeto ∑. M aceita w se existe uma seqüência de estados r0, r1, …, rn em Q com 
3 condições: 
 
1. r0 = q0 
➢ A máquina começa no estado inicial. 
2. δ(ri, wi+1) = ri+1 para i = 0, …, n­1 
➢ A máquina vai de estado para estado conforme a função de transição. 
3. rn ∈ F 
➢ A máquina aceita sua entrada se ela termina num estado de aceitação. 
 
 
 
Linguagem Regular: 
Se algum automato finito a reconhece, a linguagem é regular. 
Dizemos que M reconhece a linguagem A se A = {w | w M aceita w}. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Operações Regulares: 
Sejam A e B linguagens, as operaões regulares são 
 
● União: ​AUB = {x | x ∈ A ou x ∈ B} 
● Concatenação: ​A ० B = {xy | x ∈ A e y ∈ B} 
● Estrela: ​A* = {x1x2...xk | k � 0 e cada xi ∈ A} 
 
Como exemplo, suponha que o alfabeto ​∑ seja o padrão 26 letras {a, b, c,…, z} e​ as 
linguagens são A = {legal, ruim} e B = {garoto, garota}. 
● AUB = {legal, ruim, garoto, garota} 
● A ० B = {legalgaroto, legalgarota, ruimgaroto, ruimgarota} 
● A* = {ε, legal, ruim, legallegal, legalruim, ruimlegal, ruimruim, legallegallegal, 
legallegalruim, legalruimlegal, legalruimruim,...} 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Uma coleção de objetos é ​fechada​ sob alguma operação se, aplicando a operação, 
recebe­se um objeto ainda na coleção. Por exemplo, seja N = {1, 2, 3, …} o conjunto dos 
números naturais, N é fechado sob multiplicação pois para qualquer x e y em n, x☓y também 
está em N. O mesmo não o corre para divisão pois ½ não está em N, então N não é fechado 
sob divisão. 
A coleção de linguagens regulares é fechada sob as 3 operações regulares.  
 
 
Teorema 1.25 
A classe  de linguagens regulares é fechada sob a operação de união. Ou, se A1 e A2 
são linguagens regulares, o mesmo acontece com A1UA2. 
 
Prova por construção​: 
Construir um autômato M que reconheça A1UA2 a partir de M1 e M2 sabendo que M1 
reconhece A1 e M2 reconhece A2. M funciona simulando M1 e M2 e aceita se uma das 
simulações aceita. Simular as duas ao mesmo tempo e guardar o estado em que cada máquina 
se encontra se ela tivesse lido até esse ponto da entrada. O número de estados possíveis  se 
M1 tem k1 estados e M2 tem k2 estados é k1 x k2, que é o número de estados de M. 
Supomos que M1 =(Q1,∑,δ1,q1,F1)) reconhece A1 e M2 = (Q2,∑,δ2,q2,F2)) reconhece 
A2, a construção de M = (Q,∑,δ,q0,F)) se dará por: 
1. Q = {(r1, r2) | r1 ∈ Q1 e r2 ∈  Q2} 
○ É o produto cartesiano de todos os pares de estados. 
2. ∑ é o mesmo para M1 e M2. E mesmo com alfabetos  diferentes ∑1 e ∑2, o teorema 
permanece verdadeiro pois a prova seria modificada para tornar ∑ = ∑1 U ∑2. 
3. δ((r1, r2), a) = (δ1(r1, a), δ2(r2, a)) para cada (r1, r2) ∈ Q e cada ​a ​ ∈ ∑ 
4. q0 = (q1,q2) 
5. F = {(r1, r2) | r1 ∈ F1 ou r2 ∈ F2} 
○  É o conjunto de pares onde um dos membros é o estado de aceitação de M1 ou 
M2. É o mesmo que dizer que F = (F1 x Q2) U (Q1 X F2) 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
1.2 Não­determinismo 
 
● Determinismo​: acontece quando a máquina está em um dado estado e lê o próximo 
símbolo de entrada e sabemos qual será o próximo estado. 
● Não­Determinismo​: Várias escolhas podem existir para o próximo estado. É uma 
generalização de determinismo, ou seja, todo autômato determinístico é um autômato 
não­determinístico. 
 
AFD​: Autômato Finito Determinístico 
● Todo estado sempre tem exatamente uma seta de transição saindo para cada símbolo 
no alfabeto. 
AFN​: Autômato Finito Não­Determinístico 
● Tem possibilidades de seguir caminhos diferentes com um mesmo símbolo no alfabeto 
para um estado dado. 
● Divide­se em cópias de si mesmo para seguir pelos possíveis caminhos em paralelo e 
“morre” se o próximo símbolo de entrada não aparece sobre qualquer seta que saia do 
estado atual. 
● Se qualquer cópia estiver em um estado de aceitação ao final da entrada, o AFN aceita 
a cadeia. 
● “ε”: Se um estado com um símbolo ε sobre uma seta saindo for encontrado, a maquina 
divide­se em múltiplas cópias sem ler qualquer entrada, uma cada seguindo uma das 
setas saindo rotuladas com ε e uma permanece no estado corrente. 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de AFN: 
A diferença entre a definição de AFD e AFN é basicamente a função de transição. No 
AFD, a função de transição toma um estado e um símbolo de entrada e produz o próximo 
estado. No AFN, a função de transição toma um estado e um símbolo de entrada ou a cadeia 
vazia “ε” e produz um conjunto de próximos estados possíveis.  
Convencionamos que P(Q) é o ​conjunto das partes​ de Q, que é a coleção de todos os 
subconjuntos de Q. 
Para qualquer alfabeto ∑, escrevemos ∑ε como sendo ∑U{ε}. 
Então, um Autômato Finito Não­Determinístico é uma 5­upla (Conjunto de estados, 
alfabeto de entrada, regras para movimentação, estado inicial e estados de aceitação; 
(Q,∑,δ,q0,F)) onde: 
● Q = um conjunto finito de ​estados​; 
● ∑ = ​alfabeto finito; 
● δ : Q x ∑ε → P(Q) = ​função de transição; 
● q0 ∈ Q = ​estado inicial; 
● F ⊆ Q = ​conjunto de estados de aceitação; 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de Computação: 
Seja N = (Q,∑,δ,q0,F) um AFN e ​w​ seja uma cadeia do alfabeto ∑.  
N aceita w se w = ​w1w2w3...wn ​onde cada ​wi​ é membro do alfabeto ∑ε e existe uma seqüência 
de estados r0, r1, …, rn em Q com 3 condições: 
 
4. r0 = q0 
➢ A máquina começa no estado inicial. 
5. ri+1 ∈ δ(ri, wi+1), para i = 0, …, n­1 
➢ O estado ri +1 é um dos próximos estados permissíveis quando N está em ri e 
lendo wi+1. 
6. rn ∈ F 
➢ A máquina aceita sua entrada se o último estado é de aceitação. 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Equivalência de AFNs e AFDs 
 
AFNs e AFDs reconhecem a mesma classe de linguagens e descrever um AFN para 
uma linguagem é muitas vezes mais fácil que descrever um AFD para a mesma linguagem. 
Dois autômatos são ​equivalentes​ se eles reconhecem a mesma linguagem. 
 
Teorema 1.39 
Todo autômato finito não­determinístico tem um autômato finito determinísto 
equivalente. 
 
Prova​: 
Se k é o número de estados do AFN, ele tem  subconjuntos de estados, cada um2k  
correspondendo a uma das possibilidades que o AFD tem. Então esse AFD que simula o AFN 
terá  estados.2k  
Seja N = (Q,∑,δ,q0,F) o AFN que reconhece  alinguagem A, vamos construir o AFD M = 
(Q’,∑,δ’,q0’,F’) que também reconhece A. 
 
1. Q’ = P(Q) 
○ Todo estado de M é um conjunto de estados de N. 
2. δ’(R,a) = δ(r,a), para R ∈ Q’ e a ∈ ∑∪
 
r∈R
 
○ Quando M lê símbolo “a” no estado R, ele mostra para onde ​a ​leva cada estado 
em R. Como cada estado pode ir para um conjunto de estados, temos que tomar 
a união de todos esses conjuntos. 
○ δ(r,a) significa a união dos conjuntos δ(r,a) para cada r em R.∪
 
r∈R
 
3. q0’ = {q0} 
○ M começa no estado correspondente à coleção contendo somente o estado 
inicial de N. 
4. F’ = {R ∈ Q’ | R contém um estado de aceitaçãode N} 
○ A máquina M aceita se um dos possíveis estados nos quais N poderia estar 
nesse ponto é um estado de aceitação. 
 
Essa prova foi construída no caso onde N não tem setas ε. Para a construção completa da 
prova considerando as setas ε, para qualquer estado R de M, definimos E(R) como a coleção 
de estados que podem ser atingidos a partir de R indo somente ao longo de setas ε, incluindo 
os membros de R. Então: 
 
E(R) = {q | q pode ser atingido a partir de cada elemento de R viajando ao longo de ­ ou 
mais setas ε} 
 
Com isso, temos que modificar a função de transição de M para ser possível caminhar sobre as 
setas ε e atingir estados substituindo δ(r,a) por E(δ(r,a)): 
 
δ’(R,a) = {q ∈ Q| q ∈ E(δ(r,a)) para algum r ∈ R} 
 
Também teremos que mudar o estado inicial de M para que o autômato também possa 
caminhar para os estados possíveis a partir do estado inicial de N ao longo de setas ε. Desse 
modo, mudamos q0’ para E({q0}). 
Então temos: 
 
● Q’ = P(Q) 
● ∑ = alfabeto 
● δ’(R,a) = {q ∈ Q| q ∈ E(δ(r,a)) para algum r ∈ R} 
● q0’ = E({q0}) 
● F’ = {R ∈ Q’ | R contém um estado de aceitação de N} 
 
 
Corolário 1.40 
 
Uma linguagem é regular se e somente se algum AFN a reconhece. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Minimização de AFDs 
 
2 estados são equivalentes se, para qualquer entrada a partir desses estados, o 
resultado é o mesmo (aceita ou rejeita). 
● 2 estados q e q’ são 0­equivalentes se ambos são estados de aceitação ou ambos são 
estados de não­aceitação. 
● 2 estados q e q’ são 1­equivalentes se δ(q, a) e δ(q’, a) são 0­equivalentes para todo a 
∈ ∑. 
● 2 estados q e q’ são 2­equivalentes se δ(q, a) e δ(q’, a) são 1­equivalentes para todo a 
∈ ∑. 
● 2 estados q e q’ são ​n­equivalentes​ se δ(q, a) e δ(q’, a) são (n­1)­equivalentes para todo 
a ∈ ∑. 
→ Então 2 estados são equivalentes se são n­equivalentes para todo n ​≥​ 0. 
 
Exemplo 1: 
 
 
 
0­Equivalentes: 
A = {q1, q2, q3, q4, q5, q6, q7, q8, q9} → aceitação 
B = {q10} → não­aceitação 
 
 
  q1  q2  q3  q4  q5  q6  q7  q8  q9  q10 
a  A  A  A  A  B  B  A  A  A  B 
b  A  A  A  A  A  A  A  A  B  B 
 
 
1­Equivalentes: 
A = {q1, q2, q3, q4, q7, q8} 
B = {q5, q6} 
C = {q9} 
D = {q10} 
 
 
  q1  q2  q3  q4  q7  q8  q5  q6  q9  q10 
a  A  B  A  B  A  B  D  D  A  D 
b  A  A  C  A  C  A  A  A  D  D 
 
2­Equivalentes: 
A = {q1} 
B = {q2, q4, q8} 
C = {q3, q7} 
D = {q5, q6} 
E = {q9} 
F = {q10} 
 
 
  q1  q2  q4  q8  q3  q7  q5  q6  q9  q10 
a  B  D  D  D  B  B  F  F  B  F 
b  C  C  C  C  E  E  C  C  F  F 
 
3­Equivalentes: 
A = {q1} 
B = {q2, q4, q8} 
C = {q3, q7} 
D = {q5, q6} 
E = {q9} 
F = {q10} 
● A tabela estabilizou nesse ponto, pois os 3­equivalentes são iguais aos 2­equivalentes. 
 
Com isso, podemos construir o AFD mínimo: 
 
 
  A  B  C  D  E  F 
a  B  D  B  F  B  F 
b  C  C  E  C  F  F 
 
 
 
 
 
Exemplo 2: 
 
  q1  q2  q3  q4  q5  q6  q7 
a  q2  q3  q3  q1  q3  q5  q6 
b  q1  q4  q3  q7  q4  q7  q7 
 
0­Equivalentes: 
A = {q1} → aceitação 
B = {q2, q3, q4, q5, q6, q7} → não­aceitação 
 
 
  q1  q2  q3  q4  q5  q6  q7 
a  B  B  B  A  B  B  B 
b  A  B  B  B  B  B  B 
 
1­Equivalentes: 
A = {q1} 
B = {q2, q3, q5, q6, q7} 
C = {q4} 
 
 
  q1  q2  q3  q5  q6  q7  q4 
a  B  B  B  B  B  B  A 
b  A  C  B  B  C  B  B 
 
2­Equivalentes: 
A = {q1} 
B = {q2, q6} 
C = {q3, q5, q7} 
D = {q4} 
 
 
  q1  q2  q6  q3  q5  q7  q4 
a  B  C  C  C  C  B  A 
b  A  D  C  C  D  C  C 
 
 
3­Equivalentes: 
A = {q1} 
B = {q2, q5} 
C = {q3, q6} 
D = {q4} 
E = {q7} 
 
 
  q1  q2  q5  q3  q6  q4  q7 
a  B  C  C  C  B  A  C 
b  A  D  D  C  E  E  E 
 
4­Equivalentes: 
A = {q1} 
B = {q2, q5} 
C = {q3} 
D = {q4} 
E = {q6} 
F = {q7} 
 
 
  q1  q2  q5  q3  q4  q6  q7 
a  B  C  C  C  A  B  E 
b  A  D  D  C  F  F  F 
 
 
● A tabela estabilizou nesse ponto, pois os 4­equivalentes são iguais aos 3­equivalentes. 
 
Com isso, podemos construir o AFD mínimo: 
 
 
  A  B  C  D  E  F 
a  B  C  C  A  B  E 
b  A  D  C  F  F  F 
 
 
 
 
Exemplo 3: 
 
 
 
  q1  q2  q3  q4  q5  q6  q7  q8 
0  q2  q7  q1  q3  q8  q3  q7  q7 
1  q6  q3  q3  q7  q6  q7  q5  q3 
 
0­Equivalentes: 
A = {q3} → aceitação 
B = {q1, q2, q4, q5, q6, q7, q8} → não­aceitação 
 
 
  q1  q2  q8  q4  q5  q6  q7  q3 
0  B  B  B  A  B  A  B  B 
1  B  A  A  B  B  B  B  A 
1­Equivalentes: 
A = {q1, q5, q7} 
B = {q2, q3, q8} 
C = {q4, q6} 
 
 
  q1  q5  q7  q2  q3  q8  q4  q6 
0  B  B  A  A  A  A  B  B 
1  C  C  A  B  B  B  A  A 
 
2­Equivalentes: 
A = {q1, q5} 
B = {q2, q3, q8} 
C = {q4, q6} 
D = {q7} 
 
 
  q1  q5  q2  q3  q8  q4  q6  q7 
0  B  B  D  A  D  B  B  D 
1  C  C  B  B  B  D  D  A 
 
3­Equivalentes: 
A = {q1, q5} 
B = {q2, q8} 
C = {q3} 
D = {q4, q6} 
E = {q7} 
 
 
  q1  q5  q2  q8  q3  q4  q6  q7 
0  B  B  E  E  A  C  C  E 
1  D  D  C  C  C  E  E  A 
 
● A tabela estabilizou nesse ponto, pois os 3­equivalentes são iguais aos 2­equivalentes. 
 
 
Com isso, podemos construir o AFD mínimo: 
 
  A  B  C  D  E 
0  B  E  A  C  E 
1  D  C  C  E  A 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
FECHO SOB AS OPERAÇÕES REGULARES 
 
Provar não­deterministicamente as operações de união, concatenação e estrela. 
 
Teorema 1.45 
A classe das linguagens regulares é fechada sob a operação união. 
 
Prova​: 
A idéia é combinar dois AFNs N1 e N2 que aceitam as linguagens regulares A1 e A2 em 
um AFN N para provar que A1 U A2 é regular. O autômato N tem um novo estado inicial que 
ramifica para os estados iniciais de N1 e N2 com setas ε. Então a nova máquina caminha pelas 
duas máquinas não­deterministicamente para advinhar qual das duas aceita a entrada, se uma 
aceitar, N também aceita. 
 
N1 = (Q1,∑,δ1,q1,F1) reconhece A1. 
N2 = (Q2,∑,δ2,q2,F2) reconhece A2. 
N = (Q,∑,δ,q0,F) que reconhece A1 U A2 será: 
● Q = {q0} U Q1 U Q2 
○ É o novo estado q0 somado aos estados de N1 e N2. 
● q0 = q0 : Estado inicial de N 
● F = F1 U F2 
● δ é definido de mode que para qualquer q ∈ Q e qualquer ​a ​∈ ∑ε temos: 
δ(q,a) = { δ1(q,a) para q ∈ Q1 
  { δ2(q,a) para q ∈ Q2 
  { {q1,q2} para q = q0 e a = ε 
  { Ø para q = q0 e a ≠ ε 
 
 
Teorema 1.47 
A classe das linguagens regulares é fechada sob a operação concatenação. 
 
Prova​: 
Queremos provar que um autômato N formado a partir de N1 e N2 reconhece A1 ० A2. 
O estado inicial de N será o estado inicial de N1 e os estados de aceitação de N1 são ligados 
por setas ε ao estado inicial de N2. Os estados de aceitação de N serão os estados de 
aceitação de N2. 
 
N1 = (Q1,∑,δ1,q1,F1) reconhece A1. 
N2 = (Q2,∑,δ2,q2,F2) reconhece A2. 
N = (Q,∑,δ,q0,F) que reconhece A1 ० A2 será: 
 
● Q = Q1 U Q2 
● q0 = q1 : Estado inicial de N1 
● F = F2 
● δ é definido de mode que para qualquer q ∈ Q e qualquer ​a ​∈ ∑ε temos: 
δ(q,a) = { δ1(q,a) para q ∈ Q1 e q ∉ F1 
  { δ1(q,a) para q ∈ F1 e a ≠ ε 
  { δ1(q,a) U {q2} para q ∈ F1 e a = ε 
  { δ2(q,a) para q ∈ Q2 
 
 
Teorema 1.49 
A classe das linguagens regulares é fechada sob a operação estrela. 
 
Prova​: 
Temos uma linguagem regular A1 e queremos provar que A1* também é regular. O AFN 
N reconhecerá A1*. N pode ser construído como N1 com setas ε retornando ao estado inicial a 
partir dos estados de aceitação. E N também deve ser modificado para que aceite ε, que é 
sempre um membro de A*. Assim, adiciona­se um novo estado inicial que também é de 
aceitação e que tenha uma seta ε para o antigo estado inicial.N1 = (Q1,∑,δ1,q1,F1) reconhece A1. 
N = (Q,∑,δ,q0,F) que reconhece A1* será: 
 
● Q = Q1 U {q0} 
● q0 = q0 : Novo estado inicial 
● F = {q0} U F1 
● δ é definido de mode que para qualquer q ∈ Q e qualquer ​a ​∈ ∑ε temos: 
δ(q,a) = { δ1(q,a) para q ∈ Q1 e q ∉ F1 
  { δ1(q,a) para q ∈ F1 e a ≠ ε 
  { δ1(q,a) U {q1} para q ∈ F1 e a = ε 
  { {q1} para q = q0 e a = ε 
  { Ø para q = q0 e a ≠ ε 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­  
 
1.3 Expressões Regulares 
 
Podemos usar operações regulares para montar expressões descrevendo linguagens 
chamadas ​expressões regulares​, como por exemplo: 
 
● (0 U 1)0* = Uma linguagem constituída de todas as cadeias começando com 0 ou 1 e 
seguidas por um número qualquer de 0s. 
○ (0 U 1) = ({0} U {1}) : Conjuntos 0 e 1 = L = {0,1} 
○ 0* = {0}* = Todas as cadeias com qualquer número de 0s. 
○ O símbolo de concatenação (०) é omitido como o de multiplicação (x) em 
álgebra: (0 U 1)0* = (0 U 1) ० 0* 
 
Seja ∑ = {0,1}, a expressão regular ∑ = (0 U 1) descreve a linguagem constituída de todas as 
cadeias de comprimento 1 sobre esse alfabeto e ∑* descreve uma linguagem que constituída 
de todas as cadeias sobre ∑. ∑*1 contém todas as cadeias terminadas em 1. (0∑*)U(∑*1) 
consiste de todas as cadeias que começam com 0 e terminam com 1. 
 
Seqüência de operandos correta a menos que parênteses sejam usados mudando a ordem: 
1. Estrela 
2. Concatenação 
3. União 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de Uma Expressão Regular 
 
 
R é uma expressão regular se R for: 
1. a para algum a no alfabeto ∑ = linguagem {a}, 
2. ε = linguagem {ε}, 
○ Linguagem contendo uma única cadeia, a cadeia vazia. 
3. Ø = linguagem vazia, 
○ Linguagem que não contém nenhuma cadeia. 
4. (R1 U R2) onde R1 e R2 são expressões regulares, 
5. (R1 ० R2) onde R1 e R2 são expressões regulares, ou  
6. (R1*) onde R1 é uma expressão regular. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplos: 
 
● R+ é a abreviação de RR*. Ou seja, R* tem todas as cadeias que são 0 ou mais 
concatenações de cadeias de R, e R+ tem todas as cadeias que resultam de 1 ou mais 
concatenações de cadeias de R. 
○ R+ U ε = R*. 
○ L(R) = linguagem que descreve a expressão regular R. 
● 0*10* = {w | w contém um único 1} 
● (0U1)* = {0, 1, 00, 01, 10, 11, …..} 
● (abUa)* = {ab, a, abab, aba, aab, aa, …..} 
● ∑*1∑* = {w | w tem pelo menos um símbolo 1} 
● ∑*001∑* = {w | w contém a subcadeia 001} 
● 1*(01+)* = {w | todo 0 em w é seguido por pelo menos um 1} 
● (∑∑)* = {w | w é uma cadeia com comprimento par} 
● (∑∑∑)* = {w | o comprimento de w é um múltiplo de 3} 
● 01 U 10 = {01, 10} 
● 0∑*0 U 1∑*1 U 0U1 = {w | w começa e termina com o mesmo símbolo} 
● (0 U ε)1* = 01* U 1* = {w | w contém um 0 ou ε antes de toda cadeia de 1*} 
● (0 U ε)(1 U ε) = {ε, 0, 1, 01} 
● 1*Ø = Ø 
○ Conjunto vazio concatenado com qualquer conjunto é um conjunto vazio 
● Ø* = {ε} 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Teorema 1.54 
Uma linguagem é regular se e somente se uma expressão regular a descreve. 
 
Lema 1.55 
Se uma linguagem é descrita por uma expressão regular, então ela é regular. 
 
Prova​: 
O David eh meu heroi! A prova é feita a partir dos 6 casos na descrição formal de 
expressões regulares. Constrói­se um AFN para cada um dos casos. 
 
Lema 1.60 
Se uma linguagem é regular, então ela é descrita por uma expressão regular. 
 
Prova​: 
Se A é uma linguagem regular, então uma expressão regular a descreve. Vamos utilizar 
um AFNG, ​Autômato Finito Não­Determinístico Generalizado. ​ Convertemos AFDs em 
AFNGs e depois, AFNGs em expressões regulares. 
 
AFNG: 
São AFNs cujas setas de transição podem quaisquer expressões regulares como 
rótulos. Ele lê blocos de símbolos da entrada. Suas características são: 
● O estado inicial tem setas de transição para todos os estados mas não recebe seta de 
estado nenhum. 
● Só existe um estado de aceitação no qual chegam setas de todos os estados e dele não 
sai nenhuma seta. Não pode ser o mesmo que o estado inicial. 
● Todos os estados tem setas ligando todos os estados, com exceção do estado inicial e 
do de aceitação. 
 
Para construir esse AFNG, adiciona­se um novo estado inicial com uma seta ε 
apontando para o antigo estado inicial e um novo estado de aceitação com setas ε chegando 
dos antigos estados de aceitação. Adiciona­se setas com rótulo Ø entre estados que não 
tenham setas.O David eh meu heroi! 
Devemos reduzir os estados do AFNG até ter somente o estado inicial e o estado de 
aceitação para convertê­lo em uma expressão regular. Fazemos isso selecionando um estado 
qualquer, removendo­o e reparando a máquina alterando as expressões regulares que rotulam 
cada uma das setas restantes de modo que a mesma linguagem ainda seja reconhecida. a 
nova seta ligando ​qi e qj ​é uma expressão regular  que descreve todas as cadeias que levariam 
qi a qj, seja passando pelo estado removido ou diretamente. 
O AFNG só difere do AFN somente pela função de transição: 
 
δ: (Q ­ {qaceita) X (Q ­ {qinício}) → R 
 
R é a coleção de todas as expressões regulares sobre o alfabeto ∑. Se δ(qi,qj) = R, a seta do 
estado qi para o estado qj tem a expressão regular R como rótulo. 
 
Definição Formal de AFNG: 
É uma 5­upla (Conjunto de estados, alfabeto de entrada, regras para movimentação, 
estado inicial e estado de aceitação; (Q,∑,δ,qinicio,aceita)) onde: 
● Q = o conjunto finito conhecido como os ​estados​; 
● ∑ = ​alfabeto ​de entrada​; 
● δ: (Q ­ {qaceita) X (Q ­ {qinício}) → R = ​função de transição; 
● qinicio = ​estado inicial; 
● qaceita = ​estado de aceitação; 
Definição Formal de Computação: 
Seja N = (Q,∑,δ,q0,F) um AFNG e ​w​ seja uma cadeia do alfabeto ∑*. 
N aceita w se w = ​w1w2w3...wn ​onde cada ​wi​ é membro do alfabeto ∑* e existe uma seqüência 
de estados q0, q1, …, qk em Q com 3 condições: 
 
7. q0 = qinicio 
➢ A máquina começa no estado inicial. 
8. Para cada i, wi ∈ L(Ri), onde R = δ(qi­i, qi) 
➢ Ri é a expressão regular sobre a seta que vai de qi­1 a qi. 
9. qk = q 
➢ A máquina aceita sua entrada se o último estado é de aceitação. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
1.4 Expressões Regulares 
 
Lema do Bombeamento para Linguagens Regulares 
 
É um teorema que afirma que todas as linguagens regulares têm uma propriedade 
especial. Se mostrarmos que uma linguagem não tem essa propriedade, temos a garantia de 
que ela não é regular. 
A propriedade diz que todas as cadeias da linguagem podem ser bombeadas se elas 
são no mínimo tão longas quanto um valor ​p​, chamado de ​comprimento de bombeamento​. 
Quer dizer que cada uma dessas cadeias contém uma parte que pode ser repetida um número 
qualquer de vezes com a cadeia resultante permanecendo na linguagem. 
O David eh meu heroi! 
Teorema 1.70 ­ Lema do Bombeamento 
Se A é uma linguagem regular, então existe um número ​p​ (comprimento de 
bombeamento) ​tal que, se ​s​ ​é qualquer cadeia de A de comprimento no mínimo ​p​, então ​s 
pode ser dividida em 3 partes, ​s = xyz​, satisfazendo as seguintes condições: 
1. para cada i ≥ 0,   ∈ A,y zx i  
2. |y| > 0, 
○ y ≠  ε 
3. |xy| ≤ p 
 
|s| representa o comprimento da cadeia s e  significa que i cópias de y são concatenadasyi  
entre si, e  = ε.y0  
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­Capítulo 2 
 
2.1 Gramáticas Livres­do­Contexto 
 
● Regras de substituição​, ou ​Produções​: 
○ cada regra aparece como uma linha na gramática, compreendendo um símbolo 
e uma cadeia separadas por uma seta. 
● Variável: 
○ São os símbolos, geralmente representadas por letras maiúsculas. As cadeias 
são constituídas de variáveis e outros símbolos chamados de ​terminais​. 
● Terminais: 
○ representados por letras minúsculas. 
● Variável Inicial: 
○ Uma variável que ocorre do lado esquerdo da primeira regra. 
● Derivação: 
○ Sequência de substituições para obter uma cadeia. 
● Linguagem Livre­do­Contexto (LCC): 
○ Linguagem gerada por uma Gramática Livre­do­Contexto. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo​: 
 
G1​: A → 0A1 
A → B 
B → # 
 
ou ​G1​: A → 0A1 | B 
B → # 
 
A,B​ = Variáveis 
0,1,#​ = Terminais 
A​ = Variável Inicial 
 
­ Forma a cadeia 000#111 
­ L(G1) = Conjunto de cadeias geradas por G1 (Linguagem da gramática G1)  
­ L(G1) = { # | n ≥ 0}0n 1n  
­ Pelo Lema do Bombeamento, w =  # → L(G1) é não­regular.0p 1p  
­ Uma derivação da cadeia 000#111 na gramática G1 é: 
 A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 000B111 ⇒ 000#111 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Definição Formal de uma Gramática Livre­do­Contexto: 
É uma 4­upla (V,∑,R,S)) onde: 
● V = o conjunto finito e não­vazio conhecido como os ​variáveis​; 
● ∑ = um conjunto finito disjunto de V denominado ​terminais; 
○ Pode usar ε. 
○ Equivale ao alfabeto nas linguagens regulares 
● R: Um conjunto finito de ​regras​, com cada regra sendo uma variável e uma cadeia de 
variáveis e terminais; 
○ A → u onde A ∈ V e u ∈ (V U ∑)* 
● S: ​Variável inicial; 
○ S ∈ V  
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Se A → ​w ​é uma regra de GLC, dizemos que: 
● uAv ​origina​ uwv : uAv ⇒ uwv, onde u,v ∈ (V U ∑)* 
● u ​deriva ​v: u ⇒* v  se u = v ou se existe uma sequência u1, u2, …, uk com k ≥ 0 e u1 ⇒ 
u2 ⇒ … ⇒ uk ⇒ v  
● A ​Linguagem da Gramática ​é: {w ∈ ∑* | S ⇒* w} 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo​: 
 
G3 = ({S}, {a,b}, R, S) onde o conjunto de regras R é: 
 
S → aSb | SS | ε 
 
­ A gramática G3 forma cadias como ab, abab, aaabbb, aababb… 
­ Pense em “a” como “(“ e em b como “)”. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo​: 
 
G4: = (V, ∑, R, <EXPR>) onde: 
V = { <EXPR>, <TERM>, <FACTOR>} 
∑ = {a, +, x, (, )} 
R = <EXPR> → <EXPR> + <TERM> | <TERM> 
<TERM> → <TERM> x <FACTOR> | <FACTOR> 
<FACTOR> → (<EXPR>) | a 
 
­ as cadeias a+a x a e (a+a) x a podem ser geradas por G4. 
Gramática Sensível ao Contexto: 
A substituição depende do contexto. Como no exemplo abaixo onde temos condições 
especiais na substituição de A (precedido de 1 e 0). 
 
Exemplo​: 
 
A → 0A0 
A → 1A0 
1A0 → 1AA0 
0A0 → 0BA0 
1B1 → 1#1 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Projetando Gramáticas Livres­do­Contexto 
 
1. Simplificar construindo gramáticas individuais para cada parte: S → S1 | S2 | … | Sk, 
onde Si são variáveis iniciais para as gramáticas individuais. Por exemplo, para obter 
uma gramática para a linguagem { | n ≥ 0} U { | n ≥ 0}, primeiro construir a0n 1n 1n 0n  
gramática: 
a. S​1​ → 0S​1​1 | ε para { | n ≥ 0}. E depois:0
n 1n  
b. S​2 → ​1S​2​0 | ε para { | n ≥ 0}. Depois adicionamos a regra S → S​1 ​| S​2​ para1
n 0n  
formar: 
S → S​1 ​| S​2 
S​1​ → 0S​1​1 | ε 
S​2 → ​1S​2​0 | ε 
 
2. Construir primeiro um AFD para uma linguagem regular para depois  construir uma 
GLC. 
a. Pegar uma variácel R​i ​para cada estado q​i ​do AFD. 
b. Adicionar a regra R​i​ → aR​j​ à GLC se δ(q​i​,a) = q​j​. 
c. Adicionar R​i ​→ ε se q​i ​∈ F. 
d. R​0 ​é a variável inicial da gramática onde q​0​ é o estado inicial da máquina. 
3. Cadeias com subcadeias ligadas no sentido de uma máquina para uma linguagem 
precisa memorizar uma quantidade ilimitada de informação sobre uma das subcadeias 
para verificar se ela corresponde à outra subcadeia. 
a. Por exemplo, { | n ≥ 0}, onde temos que verificar se o número de 0s é igual0n 1n  
ao de 1s. Construir uma GLC que lide com isso com uma regra da forma R → 
uRv que fera cadeias onde a parte contendo “u” corresponde à parte contendo 
“v”. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Ambiguidade 
 
● Derivação mais à esquerda: ​se a cada passo a variável remanescente mais à 
esquerda é aquela que é substituída. 
● Uma cadeia w é derivada ​ambiguamente ​em uma gramática se ela tem duas ou mais 
derivações mais a esquerda diferentes. 
● Gramática Ambígua:​ Gera alguma cadeia ambiguamente. 
● Linguagem Inerentemente ambígua: ​LLCs geradas apenas por gramáticas ambíguas. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Teorema 
A classe das linguagens livres­do­contexto é fechada sob as operação regulares (União, 
Concatenação e Estrela). 
 
Prova​: 
Para os 3 casos, temos uma prova por construção. Lembrando que a classe das LLCs 
não é fechada sobre a Intersecção nem a complementação. Seja L1 e L2 Linguagens 
Livres­do­Contexto geradas respectivamente pelas gramátivas G1 = (V​1​, ∑, R​1​, S​1​) e G2 = (V​2​, 
∑, R​2​, S​2​) com V​1 ​e V​2 ​disjuntos: 
 
L1 = ∑*01 
L2 = { | n ≥ 0}0n 1n  
 
G1: S​1​ → X01 
X → 1X | 0X | ε 
 
G2: S​2​ → 0S​2​1 | ε 
 
1) L1 U L2: 
G: S → S​1 ​| S​2 
S​1​ → X01 
X → 1X | 0X | ε 
S​2​ → 0S​2​1 | ε 
 
G = (V, ∑, R, S) onde 
V = V​1 ​U V​2 ​U {S}, S ∉ V​1​ e S ∉ V​2 
∑ = é o mesmo. 
R = R​1​ U R​2​ U {r1, r2}, r1: S → S​1​, r2: S → S​2​ ou 
R = R​1​ U R​2​ U {r0}, r0: S → S​1​ | S​2 
 
2) L1 ० L2: 
G: S → S​1​S​2 
S​1​ → X01 
X → 1X | 0X | ε 
S​2​ → 0S​2​1 | ε 
 
G = (V, ∑, R, S) onde 
V = V​1 ​U V​2 ​U {S}, S ∉ V​1​ e S ∉ V​2 
∑ = é o mesmo. 
R = R​1​ U R​2​ U {r0}, r0: S → S​1​S​2 
 
3) L1*: 
G: S → S​1​S | ε 
S​1​ → X01 
X → 1X | 0X | ε 
 
G = (V, ∑, R, S) onde 
V = V​1  ​U {S}, S ∉ V​1 
∑ = é o mesmo. 
R = R​1​  U {r1, r2}, r1: S → S​1​S, r2: S → ε 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo​: ​GLC para  , onde L = { | n ≥ 0}L 0n 1n  
 
 =L { | n > m ≥ 0} U0n 1m  
{ | m > n ≥ 0} U0n 1m  
{w | w contém a subcadeia 10} 
 = L1 U L2 U L3L  
 
G1: S​1​ → 0S​1​1 | 0S​1​ | 0 
G2: S​2​ → 0S​2​1 | S​2​1 | 1 
G3: S​3 ​→ X10X 
X → 0X | 1X | ε 
 
G: S → S​1 ​| S​2​ | S​3 
S​1​ → 0S​1​1 | 0S​1​ | 0 
S​2​ → 0S​2​1 | S​2​1 | 1 
S​3 ​→ X10X 
X → 0X | 1X | ε 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Teorema 
Se L é regular, então é Livre­do­Contexto. 
 
Prova​: 
Se L é regular, então existe um AFD M = (Q, ∑, δ, q0, F) que a reconhece. A partir de 
M, podemos construir uma GLC G = (V, ∑, R, S) equivalente. A prova é por construção, então 
vamos pegar como exemplo o AFD que reconhece L = {w | w contém a subcadeia 101}, com ∑ 
= {0,1}: 
 
 
Q = {q0, q1, q2, q3} 
F = {q3} 
δ  0  1 
q0  q0  q1 
q1  q2  q1 
q2  q0  q3 
q3  q3  q3 
 
Para construir uma GLC a partir de um AFD: 
 
● V = Q = {q0, q1, q2, q3} 
● Pegar uma variável R​i ​para cadaestado q​i ​do AFD e adicionar a regra R​i​ → aR​j​ à GLC 
se δ(q​i​,a) = q​j ​.Adicionar R​i ​→ ε se q​i ​∈ F: 
R: q​0 ​→ 0q​0​ | 1q​1 
q​1​ → 0q​2​ | 1q​1 
q​2​ → 0q​0​ | 1q​3 
q​3​ → 0q​3​ | 1q​3 
q​3​ → ε 
● R​0 ​é a variável inicial da gramática onde q​0​ é o estado inicial da máquina. 
S = q​0 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Definição Formal de Computação: 
Se w = w1w2...wn ∈ L, então existe uma sequência de estados r0, r1, r2, …, rn tal que: 
1. r0 = q0 
➢ A máquina começa no estado inicial. 
2. r​i+1​ = δ(r1, w​i+1​) para i = 0, 1, …, n­1 
➢ r1 = δ(r0, w​1​) e existe a regra r0 → w1r1 
3. r​n​ ∈ F 
➢ A máquina aceita sua entrada se o último estado é de aceitação. 
 
w é gerado pela GLC, com derivação: 
r0 ⇒ w1r1 ⇒ w1w2r2 ⇒ … ⇒ w1w2...wnrn ⇒ w1w2...wn 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplos de GLCs: 
 
1) L = {a,b}* 
S → aS | bS | ε 
 
S ⇒ aS ⇒ abS ⇒ abaS ⇒ aba para w = aba 
 
2) L = ∑*ab∑*a 
S → TabTa 
T → aT | bT | ε 
 
3) L = { | n, m ≥ 0}an bm cn+m  
S → A | ε 
A → aAc | B | ε 
B → bBc | ε 
ou 
S → aSb | B 
B → bBc | ε 
 
4) L = {  | m ≥ n ≥ 1}an bm  
S → aAb 
A → aAb | B 
B → Bb | ε 
 
5) L = {w | w contém a mesma quantidade de a​s​ e b​s​} 
S → aSb | bSa | SS | ε 
 
Seja w = axa onde w possui a mesma quantidade de a​s​ e b​s 
| a | a | b | a | b | a | b | a | a | b | b | b | b | a | 
0  1   2   1   2   1   2   1   2   3   2  1   0  ­1   0 
 
● Um contador que incrementa a cada “a” e decresce a cada “b”. Começando e 
terminando com “a”, o contador vai começar e terminar com 0 e deve ter um outro 0 no 
caminho. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Forma Normal de Chomsky 
 
Uma GLC está na ​forma normal de Chomsky ​se toda regra é da forma: 
A → BC 
A → ​a 
 
onde ​“a”​ é qualquer terminal e A, B, C são variáveis, com A sendo a variável inicial. Ainda 
podemos usar a regra S → ε onde S é a variável inicial. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Teorema 2.9 
Qualquer linguagem livre­do­contexto é gerada por uma GLC na forma normal de 
Chomsky. 
Pode se converter qualquer gramática G na forma normal de Chomsky seguindo os passos: 
1. Adiciona­se uma nova variável inicia para garantir que a variável inicial nunca apareça 
do lado direito; 
2. Elimina­se toda regra ε da forma A → ε (exceto S​0 ​→ ε caso exista); 
3. Elimina­se toda regra unitária da forma A → B; 
4. Corrige­se a gramática para que ela continue gerando a mesma linguagem; 
 
Prova​: 
1. Criamos uma variável inicial S​0  ​∉ V e a regra S​0​ → S. A nova gramática é G = (Q, V’, R’, 
S) onde: 
V’ = V U {S​0​} 
R’ = R U {S​0​ → S} 
2. Removemos toda regra da forma A → ε em que A não é a variável inicial. Então, para 
cada ocorrência de A no lado direito, adicionamos uma nova regra com essa regra 
apagada. Ou seja, se temos R → uAv, devemos adicionar a regra R → uv. Isso é feito 
para cada ocorrência de A, de modo que R → uAvAw faz com que adicionemos: 
R → uAvw, R → uvAw, R → uvw 
Se tivermos a regra R → A, adicionamos a regra R → ε sem criar regras já eliminadas. 
Isso é repetido até eliminar todas as regras ε que não envolvem a variável inicial. 
Lembrando que u é uma cadeia de variáveis e terminais. 
3. Removemos as regras unitárias A → B. Ou seja, para cada A → B, se temos B → u 
aparece, adicionamos a regra A → u  e eliminamos A → B. 
4. Eliminamos as regras mistas da forma A → u, onde u contém pelo menos um terminal e 
|u| ≥ 2. Então, para cada regra A → u, a cada terminal “​a” ​em “u”, adicionamos a regra 
W​1 ​→ a e substituímos u por W​1​ em u (A → W​1​). 
5. Eliminar as regras compridas. B​i​ ∈ V. Substituímos cada regra A → B​1​B​2​...B​k​ (k ≥ 3) 
por: 
A → B​1​C​1 
C​1​ → B​2​C​2 
C​2​ → B​3​C​3 
C​k­2​ → B​k­1​B​k 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 2.10​: 
 
Supomos a GLC G​6​, vamos convertê­la para a forma normal de Chomsky seguindo os passos 
acima. As regras em ​azul​ acabaram de ser adicionadas. E as regras em ​vermelho​ acabaram 
de ser removidas: 
 
1. G​6​ original está a esquerda. Adicionamos ma nova variável inicial: 
S → ASA | aB S​0​ → S 
A → B | S S → ASA | aB 
B → b | ε A → B | S 
B → b | ε 
 
2. Removemos as regras ε B → ε, mostrado a esquerda, e A → ε, mostrado a direita: 
S​0​ → S S​0​ → S 
S → ASA | aB |​ ​a S​ → ASA | aB | a | ​SA​ | ​AS​ | ​S 
A → B | S | ​ε A → B | S |  ​ε 
B → b | ​ε B → b 
 
3.  
a. Removemos as regras unitárias S → S mostrada à esquerda, e S​0​ → S 
mostrada à direita: 
S​0​ → S S​0​ → S ​| ​ASA​ | ​aB​ | ​a​ | ​SA​ | ​AS 
S​ → ASA | aB | a | SA | AS | ​S S​ → ASA | aB | a | SA | AS 
A → B | S A → B | S 
B → b B → b 
 
b. Removemos as regras unitárias A → B e A → S: 
S​0​ → ASA | aB | a | SA | ASS​0​ → ASA | aB | a | SA | AS 
S​ → ASA | aB | a | SA | ASS​ → ASA | aB | a | SA | AS 
A → B​ | S | ​b A → S​ | b | ​ASA​ | ​aB​ | ​a​ | ​SA​ | ​AS 
B → b B → b 
 
4. Convertemos as regras remanescentes para a forma apropriada. A gramática a seguir é 
equivalente a G​6​. 
S​0​ → AA​1​ | UB | a | SA | AS 
S​ → AA​1​ | UB | a | SA | AS 
A → b | AA​1​ | UB | a | SA | AS 
A​1​ → SA 
U → a 
B → b 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo: 
G​7 ​é a seguinte gramática: 
S → SXS | ε 
X →  ab | ε 
1. Após aplicar o passo 1, temos: 
S​0 ​→  S 
S → SXS | ε 
X →  ab | ε 
2. Após aplicar o passo 2, temos: 
S​0 ​→  S | ε 
S → SXS | SS | XS | SX | X 
X →  ab 
3. Após aplicar o passo 3, temos: 
S​0 ​→ SXS | SS | XS | SX | ab | ε 
S → SXS | SS | XS | SX | ab 
X →  ab 
4. Após aplicar o passo 4, temos: 
S​0 ​→ SXS | SS | XS | SX | AB | ε 
S → SXS | SS | XS | SX | AB 
X →  AB 
A​ ​→ a 
B → b 
5. Após aplicar o passo 5, temos: 
S​0 ​→ ST | SS | XS | SX | AB | ε 
S → ST | SS | XS | SX | AB 
X →  AB 
T → XS 
A​ ​→ a 
B → b 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
G​8 ​é a seguinte gramática: 
S → ASA | aB 
A →  B | S 
B → b | ε 
1. Após aplicar o passo 1, temos: 
S​0 ​→  S 
S → ASA | aB 
A →  B | S 
B → b | ε 
2. Após aplicar o passo 2, temos: 
S​0 ​→  S 
S → ASA | aB | a 
A →  B | S | ε 
B → b 
 
S​0 ​→  S 
S → ASA | SA | AS | aB | a 
A →  B | S 
B → b 
3. Após aplicar o passo 3, temos: 
S​0 ​→  ASA | SA | AS | aB | a 
S → ASA | SA | AS | aB | a 
A →  b | ASA | SA | AS | aB | a 
B → b 
4. Após aplicar o passo 4, temos: 
S​0 ​→  ASA | SA | AS | XB | a 
S → ASA | SA | AS | XB | a 
A →  b | ASA | SA | AS | XB | a 
B → b 
X → a 
5. Após aplicar o passo 5, temos: 
S​0 ​→  AY | SA | AS | XB | a 
S → AY | SA | AS | XB | a 
A →  b | AY | SA | AS | XB | a 
Y → SA 
B → b 
X → a 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Problema 2.26​: Mostre que, se G for uma GLC na forma normal de Chomsky, então para 
qualquer cadeia w ∈ L(G) de comprimento n ≥ 1, exatamente 2n ­ 1 passos são necessários 
para qualquer derivação de w usando G. Se n = 0, exatamente um passo é necessário. 
 
Exemplo​: 
G: S → ASA | aB 
A → B | S 
B → b | ε 
 
w = bbabbb ∈ L(G) 
S ⇒ ASA ⇒ AASAA ⇒ AAaBAA ⇒* bbabbb 
|w| = 6. 
Usando a forma normal de Chomsky, precisamos exatamente de 2x6­1 = 11 passos 
paraderivar w. 
 
Prova​: ​Se n ≥ 1: 
Para gerar uma cadeia w com |w| = n≥ 1, temos que fazer n substituições usando regras 
da forma A → a para produzir terminais. Precisamos também produzir n­1 variáveis, usando 
regras da forma A → BC. 
Cada substituição aumenta em 1 a quantidade de variáveis. Partindo da variável inicial, 
precisamos n­1 substituições para obter n variáveis no total. 
Total de substituições = n + n­1 = 2n ­ 1. 
Se n ­ 0, então w = ε. ε é gerado usando a substituição S → ε. 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Problema da Pertinência: 
Dada uma GLC G e uma cadeia w. w ∈ L(G)? 
 
Resposta: 
É possível saber se w ∈ L(G) usando o seguinte algoritmo: 
1. Transforme G em uma GLC G’ equivalente na forma normal de Chomsky; 
2. Se |w| ≥ 1, gere uma lista de todas as cadeias com 2|w|­1 substituições ­ Se w está 
nessa lista, então w ∈ L(G), se não, não; 
3. Se |w| = 0, verifique se a regra S​0​ → ε está em G’ (ou gere todas as cadeias com 1 
substituição e verifique se ε é uma delas); 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
2.2 Autômatos com Pilha 
 
São Autômatos Finitos Não­Determinísticos com um componente extra chamado pilha 
que provê memória adicional além da memória finita disponível no controle e permite que o 
autômato reconheça linguagens não­regulares. 
● São equivalentes  em poder a GLCs. 
● Pode escrever símbolos sobre a fita e lê­los mais tarde. 
● A pilha começa vazia. E o autômato aceita se ao final da cadeia de entrada ele se 
encontra em um estado de aceitação mesmo se a pilha não estiver vazia. 
 
Propriedades: 
1. Todo AFN pode ser considerado um AP que ignora a pilha. 
a. Para toda linguagem regular, existe um AP que a reconhece. 
2. Uma linguagem é livre­do­contexto se se somente se um AP a reconhece. 
a. Para toda linguagem livre­do­contexto existe um AP que a reconhece e para 
toda GLC, existe um AP equivalente. 
b. A linguagem reconhecida por todo AP é livre­do­contexto. Para todo AP existe 
uma GLC equivalente. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 1: 
L = {a​n​b​n​ | n ≥ 0} 
 
1. Para cada símbolo ‘a’ lido, empilhamos um símbolo ‘x’; 
2. Para cada símbolo ‘b’ lido, desempilhamos um símbolo ‘x’; 
3. Se ao final da cadeia a pilha está vazia, então a quantidade de ‘a’ é a mesma de ‘b’; 
 
 
 
w​1​ = aabb → aceita. 
w​2​ = aaba → não aceita. 
w​3​ = aabbb → não aceita (por não ter mais x para desempilhar). 
w​4​ = aab → aceita (a máquina para num estado de aceitação). 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 2:  
L = {a​n​b​n​ | n ≥ 0} 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 3:  
L = {ww​R​ | w ∈ {a,b}*} 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 4: 
L = {w | w contém a mesma quantidade de ‘a’ e ‘b’} 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 5: 
L = {w | w ∈ {(,)}* e w é uma cadeia de parênteses corretamente encaixados} 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Exemplo 6: 
L = {a​i​b​j​c​k​ | i, j, k ≥ 0 e i = j ou i = k} 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de Autômato com Pilha (Não­Determinístico): 
É uma 6­upla P = (Q,∑,Γ,δ,q0,F) onde: 
● Q = Conjunto de estados; 
● ∑ = Alfabeto de entrada; 
● Γ = Alfabeto da pilha; 
○ Γ pode ser (Γ = ∑); 
● δ = Função de transição; 
● q​0​ = Estado inicial (q​0​ ∈ Q); 
● F = Conjunto de estados de aceitação (F ⊆ Q); 
 
■ δ é definido por: 
δ: Q x ∑​ε​ x Γ​ε​ → P(Q x Γ​ε​) = δ: Q x ∑​ε​ x desempilha → P(Q x empilha); 
■ a,b → c = lê, desempilha, empilha; 
 
 
Lembrando que: ∑​ε​ = ∑ U {ε}; 
Γ​ε​ = Γ U {ε}; 
 
δ(qi,a,x) = {(qj,y), (qp,z)} 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de Computação: 
Um AP P = (Q,∑,Γ,δ,q0,F) aceita a cadeia w ∈ ∑* se podemos se w = w1w2...wn, com 
wi ∈ ∑* e existe uma sequência de estados r0, r1, r2, …, rn e uma sequência de cadeias s0, 
s1, s2, …, sn com si ∈ Γ* tal que: 
1. r0 = q0, s0 = ε; 
➢ P inicia no estado inicial e com a pilha vazia. 
2. (r​i+1​, b) ∈ δ(r​i​, w​i+1​, a) 
➢ P se move conforme o estado, a pilha e o próximo símbolo de entrada. 
➢ i = 0, 1, 2, …, n­1; 
➢ s​i​ = ​at​ e s​i+1​ = ​bt​ com ​a, b​ ∈ Γ​ε​ e ​t​ ∈ Γ* 
3. rn ∈ F 
➢ O estado de aceitação ocorre ao final da entrada. 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo​: 
Utilizando o exemplo 1, onde L = {a​n​b​n​ | n ≥ 0},  
 
w = aabb 
 
Sequência de estados é: q0, q1, q1, q1, q2, q2, q2, q3 = εaaεbbε → k símbolos e k+1 estados 
(7 símbolos, 8 estados). 
Sequência de cadeia em S​i​ = ε, $, x$, xx$, x$, $, ε 
 
1. Estado inicial = q0 e s​0​ = ε; 
2. (q1, $) ∈ δ(q0, ε, ε) para (i = 0);  
s​0 ​= ε; s​1​ = $ 
(q1,x) ∈ δ(q1, a, ε) para (i = 1); 
s​1​ = $; s​2​ = x$; 
3. q3 ∈ F; 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Teorema 2.20 
Uma linguagem é livre do contexto se e somente se um autômato com pilha a 
reconhece. (Duas provas para dois lemas, ida e volta). 
 
Lema 2.21: ​Se uma linguagem é livre do contexto, então alguma autômato com pilha a 
reconhece.  
 
Prova​: 
O AP que descreveremos aceitará uma entrada ​w​ gerada por uma GLC G determinando 
se existe uma dericação para w. 
O AP começa escrevendo empilhando $ e a variável inicial na pilha, passando por 
várias cadeias intermediárias e fazendo várias substituições. Em algum momento ele pode 
chegar contendo somente símbolos terminais, o que significa que a GLC foi usada para derivar 
a cadeia. Então o AP aceita se essa cadeia for idêntica a cadeia de entrada. Os passos são: 
1. Colocar $ e a variável inicial na pilha; 
2. Loop: 
a. Se o topo da pilha é uma variável “A”, não­deterministicamente selecione uma 
das regras de A e substitua A pela cadeia do lado direito da regra. 
b. Se o topo da pilha é um terminal “​a​”, leia o próximo símbolo da entrada e 
compare­o com “​a​”. Se eles são iguais, repita. Se não são, rejeite nesse ramo 
não­determinístico. 
c. Se o topo da pilha é $, entre no estado de aceitação e a entrada é aceita se ela 
tiver sido toda lida. 
 
Um jeito de abreviar a ação de empilhar uma cadeia ao invés de um símbolo na pilha 
dentro das regras de transição é acrescentar novos estados entre um estado e outro: 
 
 
(r, xyz) ∈ δ(q, a, s); 
 
 
 
Dada uma GLC = (V,∑,R,S), queremos um AP P = (Q,∑,Γ,δ,q0,F) equivalente. O AP 
deve aceitar as mesmas cadeias geradas pela GLC. 
 
● Q = {qinício, qlaço, qaceita} U E, onde E = conjunto de estados para implementar a 
abreviação acima; 
● Γ = ∑ U V U {$}; 
● q0 = qinício; 
● F = {qaceita}; 
● δ é definido por: 
1. δ(qinício, ε, ε) = {(qlaço, S$)} 
2. Laço: 
a. δ(qlaço, ε, A) = {(qlaço, w) | A→w é regra onde A ∈ V, w ∈ (V U ∑)*}; 
b. δ(qlaço, a, a) = {(qlaço, ε)} 
c. δ(qlaço, ε, $) = {(qaceita, ε)} 
● E = {q1, q2, q3, q4, q5}Para :S → aSb | bSb | ε 
 
Como no livro, podemos simplificar para: 
 
 
 
 
 
 
 
 
 
 
 
 
Teorema 
Roda linguagem regular também é livre­do­contexto. 
 
Prova: 
L regular → existe um AFD que reconhece L → existe um AFN equivalente → existe um 
AP equivalente → existe uma GLC equivalente → L é Livre­do­Contexto. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
2.3 Linguagens Não­Livres­do­Contexto 
 
 
Lema do Bombeamento para LLCs. 
 
Teorema 2.34 
Se A é uma LLC, então existe um número ​p​ (comprimento de bombeamento) onde, se ​s 
é uma cadeia em A de comprimento pelo menos ​p​, então ​s​ pode ser dividida em 5 partes (s = 
uvxyz) que satisfazem as condições: 
 
1. para cada i ≥ 0, uv​i​xy​i​z ∈ A; 
● Uma mesma variável gera vxy em sua ocorrência mais alta e somente x em sua 
ocorrência mais baixa. 
2. |vy| > 0 (v ≠ ε ou y ≠ ε) 
3. |vxy| ≤ p; 
 
Prova: 
G é a GLC que gera a LLC A. “b” é o número máximo de símbolos do lado direito de 
uma regra. Na árvore sintática, um nó não pode ter mais que “b” filhos, ou seja, no máximo “b” 
folhas estão a um passo da variável inicial; no máximo b​2​ folhas estão a 2 passos da variável 
inicial; e no máximo b​h​ folhas estão a “h” passos da variável inicial. Então se a altura da árvore 
sintática é no máximo h, o comprimento de bombeamento ​p​ da cadeia gerada é no máximo b​h​. 
Uma árvore sintática de altura h gera uma cadeia de comprimento máximo b​h​. 
● Altura (h):​ Quantidade de substituições da primeira à última substituição. 
● Altura ≤ h ⇒ |w| ≤ b​h 
● |w| > b​h​ ⇒ altura > h 
● |V| = Número de variáveis em G e p = b​|V| + 1​: 
○ Então se w é uma cadeia em A, e seu comprimento é p ou mais, ela tem que ter 
altura no mínimo |V|+1. 
Para todo w ∈ L, com |w| ≥ p, a altura da árvore é ≥ |V|+1: ​|w| ≥ p ⇒ altura ≥ |V|+1. 
Se altura ≥ |V|+1, o caminho de maior comprimento da variável inicial até uma folha contém 
pelo menos |V|+1 variáveis, ou seja, alguma variável está repetida. 
­ Se b = 0, a GLC é S → ε, então L = {ε} e p = 1. (Satisfaz o lema por vacuidade) 
­ Se b = 1, a GLC é S → A, A → B, B → C… e L = {a,b,c,...,z,ε}, que pode conter ε e 
cadeias de comprimento 1. 
 
 
A prova é válida para b ≥ 2​: 
 
|w| ≥ b​h+1​ = |w| ≥ b​h​+b 
b ≥ 2 ⇒ |w| > b​h 
 
|w| ≥ b​h+1​ ⇒ |w| > b​h​ ⇒ altura ⇒ h 
|w| ≥ b​h+1​ ⇒ altura > h 
|w| ≥ b​h+1​ ⇒ altura ≥ h+1 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Exemplo: 
L = {0​n​#1​n​} | n≥ 0} 
 
S → 0S1 
S → B 
B → # 
 
w = 000#111 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
S → AB 
A → aA | bB | ε 
B → abBba | ε 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
L = {a​n​b​n​c​n​ | n ≥ 0} 
 
Suponha L é uma LLC. Existe p > 0 (comprimento de bombeamento). 
w = a​p​b​p​c​p​ = cadeia de teste. 
 
Começamos com a condição 3) que nos diz que 
|vxy| ≤ p e vamos analizar os casos onde isso 
acontece: 
 
caso 1)​ vxy contém somente ‘a’s 
caso 2)​ vxy contém ‘a’s e ‘b’s 
caso 3)​ vxy contém somente ‘b’s 
caso 4)​ vxy contém ‘b’s e ‘c’s 
caso 5)​ vxy contém somente ‘c’s 
 
caso 1)​ vy = a​k​ (1≤ k ≤ p) 
  uxz = a​p­k​b​p​c​p​ ∉ L 
caso 2)​ vy = a​k​b​j​ (1 ≤ k+j ≤ p) 
  uxz = a​p­k​b​p­l​c​p​ ∉ L 
caso 3)​ vy = b​k​ (1≤ k ≤ p) 
  uxz = a​p​b​p­k​c​p​ ∉ L 
caso 4)​ vy = b​k​c​j​ (1 ≤ k+j ≤ p) 
  uxz = a​p​b​p­k​c​p­j​ ∉ L 
caso 5)​ vy = c​k​ (1≤ k ≤ p) 
  uxz = a​p​b​p​c​p­k​ ∉ L 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo​: 
L = {ww | w ∈ {a,b}*} 
 
w = a​p​b​p​a​p​b​p​ → w ∈ L e |w| = 4p ≥ p 
 
 
Começamos novamente pela condição 3 para verificar os casos: 
 
1) Se vxy contém símbolos de ambas as metades, vy contém k ‘a’s e j ‘b’s (0 < k+j ≤ p). 
Bombeando para baixo: uxz = a​p​b​p­j​a​p­k​b​p​ ∉ L. 
a) Se j > k: A primeira metade começa com a e a segunda com b. 
b) Se k > j: A primeira metade termina com a e a segunda com b. 
c) Se k = j: As duas metades são diferentes. 
Portanto, uxz ∉ L. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
L = {ww​R​ | w ∈ {a,b}*} 
 
L é LLC pois S → aSa | bSb | ε gera L. 
L = {ε, aa, bb, aaaa, abba, …} 
L satisfaz o lema: p = 1 (valor mínimo, pois toda cadeia w ∈ L, |w| ≥ 1 tem a forma: 
Onde s ∈ {a,b}*. 
● uvvxyyz = saaaas​R​ ∈ L 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo​: 
L = {a​n​b​m​c​n+m​ | n,m ≥ 0} 
 
L é LLC pois : S → aSc | A 
A → bAc | ε 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo​: 
L = {a​n​b​m​c​nm​ | n,m ≥ 0} 
L não é LLC. 
 
Prova: 
Suponha L sendo LLC e p > 0. 
w = a​p​b​p​c​p2 w ∈ L e |w| = 2p + p​2​ ≥ p 
 
1) vxy contém somente ‘a’s e ‘b’s : k ‘a’s e j ‘b’s (k 
≠ 0 ou j ≠ 0). Bombeando para baixo: 
uxz = a​p­k​b​p­j​c​p2​ → p​2​ ≠ (p­k)*(p­j) 
2) vxy contém somente ‘c’s. c​k​, k > 0: 
uxz = a​p​b​p​c​p2­k​ → p​2­k​ ≠ p*p 
3) vxy contém k ‘b’s e j ‘c’s (k ≠ 0 ou j ≠ 0): 
uxz = a​p​b​p­k​c​p2­l 
 
p​2​­ j = p*(p­k) ? 
p​2​­ j = p​2​­ pk 
pk = j ? 
 
1. Se k = 0, j ≠ 0 e uxz ∉ L (caso 2) 
2. Se k ≠ 0, j = 0 e uxz ∉ L (caso 1) 
3. Se k ≠ 0 e j ≠ 0, pk > j → uxz ∉ L 
4. Se k = 1, j < p e pk > j, uxz ∉ L 
5. Se k > 1, j < p e pk > l, uxz ∉ L 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
L = {a​k​b​i​a​i​b​j​a​j​b​k​ | i, j, k ≥ 0} 
L é LLC pois: 
S → aSb | A 
A → BB 
B → bBa | ε 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
L = {w#x | w,x ∈ {a,b}* e w é uma subcadeia de x} 
L = {#, ​a​#​a​, ​a​#​a​b, ​abb​#a​abb​b,...} 
Não é LLC. 
 
Prova: 
Suponha LLC, e p o comprimento de bombeamento. 
w = a​p​b​p​#a​p​b​p 
 
aaa...​aaabbb​...bbb#aaa...aaabbb...bbb 
vxy 
 
1) vxy contém a​k​ e b​j​ antes de #. Bombeando para cima: 
uvvxyyz = a​p+k​b​p+j​#a​p​b​p​ ∉ L pois a​p+k​b​p+j​ não é subcadeia de a​p​b​p 
2) vxy contém a​k​ e b​j​ depois de #. Bombeando para baixo: 
uxz = a​p​b​p​#a​p­k​b​p­j​ ∉ L pois a​p​b​p​ não é subcadeia de a​p­k​b​p­j 
3) vxy contém o símbolo # 
a) Se v ou y contém  #, bombeando para baixo: uxz não contém # e ∉ L. 
b) x contém #. Então v = b​k​ e y = a​j​, com k ≠ 0 ou j ≠ 0. 
Bombeando para baixo: 
uxz = a​p​b​p­k​#a​p­j​b​j 
Se j ≠ 0, a​p​b​p­k​ não é subcadeia de a​p­j​b​p 
 
Bombeando para cima: 
uvvxyyz = a​p​b​p+k​#a​p+j​b​j 
Se k =≠ 0, a​p​b​p+k​ não é subcadeia de a​p+j​b​p 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
L = {w​R​#x | w,x ∈ {a,b}* e w é uma subcadeia de x} = {​abb​#aa​bba​aa, …} 
 
S → AB 
B → aB | bB | ε  
A → aAa | bAb| C 
C → Ca | Cb | # 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Capítulo 3 
 
3.1 Máquina de Turing 
 
(MT determinística) 
Em cada passo da sua operação: 
1. Lê um símbolo da fita; 
2. De acordo com o estado atual e o símbolo lido: 
a. Escreve o símbolo (na mesma posição); 
b. Muda de estado ou não; 
c. Desloca a cabeça de leitura/escrita uma posiçãopara a direita ou esquerda. 
 
● A fita é semi­infinita; 
● Inicialmente, a cabeça da leitura/escritura está no extremo esquerdo da fita; 
● Possui um único estado de aceitação e um único estado de rejeição; 
● A MT para imediatamente quando chega a um estado de aceitação ou rejeição; 
● Se a MT não para nunca, dizemos que entrou em loop; 
● MT pode ler e escrever “brancos” ​⊔​. 
 
A linguagem de uma MT = conjunto de cadeias que ela aceita. 
Se L1 = L(M), dizemos que M reconhece L1. 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Definição Formal de Máquina de Turing : 
É uma 7­upla M = (Q,∑,Γ,δ,q0,q​aceita​,q​rejeita​) onde: 
● Q = Conjunto de estados; 
● ∑ = Alfabeto de entrada; 
○ sem o símbolo em branco ​⊔ 
● Γ = Alfabeto da fita; 
○ ⊔ ​∈ Γ e ∑ ⊆ Γ 
● δ = Função de transição; 
● q​0​ = Estado inicial (q​0​ ∈ Q); 
● q​aceita​ = estado de aceitação; 
● q​rejeita​ = estado de rejeição; 
 
■ δ é definido por: 
δ: Q’ x Γ → Q x Γ x {E,D} 
Q’ = Q ­ {q​aceita​,q​rejeita​} 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplo: 
MT que reconhece L = {w#w | w ∈ {a,b}*} → L não é LLC 
 
 
 
w = aabb#aabb ∈ L 
 
 
xabb#aabb 
xabb#xabb 
xxbb#xabb 
xxbb#xxbb 
 
∑ = {a,b,#} 
Γ = {a,b,#,x,​⊔​} 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Definição de Configuração de uma MT: 
Representação do estado atual, conteúdo da fita e posição da cabeça da 
leitura/escritura. 
 
Exemplo​: 
1011q​7​01111 → a fita é 101101111, o estado atual é q​7​ e a cabeça está sobre o 
segundo 0. 
 
Exemplo: 
● uaq​i​bv origina uq​j​acv se na função de transição  δ(q​i​, b) = (q​j​, c, E) 
● uaq​i​bv origina uacq​j​v se na função de transição  δ(q​i​, b) = (q​j​, c, D) 
 
Exemplo: 
● A configuração q​i​bv origina q​j​cv se na função de transição δ(q​i​, b) = (q​j​, c, E) 
● A configuração uaq​i​ (uaq​i​⊔​) origina ua​⊔​q​j​ se na função de transição δ(q​i​, ​⊔​) = (q​j​, ​⊔​, D  
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Definição Formal de Computação: 
Uma MT M = (Q,∑,Γ,δ,q0,q​aceita​,q​rejeita​) aceita (rejeita) uma cadeia w = w1w2...wn, com wi 
∈ ∑ se existe uma sequência de configurações C0, C1, C2, …, Cn tal que: 
1. C0 é a configuração inicial q​0​w; 
2. Ci origina C​i+1​ segundo a função de transição; 
3. Cn é uma configuração de aceitação (rejeição); 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Exemplos de MT: 
 
Exemplo 1: 
MT que decide (aceita w ​∈ A e rejeita w ∉ A) ​a linguagem A = {0​2^n​ | n ≥ 0 } = 
{0,00,0000,000000,...} 
Nesse caso, a MT sempre para. 
 
M = “Sobre a cadeia de entrada w: 
1. Faça uma varredura da esquerda a direita, marcando um 0 não e um sim. 
2. Se no estágio 1 a fita contém um único 0, aceite. 
3. Se no estágio 1, a fita contém mais de um 0 em uma quantidade ímpar, rejeite. 
4. Retorne ao extremo esquerdo da fita. 
5. Vá para o estágio 1. 
 
∑ = {0}, ​Γ = {0,@,X,​⊔​} 
 
 
Exemplo 2​: 
MT ENDMARK → Recebe uma cadeia w, escreve o símbolo @ na frente de w 
para ∑ = {0,1} 
 
 
 
Exemplo 3: 
MT EQUAL →  Decide a linguagem L = {w | w possui a mesma quantidade de 
0’s e 1’s} 
 
 
Exemplo 4: 
MT EVEN → Recebe uma cadeia de entrada w que representa um número 
binário n. Aceita se n for par e rejeita se n for ímpar. 
 
 
Exemplo 5: 
MT LEFTEND → Dada uma entrada @w, coloca a cabeça sobre o primeiro 
símbolo de w e para. 
 
 
 
Exemplo 5: 
MT NEXTLEX → Recebe @w e retorna @u, onde u é o sucessor lexicográfico 
de w. 
 
 
Exemplo 6: 
MT INCR → f(n) = n+1 
 
 
Exemplo 7: 
MT COPY → Recebe @w e retorna @w#w 
 
 
Exemplo 8: 
MT ENUM → Enumera (lista) cadeuas de {0,1}* em ordem lexicográfica. 
 
##0#1#00#01#10#... 
 
 
Exemplo 8: 
MT COMP → Recebe @w1#w2, e retorna @1 se w1 < w2 ou @0 se w1 ≥ w2, 
onde w1 e w2 representam números binários n1 e n2. Computa a função f(n1, n2) = 1, 
se n1 , n2; 0, se n1 ≥ n2. 
 
f(1110#11100) = 1 
f(11100#01100 = 0 
∑ = {@,0,1,#} 
Γ = {@,0,1,#,⊔​, ​0º,1º} 
 
M = “Sobre a entrada @w1#w2: 
1. Se os comprimentos w1 e w2 não são iguais, insira 0’s na frente da cadeia mais curta 
para que ambas fiquem do mesmo tamanho. 
2. Compare os dígitos mais à esquerda de cada cadeia. 
3. Se o dígito mais à esquerda de w1 é 0, e o de w2 é 1, apague a fita exceto @, escreva 
1 e pare. 
4. Se o dígito mais à esquerda de w1 é 1, e o de w2 é 0, apague a fita exceto @, escreva 
0 e pare. 
5. Se são iguais, substitua ambos por X e compare os próximos dígitos de cada cadeia. 
6. Repita até achar dígitos diferentes ou chega ao fim das cadeias. 
7. Apague a fita exceto @, escreva 0 e pare.” 
 
Exemplo 9: 
MT que decide C = {a​j​, b​j​, c​k​ | i*j = k e i,j,k ≥1} 
M = “Sore a cadeia de entrada w: 
1. Verifique se w tem a forma a​n​b​n​c​n​. Se não tiver, rejeite. 
2. Marque um a, vá e volte entre b’s e c’s marcando um de cada até esgotar os b’s. Se 
todos os c’s foram marcados, rejeite. 
3. Apague as marcas sobre os b’s, repita o passo dois para cada “a”, Se todos os a’s 
forem marcados, veja se todos os c’s também foram marcados. Se sim, aceite, se não, 
rejeite. 
 
Exemplo 10: 
MT ADD → Recebe w​1​#w​2​, e retorna w​3​, onde w​i​ representam números binários n​i​, e n​3 
= n​1​ + n​2​ (Computa a função f(n​1​,n​2​) = n​1​ + n​2​) 
M = “Sobre a entrada w​1​#w​2​: 
1. No final da cadeia entrada, adicione #0. 
2. Rode COMP sobre w​2​ e 0 
3. Se w​2​ > 0, rode INCR sobre w​1​ e DECR sobre w​2​. 
4. Repita até obter w​2​ = 0. 
5. Apague tudo exceto w​1​” 
 
Exemplo 11: 
MT MULT → f(n​1​,n​2​) = n1​1​*n​2 
M = “Sobre a entrada w​1​#w​2​: 
1. No final da entrada escreva #0#0, o primeiro 0 é X. 
2. Rode COMP sobre w​2​ e o segundo 0. 
3. Se w​2​ > 0: 
a. Rode COPY para criar uma cópia de w​1​ no final. 
b. Rode ADD para adicionar w​1​ a X. 
c. Rode DECR sobre w​2​. 
4. Repita até w​2​ = 0. 
5. Apague tudo exceto X. 
 
Exemplo 12: 
MT SQRT → f(n) = {sqrt(n), se n é um quadrado perfeito | maior inteiro n tal que m ≤ 
sqrt(n), se n não é um quadrado perfeito}: f(25) = 5, f(18) = 4 
 
M = “Sobre a entrada w: 
1. No final da entrada escreva #0. Chame ao 0 de X. 
2. Rode COPY para criar 2 cópias de X. 
3. Rode MULT para multiplicar as duas cópias de X e obter Y = X*X. 
4. Rode COMP para comparar Y com w. 
5. Se y ≤ w, rode INCR sobre X. 
6. Repita os passos 2­5 até Y > w. 
7. Rode DECR sobre X 
8. Apague tudo exceto X” 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Variantes de Máquinas de Turing: 
 
1) MT M​1​ na qual a cabeça de leitura/escrita pode não deslocar. 
 
Função de transição = δ: Q’ x Γ → Q x Γ x {E,D,P} 
Q’ = Q ­ {q​aceita​,q​rejeita​} 
 
Teorema 
Para toda MT M​1​ existe uma MT regular M​2​ equivalente. 
 
Prova: 
Para cada transição δ(q​i​,a) = (q​j​,b,P) de M​1​, M​2​ realiza as transições: 
δ(q​i​,a) = (q​i​’,b,D) 
δ(q​i​’,c) = (q​j​,c,E) para todo c ∈ Γ. 
 
2) MT Multifita 
Função de transição = δ: Q’ x Γ​1 ​x Γ​2 ​x … x Γ​k​ → Q x Γ​1 ​x Γ​2 ​x … x Γ​k​ x {E,D}​k 
 
 
Teorema 
Para tida MT de k fitas, existe uma MT de uma fita equivalente 
 
Prova: 
A MT regular simula as k fitas em uma única fita da seguinte forma: 
 
 
 
Γ = {0,1,a,b,x,@,⊔,#,0º,1º,aº,bº,xº,@º,⊔º} 
 
 
3) MT com fita infinita para os dois sentidos 
 
Teorema 
Para toda MT infinita para os dois sentidos, existe uma MT regular equivalente.Prova: 
Podemos simular esta MT com uma MT com duas fitas. Toda MT com fita em ambos 
sentidos possui uma MT de duas fitas equivalente. Toda MT com duas fitas possui uma MT 
regular equivalente. 
 
4) MT não­determinística 
 
Função de transição = δ: Q’ x Γ → P(Q x Γ x {E,D}) 
 
Se pelo menos um ramo da árvore leva ao estado de aceitação, a MT aceita a entrada. Se 
todos os ramos válidos levam a estados de rejeição, a MT rejeita. (Busca por nível). 
 
Teorema 
Para toda MT não­determinística existe uma MT determinística equivalente. 
 
Prova: 
Seja uma MT não­determinística M. Construímos uma MT N determinística equivalente 
usando 3 fitas: 
Fita 1: Recebe a cadeia de entrada, e não é modificada. 
Fita 2: Fita de simulação. 
Fita 3: Fita endereço → (MT ENUM) Ordem lexicográfica → índice do ramo não 
determinístico. 
 
A fita 3 trabalha com um alfabeto ∑ = {1,2,3} (maior quantidade de bifurcações possíveis), 
enumerando cadeias sobre ∑​3​ em ordem lexicográfica. 
 
Teorema 
Para toda MT com qualquer variante que alguém tenha considerado alguma vez, ou 
possa considerar no futuro, existe uma MT regular equivalente. 
 
Corolário 
Uma linguagem é Turing­Reconhecível (decidível) se e somente se uma MT Variante a 
reconhece. 
 
Prova para MT Multifita: 
L é Decidível → uma MT com uma única fita decide L → Essa MT também é multifita, 
com k =1 → uma MT multifita decide L. 
 
L é decidido por uma MT multifita → existe uma MT com uma única fita equivalente → 
Essa MT é decide L → L é decidível. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Enumeradores: 
 
1. MT ENUM → Enumera cadeias sobre ∑ em ordem lexicográfica. 
G = “Sobre a entrada w: 
1. Ignore a entrada e apague a fita e escreva # no início da fita 
2. Começando por s = ε, escreva s# na fita 
3. Copie S a direita do último # 
4. Substitua o último s pelo seu sucessor lexicográfico, e adicione # a direita 
5. Volte ao passo 2, e repita indefinidamente.” 
 
2. MT que enumera cadeias da linguagem L = {w | w contém uma quantidade ímpar de 
1’s} → L é regular = 0*1(0*10*1)*0* 
∑ = {0,1} 
L = {1,01,10,001, 010,...} 
 
MT com 3 fitas: 
E = “Sobre a entrada w: 
1. Apague a fita 1 (as outras já começam vazias) 
2. Rode o enumerador G para gerar cadeias  s​i​ ∈ ∑*, na fita 2.. Para cada cadeia 
s​i​ gerada: 
a. Apague a fita 3 e escreva 1 na fita 3 
b. Faça uma varredura sobre s​i​ cada vez que leia 1, troque o 1 na fita 3 por 
0, ou o 0 por 1. 
c. Ao chegar no final de s​i​, leia a fita 3. Se contiver 00, escreva # a direita 
do conteúdo da fita 1 e copie a cadeia s​i​ parar a fita 1. Se a fita 3 contém 
10, volte ao passo 2 para gerar outra cadeia.” 
 
3. MT que enumera L = { w | w contém a subcadeia 111 } → L é regular = ∑*111∑* 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Teorema 
Uma linguagem é decidível se e somente se um enumerador a enumera em ordem 
lexicográfica 
 
Prova: 
1) Se L é decidível, então é enumerável em ordem lexicográfica. Se existe a MT D que 
decide L, então podemos construir o enumerador E da seguinte forma: 
 
E = “Sobre a entrada w: 
1. Ignore a entrada. 
2. Rode ENUM para gerar cadeias sobre ∑ em ordem lexicográfica. Para cada cadeia 
gerada s​i​: 
a. Rode D sobre s​i​. Se aceita, imprima s​i​”. 
 
 
2) Seja L enumerável lexicograficamente, com enumerador E, construímos uma MT D que 
decide L: 
 
D = “Sobre a entrada w: 
1. Rode E para gerar cadeias s​i​ ∈ L. Para cadeias s​i​: 
a. Compare s​i​ e w. Se w < s​i​, rejeite. 
b. Se w = s​i​, aceite. Se w > s​i​, volte ao passo 1 para gerar a próxima  cadeia s​i​.” 
 
Teorema 
Uma linguagem é Turing­Reconhecível se e somente se uma enumerador a enumera. 
 
Prova: 
1) L é enumerável. Construímos uma MT que reconhece L. 
 
R = “Sobre a entrada w: 
1. Rode E para gerar cadeias s​i​ ∈ L. Para cada cadeia s​i​: 
a. Compare s​i​ e w. 
b. Se s​i​ = w, aceite. Se s​i​ ≠ w, volte ao passo 1.” 
 
2) L é Turing­Reconhecível. Construímos um enumerador para L. 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Fecho sobre operações: 
A classe das linguagens decidíveis é fechada sobre: 
1) União 
2) Intersecção 
3) Complementação 
4) Concatenação 
5) Operação estrela 
 
Sejam L1 e L2 decidíveis e D1 e D2 as MTs que as decidem. 
 
Complementação: 
 
D = “Sobre a entrada w: 
1. Rode D1 sobre w. Se Aceita, rejeita, se rejeita, aceite” 
 
Concatenação: 
 
D = “sobre a entrada w: 
1. Para cada forma de subdividir w na forma w = w1w2: 
a. Rode D1 sobre w1. Se aceita, rode D2 sobre w2. Se D2 aceita, aceite. 
2. Se todas as subdivisões foram testadas e nenhuma foi aceita, rejeite. 
 
União: 
 
 
Intersecção: 
 
 
Estrela: 
 
D = “Sobre a entrada w: 
1. Sobre cada forma de subdividir w = w1,w2,...wk, onde os wi são subcadeias: 
a. Rode D1 sobre cada wi. Se D1 aceita todos os wi, aceite. 
2. Se todas as subdivisões forem listadas, rejeite. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
Capítulo 4 
 
4.1 Linguagens Decidíveis 
 
Problemas decidíveis concernentes a Linguagens Regulares 
 
Vamos analisar algoritmos que testam se um autômato finito aceita uma cadeia, se a 
linguagem de um AFD é vazia e se dois AFDs são equivalentes. Vamos mostrar pelos 
teoremas 4.1, 4.2 e 4.3 que entregar à MT um AFD, um AFN ou uma expressão regular é a 
mesma coisa, pois podemos converter uma codificação na outra. 
 
Problema da aceitação: ​Expresso pela linguagem A​AFD​ que testa se um AFD específico aceita 
uma dada cadeia. 
A​AFD​ = {<B,w> | B é um AFD que aceita a cadeia de entrada w} → Testamos se <B,w> é 
membro da linguagem A​AFD​. (Se o AFD B aceita a entrada w).  
Mostrar que a linguagem é decidível é o mesmo que mostrar que o problema 
computacional é decidível. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Teorema 4.1 
A​AFD​ é uma linguagem decidível. 
 
Prova: 
Construímos uma MT M que decide A​AFD​. 
M = “Sobre a entrada <B,w>, onde B é um AFD, e w é uma cadeia: 
1. Simule B sobre a entrada w. 
2. Se a simulação termina em um estado de aceitação, aceite; Se não, rejeite.” 
 
É o mesmo que imaginar um programa que realiza uma simulação. A entrada <B,w> é uma 
representação do AFD B (uma lista de seus 5 componentes Q, ∑, δ, q0, F) e de uma cadeia w. 
Ao receber a entrada, M determina primeiro se o AFD B está representado apropriadamente, 
se não estiver, M rejeita. 
M realiza a simulação mantendo o registro do estado atual de B e da posição atual de B 
na entrada w escrevendo essa informação na sua fita. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Teorema 4.2 
A​AFN​ é uma linguagem decidível. 
 
Prova: 
A​AFN​ = {<B,w> | B é um AFN que aceita a cadeia de entrada w} 
 
Construímos uma MT N que decide A​AFN​ e convertemos o AFN B para um AFD equivalente C, 
fazendo N usar M como sub­rotina. 
 
N = “Sobre a entrada <B,w> onde B é um AFN, e w é uma cadeia: 
1. Converta o AFN B para um AFD equivalente C usando o procedimento do Teorema 
1.39. 
2. Rode a MT M sobre <C,w>. 
3. Se M aceita, aceite, Se M rejeita, rejeite. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Teorema 4.3 
A​EXR​ é uma linguagem decidível. 
 
Prova: 
A​EXR​ = {<R,w> | R é uma expressão regular que gera a cadeia w} 
 
Construímos