LFA II - Manual

Prévia do material em texto

Linguagens Formais e Autómatos 
78 
Capítulo 7 
 
Minimização de Autómatos Finitos Determinísticos. 
Lema de Repetição para LR’s 
 
É natural colocar a seguinte questão: exixtirá entre todos os autómatos reconhecendo uma 
linguagem algum que se possa dizer, num certo sentido, o mais simples de todos? Por exemplo, 
tem o número mínimo de estados. Vamos ver que sim. 
Existem muitos algoritmos para receber um autómato mínimo ou para minimizar um 
autómato dado. 
Vamos minimizar um AFD dado utilizando o conceito dos estados equivalentes. 
Seja 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) um AFD, introduzimos uma relação 𝑅𝐿
∗ em 𝑄. 
Definição 7.1. 
𝑅𝐿
∗ = {(𝑝, 𝑞)| 𝑝, 𝑞 ∈ 𝑄 𝑒 ∀𝑤 ∈ Σ∗(𝛿(𝑝, 𝑤) ∈ 𝐹 ⟺ 𝛿(𝑞, 𝑤) ∈ 𝐹)} 
 
 
 
 
 
 
Teorema 7.1. 𝑅𝐿
∗
 é uma relação de equivalência. 
Demonstração. Problema Proposto. 
 
Exemplo 7.1. (𝑝, 𝑞) ∉ 𝑅𝐿
∗
 se 𝑝 ∈ 𝐹, 𝑞 ∉ 𝐹. 
Solução. Seja 𝑤 = 𝜆. 𝛿(𝑝, 𝜆) ∈ 𝐹 𝑒 𝛿(𝑞, 𝜆) ∉ 𝐹 . 
 
𝐹 
 
𝑄 𝑤 
𝑤 
𝑝 
𝑞 
∉ 𝑅𝐿
∗ 
 Linguagens Formais e Autómatos 
79 
Construção de AFD mínimo 
 
Para minimizar um AFD dado (encontrar AFD reduzido) é preciso achar relação 𝑅𝐿
∗. Para 
encontrar 𝑅𝐿
∗ construímos o digrafo etiquetado 𝐺: No início eliminamos os estados não acessíveis 
do estado inicial (se existir). Cada vértice de 𝐺 é um par não ordenado de estados. 
Seja 𝑈 = {(𝑞𝑖 , 𝑞𝑗)| 𝑞𝑖 ∈ 𝐹, 𝑞𝑗 ∉ 𝐹}. Para cada (𝑞𝑖 , 𝑞𝑗) ∉ 𝑈 e 𝑖 ≠ 𝑗 e 𝑎 ∈ Σ construímos o arco 
 
 
(𝑞𝑖 , 𝑞𝑗) ∈ 𝑅𝐿
∗ se e só se não existe o caminho em 𝐺 de (𝑞𝑖 , 𝑞𝑗) para um vértice que pertence a 𝑈 
(vértice “mal”). 
Exemplo 7.2. Achar um AFD mínimo 𝐴1 para AFD 𝐴: 
 
 
 
 
 
 
Solução. Todos os estados são acessíveis do estado inicial. 
 
 
 
 
 
 
 
 
 
𝑞𝑖, 𝑞𝑗 𝛿(𝑞𝑖 , 𝑎), 𝛿(𝑞𝑗 , 𝑎) 
a 
1 0 
0,1 
1 
1 
0 
𝐴: 
0 
𝑞1 𝑞3 
𝑞0 
𝑞5 
𝑞4 𝑞2 
1 
1 
0 
0 
𝑞0, 𝑞1 𝑞0, 𝑞4 
𝑞5, 𝑞5 
1 
1 
0 
1 
𝑞1, 𝑞4 𝑞2, 𝑞3 
𝑞4, 𝑞5 𝑞2, 𝑞5 
𝑞4, 𝑞4 
𝑞3, 𝑞5 
1 
1 
0 
0 
vértice 
“mal” 
1 
0 
0 
0 
 Linguagens Formais e Autómatos 
80 
Assim, (𝑞0, 𝑞1) ∈ 𝑅𝐿
∗, (𝑞2, 𝑞3) ∈ 𝑅𝐿
∗ 
𝑅𝐿
∗ = {(𝑞0, 𝑞0), (𝑞1, 𝑞1), (𝑞2, 𝑞2), (𝑞3, 𝑞3), (𝑞4, 𝑞4), (𝑞5, 𝑞5), (𝑞0, 𝑞1), (𝑞1, 𝑞0), (𝑞2, 𝑞3), (𝑞3, 𝑞2)} 
[𝑞0] = {𝑞0, 𝑞1} = [𝑞1], [𝑞2] = {𝑞2, 𝑞3} = [𝑞3], [𝑞4] = {𝑞4}, [𝑞5] = {𝑞5}. 
𝑄 𝑅𝐿
∗⁄ = {{𝑞0, 𝑞1}, {𝑞2, 𝑞3}, {𝑞4}, {𝑞5}} − 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑞𝑢𝑜𝑐𝑖𝑒𝑛𝑡𝑒. 
 
 
 
 
 
O autómato mínimo para 𝐴 é 𝐴1: 
 
 
 
 
 
𝐿(𝐴) = 𝐿(𝐴1). 
 
Lema de Repetição para LR’s 
 
Lema de Repetição para LR’s é um dos resultados básicos sobre linguagens regulares. Este 
lema tem vários nomes: Pumping Lemma, Teorema de abcesso, 𝑢𝑣𝑤 – Teorema e aplica-se, de 
costume, para demonstrar que algumas linguagens não são regulares. 
Teorema 7.2. (Lema de Repetição para LR’s) 
 Seja 𝐿 uma linguagem regular. Então existe uma constante (inteiro positivo) 𝑛 que depende 
de 𝐿 tal que se 𝑥 é qualquer palavra de 𝐿 e |𝑥| ≥ 𝑛 então podemos representar 𝑥 = 𝑢𝑣𝑤 onde: 
* 
𝑞1 𝑞3 𝑞0 𝑞5 𝑞4 𝑞2 
* 
𝑞0, 𝑞1 
1 1 
0 0 
1 
0,1 
𝑞5 𝑞4 
0 
𝑞2, 𝑞3 𝐴1: 
 Linguagens Formais e Autómatos 
81 
1) |𝑢𝑣| ≤ 𝑛; 
2) |𝑣| ≥ 1 (𝑣 ≠ 𝜆); 
3) para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿. 
Demonstração. Seja 𝐿 uma linguagem regular. Pelo Teorema de Kleene existe um AFD 𝐴 que 
aceita 𝐿. Sem perda de generalidade podemos supor que o autómato 𝐴 é mínimo. Suponhamos que 
𝐴 tem 𝑛 estados e 𝑥 ∈ 𝐿 tal que |𝑥| ≥ 𝑛. O caminho de computação de 𝑥 envolve |𝑥| arcos e logo 
|𝑥| + 1 estados (vértices). Como 𝐴 tem 𝑛 estados então neste caminho alguns estados devem 
repetir-se. Seja 𝑞𝑖 o primeiro estado que se repete. O caminho de computação de 𝑥 podemos 
representar assim: 
 
 
 
 
Logo, 𝑥 = 𝑢𝑣𝑤 onde |𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1 e para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿. 
 
Problemas resolvidos 
 
7.1. Seja 𝐿(𝐴) = (0 + 1)∗101(0 + 1)∗. Achar constante 𝑛 que existe pelo Lema de Repetição. 
Escolher uma palavra 𝑥 ∈ 𝐿 tal que |𝑥| ≥ 𝑛. Representar 𝑥 na forma 𝑥 = 𝑢𝑣𝑤 onde 
|𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1. Verificar que 𝑢𝑤 ∈ 𝐿 e 𝑢𝑣2𝑤 ∈ 𝐿. 
Solução. Vamos inicialmente construir AFD 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗101(0 + 1)∗. 
 
 
 
 
 
Assim, 𝑛 = 4 é o número de estados de 𝐴. 
v 
𝑞0 𝑞𝑖 𝑞𝑓 
w u 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
0,1 
0 
0 
1 
𝐴: 
 Linguagens Formais e Autómatos 
82 
Seja 𝑥 = 1101. Então |𝑥| ≥ 4 e 𝑥 ∈ 𝐿. 𝑥 = 𝑢𝑣𝑤 onde 𝑢 = 1, 𝑣 = 1, 𝑤 = 01. 
O caminho de computação de 𝑢 = 1 é , todos os estados são diferentes. 
O caminho de computação de 𝑢𝑣 = 11 é , 𝑞1 é o primeiro 
estado que se repete. Assim, |𝑢𝑣| = |11| = 2 ≤ 4, |𝑣| = |1| = 1 ≥ 1, o caminho de 
computação da palavra 𝑥 = 𝑢𝑣𝑤 = 1101 tem a forma: 
 
 
 
 
 
 
𝑢𝑤 = 101 ∈ 𝐿, 𝑢𝑣2𝑤 = 11101 ∈ 𝐿. 
 
Seja 𝑥 = 100101. Então |𝑥| = 6 ≥ 4 e 𝑥 ∈ 𝐿. 𝑥 = 𝑢𝑣𝑤 onde 𝑢 = 𝜆, 𝑣 = 100, 𝑤 = 101. 
O caminho de computação de 𝑢 = 𝜆 é , o caminho de computação de 𝑢𝑣 = 100 é 
 , 𝑞0 é o primeiro estado que se repete. 
Assim, |𝑢𝑣| = |100| = 3 ≤ 4, |𝑣| = |100| = 3 ≥ 1, o caminho de computação da 
palavra 𝑥 = 𝑢𝑣𝑤 = 100101 tem a forma: 
 
 
 
 
 
 
 
 
𝑢𝑤 = 101 ∈ 𝐿, 𝑢𝑣2𝑤 = 100100101 ∈ 𝐿. 
 
𝑞0 𝑞1 
1 
1 
𝑞0 𝑞1 
1 
𝑞1 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
v 
u 
w 
1 
𝑢 = 1, 𝑣 = 1, 𝑤 = 01 
𝑞0 
0 
𝑞0 𝑞1 
1 
𝑞2 
0 
𝑞0 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
1 
0 
0 
1 
𝑞1 𝑞2 
v 
w 
𝑢 = 𝜆, 𝑣 = 100, 𝑤 = 101 
 Linguagens Formais e Autómatos 
83 
7.2. Achar um AFD mínimo 𝐴1 para AFD 𝐴: 
 
 
 
 
 
 
Solução. Todos os estados são acessíveis do estado inicial. 
 
 
 
 
 
 
 
 
 
 
 
 
Assim, (2,4) ∈ 𝑅𝐿
∗, (3,5) ∈ 𝑅𝐿
∗ 
𝑅𝐿
∗ = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 4), (4, 2), (3, 5), (5, 3)} 
[1] = {1}, [2] = {2, 4} = [4], [3] = {3, 5} = [5]. 
𝑄 𝑅𝐿
∗⁄ = {{1}, {2, 4}, {3, 5}} − 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑞𝑢𝑜𝑐𝑖𝑒𝑛𝑡𝑒. 
 
 
 
* 
4 1 5 3 2 
a 
b 
b 
b 𝐴: 
a 
a,b 
1 2 
4 
3 
a 
5 
a,b 
1, 2 
1, 4 
b 
b 
a 
2, 4 3, 5 
4, 5 
3, 3 
2, 3 
5, 5 
a,b 
- vértice “mal” 
 
a 
b 
a 
- vértice “mal” 
 Linguagens Formais e Autómatos 
84 
O autómato mínimo para 𝐴 é 𝐴1: 
 
 
 
 
7.3. Demonstrar que a linguagem 𝐿 = {0𝑛1𝑛| 𝑛 ≥ 0} não é LR, utilizando o Lema de Repetição. 
Solução. Demonstramos que 𝐿 não é LR pelo método de redução à contradição. 
Suponhamos que 𝐿 é uma LR. Pelo Lema de Repetição deve existir um número 𝑛 tal que se 𝑥 ∈ 𝐿 
e |𝑥| ≥ 𝑛 então 𝑥 = 𝑢𝑣𝑤 onde |𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1 e para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿. 
Vamos escolher um número 𝑚 > 𝑛. 
A palavra 𝑥 = 0𝑚1𝑚 ∈ 𝐿 e |𝑥| = |0𝑚1𝑚| = 2𝑚 > 𝑛. Assim, 𝑥 = 𝑢𝑣𝑤 onde 𝑢, 𝑣, 𝑤 satisfazem 
as conclusões do Lema de Repetição. Logo, |𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1 e 𝑢𝑣𝑘𝑤 ∈ 𝐿 para todo 𝑘 ≥ 0. 
Como 𝑚 > 𝑛 e 𝑚 é o número de 0’s em 𝑥 e |𝑢𝑣| ≤ 𝑛 < 𝑚 então 𝑢𝑣 tem só 0’s. 
 
 
 
Pelo Lema de Repetição 𝑢𝑣2𝑤 ∈ 𝐿. 
Mas o número de 0’s de 𝑢𝑣2𝑤 é maior do que o número de 1’s, |𝑢𝑣2𝑤|0 > |𝑢𝑣
2𝑤|1. 
Logo, 𝑢𝑣2𝑤 ∉ 𝐿. É uma contradição. 
Assim, 𝐿 não é LR. 
7.4. Demonstrar que a linguagem 𝐿 = {1𝑛
2
| 𝑛 = 1,2, … } não é LR, utilizando o Lema de 
Repetição. 
Solução. Demonstramos que𝐿 não é LR pelo método de redução à contradição. 
a,b a,b 
a,b 
1 2, 4 3, 5 𝐴1: 
v u w 
𝑥 = 00 … 0 11 … 1 
m m 
 Linguagens Formais e Autómatos 
85 
Suponhamos que 𝐿 é uma LR. Pelo Lema de Repetição deve existir um número 𝑛 tal que se 𝑥 ∈ 𝐿 
e |𝑥| ≥ 𝑛 então 𝑥 = 𝑢𝑣𝑤 onde |𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1 e para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿. 
Seja 𝑥 = 1𝑛
2
onde 𝑛 é constante que existe pelo Lema de Repetição. Logo, |𝑥| = |1𝑛
2
| =
𝑛2 > 𝑛, 𝑥 ∈ 𝐿 e 𝑥 = 𝑢𝑣𝑤 onde |𝑢𝑣| ≤ 𝑛, 𝑛2 = |𝑥| = |𝑢𝑣𝑤| < |𝑢𝑣2𝑤| = |𝑢𝑣𝑤| + |𝑣| =
𝑛2 + |𝑣| ≤ 𝑛2 + 𝑛 < 𝑛2 + 2𝑛 + 1 = (𝑛 + 1)2 
Assim, 𝑛2 < |𝑢𝑣2𝑤| < (𝑛 + 1)2. 
Pelo Lema de Repetição 𝑢𝑣2𝑤 ∈ 𝐿, mas por outro lado 𝑢𝑣2𝑤 não é um quadrado perfeito e 
𝑢𝑣2𝑤 ∉ 𝐿. É uma contradição. Assim, 𝐿 não é LR. 
 
7.5. Demonstrar que 𝐿 = {1𝑝| 𝑝 ∈ ℙ − 𝑡𝑜𝑑𝑜𝑠 𝑜𝑠 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑝𝑟𝑖𝑚𝑜𝑠} não é LR, utilizando Lema 
de Repetição. 
Solução. Demonstramos que 𝐿 não é LR pelo método de redução à contradição. 
Suponhamos que 𝐿 é uma LR. Pelo Lema de Repetição deve existir um número 𝑛 tal que se 𝑥 ∈ 𝐿 
e |𝑥| ≥ 𝑛 então 𝑥 = 𝑢𝑣𝑤 onde |𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1 e para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿. 
Consideremos um número primo 𝑝 > 𝑛. Então, 1𝑝 ∈ 𝐿 e |1𝑝| = 𝑝 > 𝑛. Seja |𝑢| + |𝑤| = 𝑖, 
|𝑣| = 𝑗. Para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿, logo |𝑢𝑣𝑘𝑤| = |𝑢𝑤| + 𝑘|𝑣| = 𝑖 + 𝑘𝑗 é um número primo. 
Se 𝑘 = 0 então 𝑖 + 𝑘𝑗 = 𝑖 é um número primo e 𝑖 ≥ 2. 
Se 𝑘 = 𝑖 então 𝑖 + 𝑘𝑗 = 𝑖 + 𝑖𝑗 = 𝑖(1 + 𝑗) não é um número primo. É produto de dois números 
onde cada factor é maior ou igual a 2(𝑖 ≥ 2, 1 + 𝑗 = 1 + |𝑣| ≥ 2). 
Assim, por um lado, pelo Lema de Repetição, 𝑖 + 𝑘𝑗 é um número primo para todo 𝑘 ≥ 0, por 
outro lado para 𝑘 = 𝑖, 𝑖 + 𝑘𝑗 = 𝑖 + 𝑖𝑗 = 𝑖(1 + 𝑗). É uma contradição. Assim, 𝐿 não é LR. 
 
 
 
 Linguagens Formais e Autómatos 
86 
Problemas propostos 
 
7.6. Achar um AFD mínimo para AFD 𝐴: 
 
 
 
 
 
7.7. Achar um AFD mínimo para AFD 𝐴: 
 
 
 
 
 
 
 
7.8. Achar um AFD mínimo para AFD 𝐴: 
 
 
 
 
 
7.9. Achar um AFD mínimo para AFD 𝐴: 
 
 
 
 
 
7.10. Seja 𝐿(𝐴) = (0 + 1)∗011(0 + 1)∗. Construir AFD 𝐴 tal que 𝐿(𝐴) = 𝐿. Achar constante 𝑛 
que existe pelo Lema de Repetição. 
 ↓ ∗ ∗ 
𝛿 1 2 3 4 5 6 7 8 
𝑎 1 3 4 3 4 6 2 3 
𝑏 4 1 2 5 6 3 4 1 
 ↓ ∗ ∗ 
𝛿 1 2 3 4 5 6 7 8 
𝑎 3 8 7 6 1 2 1 5 
𝑏 5 7 2 2 8 3 4 1 
a 
b 
b 
𝐴: 
a 
b 
1 2 3 
a 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
0,1 
0 
0 
1 
𝐴: 
𝐴: 
𝐴: 
 Linguagens Formais e Autómatos 
87 
a) Escolher uma palavra 𝑥 ∈ 𝐿 e |𝑥| ≥ 𝑛. Representar 𝑥 na forma 𝑥 = 𝑢𝑣𝑤, |𝑢𝑣| ≤ 𝑛,
|𝑣| ≥ 1, para todo 𝑘 ≥ 0, 𝑢𝑣𝑘𝑤 ∈ 𝐿. 
b) Seja 𝑥 = 0111. Representar 𝑥 na forma 𝑥 = 𝑢𝑣𝑤, |𝑢𝑣| ≤ 𝑛, |𝑣| ≥ 1. Escrever 
separadamente 𝑢, 𝑣 e 𝑤. 
c) Fazer a mesma coisa para 𝑥 = 01111. 
 
7.11. Demonstrar que as linguagens seguintes não são LR’s: 
a) 𝐿 = {𝑎𝑛
3
| 𝑛 ≥ 1}; 
b) 𝐿 = {𝑎𝑛𝑏𝑛𝑐𝑛| 𝑛 ≥ 1}; 
c) 𝐿 = {𝑤𝑤𝑅| 𝑤 ∈ {0,1}∗}; 
d) 𝐿 = {0𝑖1𝑗| 𝑖 = 2𝑗}; 
e) 𝐿 = {0𝑖1𝑗| 𝑖 ≥ 0, 𝑗 ≥ 𝑖}; 
f) 𝐿 = {𝑤|𝑤 ∈ {0,1, … ,9, +, (, )}∗, 𝑤 é 𝑢𝑚𝑎 𝑒𝑥𝑝𝑟𝑒𝑠𝑠ã𝑜 𝑎𝑟𝑖𝑡𝑚é𝑡𝑖𝑐𝑎 
𝑠𝑖𝑛𝑡𝑎𝑐𝑡𝑖𝑐𝑎𝑚𝑒𝑛𝑡𝑒 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑎}; 
g) 𝐿 = {0𝑖1𝑗| 𝑖 ≠ 𝑗}. 
 
7.12. 
 
 
 
 
 
 
a) Construir AFD 𝐴1 tal que 𝐿(𝐴1) = 𝐿(𝐴). 
b) Achar AFD mínimo para AFD 𝐴1. 
a,b 
b 
𝑞0 𝑞2 
𝑞1 𝑞3 
b 
a 
a 𝐴: 
 Linguagens Formais e Autómatos 
88 
Respostas 
 
7.6. 
 
 
 
7.7. AFD 𝐴 já é mínimo. 
 
7.8. 
 
 
 
 
 
 
7.9. 
 
 
 
 
 
 
7.10. b) 𝑥 = 0111, 𝑢 = 011, 𝑣 = 1, 𝑤 = 𝜆 
 c) 𝑥 = 01111, 𝑢 = 011, 𝑣 = 1, 𝑤 = 1. 
 
7.11. g) Sugestão. (𝐿 ⊂ 0∗1∗). 
 
 
7.12. b) 
a 
b 
a,b 
1 2, 3 
a 
b 
b 
a 
b 
1,6 
2,5 
3,4 
a 
a 
b b 
a 
b 
1,2 
5,6,7 
3,4,8 
a 
a,b 
 Linguagens Formais e Autómatos 
89 
Capítulo 8 
 
Gramáticas e Linguagens Formais. A hierarquia de Chomsky. 
Autómatos e Gramáticas Regulares 
 
Como já sabemos existem as linguagens não regulares, não são reconhecíveis por autómatos 
finitos. Isto leva-nos a pensar que a classe das linguagens regulares é muito restrita. Realmente, 
linguagens regulares aplicam-se na elaboração de compiladores para criar identificadores. 
Introduzimos outros instrumentos para trabalhar com linguagens que se chamam gramáticas. 
Definição 8.1. Uma gramática 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) é um sistema de quatro elementos onde: 
1) 𝑁 é um conjunto finito de símbolos não terminais. 
2) 𝑇 é um conjunto finito de símbolos terminais, 𝑁 ∩ 𝑇 = ∅ e põe-se 𝑉 = 𝑁 ∪ 𝑇. 
3) 𝑃 ⊂ 𝑉∗𝑁 𝑉∗ × 𝑉∗ subconjunto finito dito produções. Cada produção (𝛼, 𝛽) ∈ 𝑃 vamos 
representar na forma 𝛼 → 𝛽 onde 𝛼 chama-se cabeça e 𝛽 chama-se corpo de produção. É 
importante que a cabeça de cada produção sempre tem pelomenos um símbolo não 
terminal. 
4) 𝑆 ∈ 𝑁 é o símbolo inicial. 
Se tivermos as produções com mesma cabeça, 𝛼 → 𝛽1, 𝛼 → 𝛽2, … , 𝛼 → 𝛽𝑛, podemos abreviar, 
escrevendo 𝛼 → 𝛽1|𝛽2| … |𝛽𝑛. 
Sejam 𝑢, 𝑣 ∈ 𝑉∗. Escrevemos 𝑢 ⇒ 𝑣 e dizemos que 𝑣 deriva directamente de 𝑢 se 
existem 𝑥, 𝑦 ∈ 𝑉∗ e uma produção 𝛼 → 𝛽 tais que 𝑢 = 𝑥𝛼𝑦 e 𝑣 = 𝑥𝛽𝑦. 
 
 
 
 
 
x α y 
x β y 
𝑢 = 
 
𝑣 = 
 
𝛼 → 𝛽 ∈ 𝑃, 𝑢 ⇒ 𝑣 
 Linguagens Formais e Autómatos 
90 
Escrevemos 𝑢 ⇒∗ 𝑣 e dizemos que 𝑣 deriva de 𝑢 se 𝑢 = 𝑣 ou existem 𝑤0, 𝑤1, … , 𝑤𝑛 ∈ 𝑉
∗ tais 
que 𝑢 = 𝑤0 ⇒ 𝑤1 ⇒ ⋯ ⇒ 𝑤𝑛 = 𝑣. Dizemos neste caso que 𝑑: 𝑢 ⇒ 𝑤1 ⇒ ⋯ ⇒ 𝑣 é uma 
derivação em 𝐺, o número 𝑛 diz-se o comprimento de derivação e denota-se por |𝑑|. 
Nota 8.1. No caso 𝑢 = 𝑣, |𝑑| = 0. O símbolo 𝑢 ⇒+ 𝑣 significa que |𝑑| ≥ 1. 
Definição 8.2. Uma palavra 𝑤 ∈ 𝑉∗ chama-se forma sentencial se 𝑆 ⇒∗ 𝑤. Uma palavra 
𝑤 ∈ 𝑇∗ chama-se sentença se 𝑆 ⇒∗ 𝑤. 
Definição 8.3. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma gramática. A linguagem gerada pela gramática 𝐺 (por 
vezes também dita linguagem da gramática 𝐺) é a linguagem 
𝐿(𝐺) = {𝑤|𝑤 ∈ 𝑇∗, 𝑆 ⇒∗ 𝑤}. 
Definição 8.4. Duas gramáticas 𝐺1 e 𝐺2 dizem-se equivalentes se gerem a mesma linguagem, isto 
é 𝐿(𝐺1) = 𝐿(𝐺2). Neste caso escrevemos que 𝐺1~𝐺2. 
Exemplo 8.1. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝜆 | 𝑎𝑆𝑏}. Achar 𝐿(𝐺). 
Solução. Vamos encontrar algumas palavras concretas que pertencem a 𝐿(𝐺). 
𝑆 ⇒ 𝜆 ∈ 𝐿(𝐺); 
𝑆 ⇒ 𝑎𝑆𝑏 ⇒ 𝑎𝜆𝑏 = 𝑎𝑏 ∈ 𝐿(𝐺); 
𝑆 ⇒ 𝑎𝑆𝑏 ⇒ 𝑎𝑎𝑆𝑏𝑏 ⇒ 𝑎𝑎𝑏𝑏 = 𝑎2𝑏2 ∈ 𝐿(𝐺); 
𝑆 ⇒ 𝑎𝑆𝑏 ⇒ 𝑎2𝑆𝑏2 ⇒ ⋯ ⇒ 𝑎𝑛𝑆𝑏𝑛 ⇒ 𝑎𝑛𝑏𝑛 ∈ 𝐿(𝐺). 
Assim, se 𝑤 ∈ 𝐿(𝐺) então 𝑤 = 𝑎𝑛𝑏𝑛 isto é 𝐿(𝐺) ⊆ {𝑎𝑛𝑏𝑛 | 𝑛 ≥ 0}. 
Vamos demonstrar que {𝑎𝑛𝑏𝑛 | 𝑛 ≥ 0} ⊆ 𝐿(𝐺). 
Se 𝑢 ∈ 𝐿(𝐺) então 𝑆 ⇒∗ 𝑢 e 𝑆 ⇒ 𝑎𝑆𝑏 ⇒∗ 𝑎𝑢𝑏. 
Assim, se 𝑢 ∈ 𝐿(𝐺) então 𝑎𝑢𝑏 ∈ 𝐿(𝐺). 
 
Agora, utilizando a indução matemática demonstraremos que 𝑎𝑛𝑏𝑛 ∈ 𝐿(𝐺) para todo 𝑛 ≥ 0. 
(Base) 𝑛 = 0, 𝑎0𝑏0 = 𝜆 ∈ 𝐿(𝐺). 
(Passo Indutivo) Suponhamos que 𝑛 ≥ 0 e 𝑎𝑛𝑏𝑛 ∈ 𝐿(𝐺). 
 Linguagens Formais e Autómatos 
91 
Então 𝑎𝑛+1𝑏𝑛+1 = 𝑎 𝑎𝑛𝑏𝑛𝑏 ∈ 𝐿(𝐺) 
 
Logo, 𝑎𝑛𝑏𝑛 ∈ 𝐿(𝐺) para todo 𝑛 ≥ 0. 
Assim, 𝐿(𝐺) = {𝑎𝑛𝑏𝑛 | 𝑛 ≥ 0}. 
Exemplo 8.2. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {< 𝑓𝑟𝑎𝑠𝑒 >, < 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 >, < 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜 >, 
< 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 >, < 𝑛𝑜𝑚𝑒 >, < 𝑣𝑒𝑟𝑏𝑜 >, < 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑖𝑟𝑒𝑐𝑡𝑜 >}; 
𝑇 = {𝑐𝑜𝑒𝑙ℎ𝑜, 𝑒𝑟𝑣𝑎, 𝑐𝑜𝑚𝑒, 𝑜, 𝑎}; 𝑃 = {< 𝑓𝑟𝑎𝑠𝑒 > → < 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 >< 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜>, 
< 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 > → < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 >< 𝑛𝑜𝑚𝑒 >, < 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜 > → < 𝑣𝑒𝑟𝑏𝑜 > 
< 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑖𝑟𝑒𝑐𝑡𝑜 >, < 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑖𝑟𝑒𝑐𝑡𝑜 >→< 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 >< 𝑛𝑜𝑚𝑒 >,
< 𝑛𝑜𝑚𝑒 > → 𝑐𝑜𝑒𝑙ℎ𝑜|𝑒𝑟𝑣𝑎, < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 > → 𝑜|𝑎, < 𝑣𝑒𝑟𝑏𝑜 > → 𝑐𝑜𝑚𝑒}; 
𝑆 = < 𝑓𝑟𝑎𝑠𝑒 >. 
Esta gramática pode ser usada para gerar frases. Por exemplo, 
< 𝑓𝑟𝑎𝑠𝑒 > ⇒ < 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 > < 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜 > ⇒ < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 > < 𝑛𝑜𝑚𝑒 > 
< 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜 > ⇒ < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 >< 𝑛𝑜𝑚𝑒 > < 𝑣𝑒𝑟𝑏𝑜 > < 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑖𝑟𝑒𝑐𝑡𝑜 >
⇒ < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 > < 𝑛𝑜𝑚𝑒 > < 𝑣𝑒𝑟𝑏𝑜 > < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 > < 𝑛𝑜𝑚𝑒 > ⇒ < 𝑜 > 
< 𝑛𝑜𝑚𝑒 > < 𝑣𝑒𝑟𝑏𝑜 > < 𝑑𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡𝑒 > < 𝑛𝑜𝑚𝑒 > ⇒∗ 𝑜 𝑐𝑜𝑒𝑙ℎ𝑜 𝑐𝑜𝑚𝑒 𝑎 𝑒𝑟𝑣𝑎. 
É claro que a frase “a erva come o coelho” podia também ser gerada por esta gramática. 
Exemplo 8.3. (Gramática de números inteiros) 
Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 
𝑁 = {< 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 >, < 𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 >, < 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 >, < 𝑑𝑖𝑔𝑖𝑡 >}; 
𝑇 = {0,1, … ,9, +, −}; 
𝑃 = {< 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > → < 𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > | < 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > 
< 𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > → + < 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > |− < 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > 
< 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > → < 𝑑𝑖𝑔𝑖𝑡 > | < 𝑑𝑖𝑔𝑖𝑡 >< 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > 
< 𝑑𝑖𝑔𝑖𝑡 > → 0|1| … |9 }; 
𝑆 = < 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 >. 
𝑢 ∈ 𝐿(𝐺) 
 Linguagens Formais e Autómatos 
92 
Vamos considerar uma derivação nesta gramática 
< 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > ⇒ < 𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > ⇒ − < 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > ⇒ − < 𝑑𝑖𝑔𝑖𝑡 >
< 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > ⇒ −2 < 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 > ⇒ −2 < 𝑑𝑖𝑔𝑖𝑡 > ⇒ −27. 
Podemos demonstrar que nesta gramática é possível derivar qualquer número inteiro e nada mais. 
Exemplo 8.4. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆, 𝐵}, 𝑇 = {𝑎, 𝑏, 𝑐}, 𝑃 = {𝑆 → 𝑎𝑆𝐵𝑐 | 𝑎𝑏𝑐,
𝑐𝐵 → 𝐵𝑐, 𝑏𝐵 → 𝑏𝑏 }. Achar 𝐿(𝐺). 
Solução. 𝑆 ⇒ 𝑎𝑏𝑐 ∈ 𝐿(𝐺); 
𝑆 ⇒ 𝑎𝑆𝐵𝑐 ⇒ 𝑎𝑎𝑏𝑐𝐵𝑐 ⇒ 𝑎𝑎𝑏𝐵𝑐𝑐 ⇒ 𝑎𝑎𝑏𝑏𝑐𝑐 = 𝑎2𝑏2𝑐2 ∈ 𝐿(𝐺); 
𝑆 ⇒ 𝑎𝑆𝐵𝑐 ⇒ 𝑎𝑎𝑆𝐵𝑐𝐵𝑐 ⇒ ⋯ ⇒ 𝑎𝑛−1𝑆(𝐵𝑐)𝑛−1 ⇒ 𝑎𝑛𝑏𝑐𝐵𝑐 … 𝐵𝑐 ⇒ ⋯ ⇒ 𝑎𝑛𝑏𝐵𝑛−1𝑐𝑛 ⇒
⋯ ⇒ 𝑎𝑛𝑏𝑛𝑐𝑛 ∈ 𝐿(𝐺). 
Logo, 𝐿(𝐺) = {𝑎𝑛𝑏𝑛𝑐𝑛 | 𝑛 ≥ 1}. 
 
Hierarquia de Chomsky 
 
Vamos fazer a classificação de gramáticas utilizando a forma das produções. 
Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma gramática, 𝑉 = 𝑁 ∪ 𝑇. A classificação de Chomsky tem 4 tipos de 
gramáticas: 
Tipo 0 (Gramáticas não restringidas) 
➢ Pode ter as produções de qualquer forma. 
Tipo 1 (Gramáticas dependentes do contexto ou gramáticas sensíveis ao contexto, GSC) 
➢ Pode ter só as produções da forma 𝑢 → 𝑣, onde 𝑢, 𝑣 ∈ 𝑉+, e |𝑢| ≤ |𝑣|. 
Tipo 2 (Gramáticas independentes (livres) do contexto, GIC) 
➢ Pode ter só as produções da forma 𝐴 → 𝛿, onde 𝐴 ∈ 𝑁, e 𝛿 ∈ 𝑉∗. 
Tipo 3 (Gramáticas regulares, GR) 
➢ Pode ter só as produções da forma 𝐴 → 𝑥𝐵| 𝑥 |𝜆, onde 𝐴, 𝐵 ∈ 𝑁, e 𝑥 ∈ 𝑇. 
𝑛 − 1 
 Linguagens Formais e Autómatos 
93 
Exemplo 8.5. Achar os tipos de gramáticas de Exemplos 8.1 – 8.4. 
Solução. Exemplo 8.1 – GIC (Tipo 2); Exemplo 8.2 – GIC (Tipo 2); Exemplo 8.3 – GIC (Tipo 2); 
Exemplo 8.4 – GSC (Tipo 1). 
Definição 8.5. (Classificação de linguagens) 
Uma linguagem 𝐿 é do tipo 𝑖 (𝑖 = 0, 1, 2, 3) se existe uma gramática 𝐺 do tipo 𝑖 que gere 𝐿, 
𝐿 = 𝐿(𝐺). 
Designemos por ℒ𝑖 a classe das linguagens do tipo 𝑖 (𝑖 = 0, 1, 2, 3), então: 
ℒ0 – linguagens recursivamente enumeráveis; 
ℒ1– linguagens dependentes de contexto ou sensíveis ao contexto (LSC); 
ℒ2– linguagens independentes de contexto (LIC); 
ℒ3– linguagens regulares (LR). 
Tem-se as seguintes inclusões estritas; 
 ℒ3 ⊂ ℒ2 ⊂ ℒ1 ⊂ ℒ0. 
Por exemplo, a linguagem do Exemplo 8.1 𝐿 = {𝑎𝑛𝑏𝑛| 𝑛 ≥ 0} ∈ ℒ2 e 𝐿 = {𝑎
𝑛𝑏𝑛| 𝑛 ≥ 0} ∉ ℒ3. 
A linguagem do Exemplo 8.4 𝐿 = {𝑎𝑛𝑏𝑛𝑐𝑛| 𝑛 ≥ 1} ∈ ℒ1 e 𝐿 = {𝑎
𝑛𝑏𝑛𝑐𝑛| 𝑛 ≥ 1} ∉ ℒ2. 
 
Autómatos e Gramáticas Regulares 
 
Mostraremos que as gramáticas regulares do tipo 3 realmente geram todas as linguagens regulares 
no sentido de Capítulo 3. 
Exemplo 8.6. Seja 𝐴 AFD seguinte: 
 
 
 
 
Achar uma gramática 𝐺 tal que 𝐿(𝐴) = 𝐿(𝐺). 
𝑞0 
b 
𝐴: 𝑞1 
b 
a 
a 
 Linguagens Formais e Autómatos 
94 
Solução. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑞0, 𝑞1}, 𝑇 = {𝑎, 𝑏}, 𝑆 = 𝑞0, 
𝑃 = {𝑞0 → 𝑏𝑞0 , 𝑞0 → 𝑎𝑞1, 𝑞1 → 𝑏𝑞1, 𝑞1 → 𝑎𝑞0, 𝑞1 → 𝜆 } 
Vamos encontrar o caminho de computação para a palavra 𝑤 = 𝑏𝑎: 
 𝑏𝑎 ∈ 𝐿(𝐴). 
Também, existe derivação de 𝑤 = 𝑏𝑎 em 𝐺: 𝑞0 ⇒ 𝑏𝑞0 ⇒ 𝑏𝑎𝑞1 ⇒ 𝑏𝑎 ∈ 𝐿(𝐺). Não é difícil 
mostrar que 𝐿(𝐴) = 𝐿(𝐺). 
Teorema 8.1. Seja 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) um autómato. 
Consideremos 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = 𝑄, 𝑇 = Σ, 𝑆 = 𝑞0, 
𝑃 = {𝑞 → 𝑎 𝑝|𝛿(𝑞, 𝑎) = 𝑝} ∪ {𝑝 → 𝜆 |𝑝 ∈ 𝐹}. 
Então, 𝐿(𝐴) = 𝐿(𝐺). 
Demonstração. Vamos demonstrar que 𝐿(𝐴) ⊆ 𝐿(𝐺). 
Seja 𝑤 ∈ 𝐿(𝐴), 
1) Se 𝑤 = 𝜆 então 𝑞0 ∈ 𝐹. Existe produção 𝑞0 → 𝜆 ∈ 𝑃. Logo 𝑞0 ⇒ 𝜆 ∈ 𝐿(𝐺). 
2) Suponhamos que 𝑤 ≠ 𝜆 e 𝑤 ∈ 𝐿(𝐴). Então 𝑤 = 𝑎1𝑎2 … 𝑎𝑛 e existe caminho de 
computação , 𝑞𝑛 ∈ 𝐹. Assim, em 𝐺 
existem produções 𝑞0 → 𝑎1𝑞1, 𝑞𝑖−1 → 𝑎𝑖𝑞𝑖 , 𝑖 = 2, … , 𝑛, 𝑞𝑛 → 𝜆 e existe derivação 
𝑞0 ⇒ 𝑎1𝑞1 ⇒ 𝑎1𝑎2𝑞2 ⇒ ⋯ ⇒ 𝑎1𝑎2 … 𝑎𝑛𝑞𝑛 ⇒ 𝑎1𝑎2 … 𝑎𝑛 = 𝑤 ∈ 𝐿(𝐺) 
Logo, 𝐿(𝐴) ⊆ 𝐿(𝐺). 
Analogamente podemos demonstrar que 𝐿(𝐺) ⊆ 𝐿(𝐴). 
Suponhamos que 𝑥 ∈ 𝐿(𝐴). 
Se 𝑥 = 𝜆, então 𝐺 tem produção 𝑆 → 𝜆 (Por quê?). 
Então, 𝑆 = 𝑞0 ∈ 𝐹 e 𝜆 ∈ 𝐿(𝐴). 
Seja 𝑥 ≠ 𝜆 e 𝑥 = 𝑎1𝑎2 … 𝑎𝑛, 𝑎𝑖 ∈ 𝑇 = Σ, 𝑖 = 1, 2, … , 𝑛. 
Existe uma derivação em 𝐺: 𝑆 = 𝑞0 ⇒ 𝑎1𝑞1 ⇒ 𝑎1𝑎2𝑞2 ⇒ ⋯ ⇒ 𝑎1𝑎2 … 𝑎𝑛𝑞𝑛 ⇒ 𝑎1𝑎2 … 𝑎𝑛. 
Devem existir produções em 𝐺: 𝑆 = 𝑞0 → 𝑎1𝑞1 , 𝑞1 → 𝑎2𝑞2, … , 𝑞𝑛−1 → 𝑎𝑛𝑞𝑛, 𝑞𝑛 → 𝜆. 
a 
𝑞0 𝑞0 
b 
𝑞1 
𝑎2 
𝑞0 𝑞1 
𝑎1 … 
𝑎𝑛 
𝑞𝑛 
 Linguagens Formais e Autómatos 
95 
Exixte um caminho de computação em 𝐴: 
 e 𝑞𝑛 ∈ 𝐹. 
Logo, 𝑥 = 𝑎1𝑎2 … 𝑎𝑛 ∈ 𝐿(𝐴) e 𝐿(𝐺) ⊆ 𝐿(𝐴). 
Assim, 𝐿(𝐴) ⊆ 𝐿(𝐺) e 𝐿(𝐺) ⊆ 𝐿(𝐴). Então, 𝐿(𝐴) = 𝐿(𝐺). O que foi preciso demonstrar. 
 
Exemplo 8.7. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma gramática regular, onde 𝑁 = {𝑆, 𝐶}, 𝑇 = {𝑎, 𝑏}, 
𝑃 = {𝑆 → 𝑏𝑆 , 𝑆 → 𝑎𝐶, 𝐶 → 𝑏𝐶, 𝐶 → 𝑏 }. Achar um autómato 𝐴 tal que 𝐿(𝐺) = 𝐿(𝐴). 
Solução. Podemos representar três primeiras produções 𝑆 → 𝑏𝑆 , 𝑆 → 𝑎𝐶, 𝐶 → 𝑏𝐶: 
 
 
 
Falta representar última produção 𝐶 → 𝑏. Mas em vez de produção 𝐶 → 𝑏 podemos considerar 
duas produções 𝐶 → 𝑏Φ e Φ → 𝜆. 
É facil ver que a gramática 𝐺1 = (𝑁1, 𝑇, 𝑃1, 𝑆) 𝑁1 = {𝑆, 𝐶, Φ}, 𝑇 = {𝑎, 𝑏} 
𝑃1 = {𝑆 → 𝑏𝑆 , 𝑆 → 𝑎𝐶, 𝐶 → 𝑏Φ, Φ → 𝜆 } é equivalente a gramática 𝐺, isto é 𝐿(𝐺) = 𝐿(𝐺1). 
Agora podemos construir o autómato 𝐴: 
 
 
 
𝐿(𝐴) = 𝐿(𝐺1) = 𝐿(𝐺). 
 
Teorema 8.2. 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma gramática regular e Σ = 𝑇, 𝑆 = 𝑞0, 𝑄 = 𝑁 ∪ {Φ}, 
𝐹 = {𝐶|𝐶 → 𝜆 ∈ 𝑃} ∪ {Φ}, 
𝛿(𝐶, 𝑎) = {𝐶′|𝐶 → 𝑎𝐶′ ∈ 𝑃} ∪ {Φ |𝐶 → 𝑎 ∈ 𝑃}. 
Seja autómato 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0). 
Então, 𝐿(𝐴) = 𝐿(𝐺). 
Dos teoremas 8.1, 8.2 e de Kleene segue 
𝑎1 
𝑞0 𝑞1 
𝑎2 
𝑞2 
𝑎𝑛 
… 𝑞𝑛 
𝑆 
b 
𝐶 
b 
a 
a b 
b b 
𝑆 𝐶 Φ 𝐴: 
𝑎3 
 
 Linguagens Formais e Autómatos 
96 
Teorema 8.3. Uma linguagem 𝐿 é regular (no sentido de Capítulo 3) se e só se existe uma 
gramática regular 𝐺 que gera 𝐿, isto é, 𝐿 = 𝐿(𝐺). 
 
Problemasresolvidos 
 
8.1. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {0,1}, 𝑃 = {𝑆 → 𝜆 | 0𝑆 |1𝑆 }. 
a) Que tipo tem gramática 𝐺? 
b) Obtem uma derivação para as palavras 01, 101 em 𝐺. 
c) Achar 𝐿(𝐺). 
Solução. a) 𝐺 tem tipo 3, GR. 
b) 𝑆 ⇒ 0𝑆 ⇒ 01𝑆 ⇒ 01 
 𝑆 ⇒ 1𝑆 ⇒ 10𝑆 ⇒ 101𝑆 ⇒ 101 
c) 𝐿(𝐺) = {0,1}∗. 
 
 
8.2. 
 
 
 
 
 
Para AFD 𝐴 achar uma GR 𝐺 tal que 𝐿(𝐴) = 𝐿(𝐺). 
Solução. 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴, 𝐵}, 𝑇 = {𝑎, 𝑏}, 
𝑃 = {𝑆 → 𝑎𝐴 | 𝑏𝐵, 𝐴 → 𝑎𝑆 | 𝑏𝐴 | 𝜆, 𝐵 → 𝑏𝑆|𝑎𝐴 | 𝜆 }. 
(Teorema 8.1). 
8.3. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), 𝑁 = {𝑆, 𝐴}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑏𝑆 | 𝑎𝐴 | 𝑏, 𝐴 → 𝑎𝑆|𝑏𝐴 | 𝑎 }. 
Achar AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐺). 
b 
𝐵 
b 
a 
a 
b 
𝐴 𝑆 𝐴: 
a 
 Linguagens Formais e Autómatos 
97 
Solução. 
 
 
 
 
 
8.4. Thomas A. Sudkamp, Languages and Machines, Examples 3.6.1, 3.6.2, 3.6.3 pp.79-82. 
8.5. Achar uma gramática regular 𝐺 que gera todas as palavras sobre {𝑎, 𝑏} de comprimento par. 
𝐿(𝐺) = {𝑤|𝑤 ∈ {𝑎, 𝑏}∗, |𝑤| é 𝑢𝑚 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑎𝑟}. 
Solução. Introduzimos duas variáveis não terminais 𝑆 e 𝐼 que vão servir como contadores. 𝑆 
significa que a forma sentencial tem um número par de símbolos terminais e 𝐼 significa que a 
forma sentencial tem um número ímpar de símbolos terminais. Assim, 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), 
𝑁 = {𝑆, 𝐼}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑎𝐼| 𝑏𝐼 |𝜆, 𝐼 → 𝑎𝑆| 𝑏𝑆}. 
Outro método. No início podemos construir o autómato 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐺) e depois 
utilizando Teorema 8.1 achar GR 𝐺. 
 
 
 
𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐼}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑎𝐼| 𝑏𝐼 |𝜆, 𝐼 → 𝑎𝑆| 𝑏𝑆}. 
 
8.6. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑎𝑆| 𝑏𝐴 |𝜆, 𝐴 → 𝑎𝐴| 𝑏𝑆}. 
a) Achar derivações das palavras bab, aba. 
b) Construir o autómato 𝐴 tal que 𝐿(𝐺) = 𝐿(𝐴). 
c) Achar a linguagem 𝐿(𝐺). 
Solução. a) 𝑆 ⇒ 𝑏𝐴 ⇒ 𝑏𝑎𝐴 ⇒ 𝑏𝑎𝑏𝑆 ⇒ 𝑏𝑎𝑏 
𝑆 ⇒ 𝑎𝑆 ⇒ 𝑎𝑏𝐴 ⇒ 𝑎𝑏𝑎𝐴 
a a 
b b 
𝑆 𝐴 Φ 𝐴: 
a 
b 
(Teorema 8.2). 
a,b 
a,b 
𝐼 𝑆 𝐴: 
 Linguagens Formais e Autómatos 
98 
Não existe a derivação da palavra aba. 
 
b) 
 
 
 
c) 𝐿(𝐺) = 𝐿(𝐴) são todas as palavras sobre {𝑎, 𝑏} que têm um número par de letras “b”. 
 
 
Problemas propostos 
 
8.7. Achar uma GR 𝐺 tal que 𝐿(𝐺) = 𝑎+𝑏∗. 
8.8. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑎𝑆𝑎| 𝑏𝑆𝑏 | 𝑎 | 𝑏 |𝜆}. 
a) Que tipo tem a gramática 𝐺? 
b) Achar derivações das palavras bab, abb. 
c) Achar a linguagem 𝐿(𝐺). 
 
8.9. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴, 𝐵}, 𝑇 = {𝑎, 𝑏}, 
𝑃 = {𝑆 → 𝑏𝑆|𝑎𝐴, 𝐴 → 𝑏𝑆| 𝑎𝐵, 𝐵 → 𝑎𝐵| 𝑏𝐵 |𝜆, }. 
a) Que tipo tem a gramática 𝐺? 
b) Achar derivações das palavras baab, abb. 
c) Construir o autómato 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐺). 
d) Achar a linguagem 𝐿(𝐺). 
 
8.10. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴, 𝐵}, 𝑇 = {𝑎, 𝑏}, 
𝑃 = {𝑆 → 𝑎𝑆| 𝑏𝐴 |𝜆, 𝐴 → 𝑎𝐴| 𝑏𝐵, 𝐵 → 𝑏}. 
Achar autómato 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐺). 
a 
b 
b 
a 
𝐴 𝑆 𝐴: 𝐿(𝐴) = 𝐿(𝐺) 
 Linguagens Formais e Autómatos 
99 
8.11. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴, 𝐶}, 𝑇 = {𝑎, 𝑏}, 
𝑃 = {𝑆 → 𝑎𝑆|𝑏𝐴 , 𝐴 → 𝑎𝐴| 𝑏𝐶, 𝐶 → 𝑎𝐶|𝜆}. 
Achar 𝐿(𝐺). 
8.12. Demonstrar Teorema 8.2. 
8.13. Demonstrar Teorema 8.3. 
 
 
Respostas 
 
8.7. 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐵}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑎𝑆|𝑎𝐵 , 𝐵 → 𝑏𝐵|𝜆}. 
 
8.8. a) Tipo 2, GIC. 
b) 𝑆 ⇒ 𝑏𝑆𝑏 ⇒ 𝑏𝑎𝑏; 
 𝑆 ⇒ 𝑎𝑆𝑎, derivação de abb não existe. 
c) 𝐿(𝐺) = {𝑤|𝑤 ∈ {𝑎, 𝑏}∗, 𝑤 = 𝑤𝑅}. 
 
8.9. a) Tipo 3, GR. 
b) 𝑆 ⇒ 𝑏𝑆 ⇒ 𝑏𝑎𝐴 ⇒ 𝑏𝑎𝑎𝐵 ⇒ 𝑏𝑎𝑎𝑏𝐵 ⇒ 𝑏𝑎𝑎𝑏; 
 𝑆 ⇒ 𝑎𝐴 ⇒ 𝑎𝑏𝑆 ⇒ 𝑎𝑏𝑏𝑆, derivação de abb não existe. 
 
 
c) 
 
 
d) 𝐿(𝐺) = (𝑎 + 𝑏)∗𝑎𝑎(𝑎 + 𝑏)∗. 
 
a a 
a,b b 
𝑆 𝐴 𝐵 𝐴: 
b 
 Linguagens Formais e Autómatos 
100 
8.10. 
 
 
8.11. 𝐿(𝐺) = 𝑎∗𝑏𝑎∗𝑏𝑎∗. 
 
 
 
b b 
a 
b 
𝐴: 
a 
𝑆 𝐴 𝐵 Φ 
 Linguagens Formais e Autómatos 
101 
Capítulo 9 
 
Gramáticas Independentes de Contexto. Árvores de Derivação. 
Ambiguidade 
 
Definição 9.1. Uma gramática 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) chama-se gramática independente de contexto 
(GIC) se todas as produções de 𝐺 tem a forma 
𝐴 → 𝛿, 𝐴 ∈ 𝑁, 𝛿 ∈ (𝑁 ∪ 𝑇)∗. 
A linguagem 𝐿 gerada por uma GIC 𝐺 chama-se linguagem independente de contexto (LIC). 
Muitas linguagens de programação utilizam parênteses. Os parênteses devem ser balanceados. 
 
Definição 9.2. A sequência de parênteses é balanceada (bem casada) se para cada parêntese 
esquerdo “(“ existe o parêntese direito “)” correspondente à direita do primeiro. A linguagem de 
todos parênteses balanceados designa-se por 𝐿𝑏𝑎𝑙. 
Exemplo 9.1. ( ), (( )), (( ) ( )), 𝜆 − 𝑠𝑒𝑞𝑢ê𝑛𝑐𝑖𝑎𝑠 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝑎𝑑𝑎𝑠; 
)(, ((), ()( − 𝑠𝑒𝑞𝑢ê𝑛𝑐𝑖𝑎𝑠 𝑛ã𝑜 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝑎𝑑𝑎𝑠. 
Exemplo 9.2. Uma gramática que gere 𝐿𝑏𝑎𝑙 é 𝐺𝑏𝑎𝑙 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {(, )}, 
𝑃 = {𝑆 → 𝑆𝑆|(𝑆)|𝜆}. Então 𝐿𝑏𝑎𝑙 = 𝐿(𝐺𝑏𝑎𝑙). 
A produção 𝑆 → 𝜆 significa que 𝜆 ∈ 𝐿(𝐺𝑏𝑎𝑙). 
A produção 𝑆 → (𝑆) significa que se vamos por parênteses sobre uma palavra de 𝐿(𝐺𝑏𝑎𝑙) o 
resultado pertence a 𝐿(𝐺𝑏𝑎𝑙). 
A produção 𝑆 → 𝑆𝑆 significa que a concatenação de duas palavras de 𝐿(𝐺𝑏𝑎𝑙) pertence a 𝐿(𝐺𝑏𝑎𝑙). 
Também, podemos dar a definição recursiva de 𝐿𝑏𝑎𝑙. 
Definição 9.3. 
Base: 𝜆 ∈ 𝐿𝑏𝑎𝑙 . 
 Linguagens Formais e Autómatos 
102 
Passo Recursivo: Se 𝑥 ∈ 𝐿𝑏𝑎𝑙 , então (𝑥) ∈ 𝐿𝑏𝑎𝑙; 
 Se 𝑥 ∈ 𝐿𝑏𝑎𝑙 , então 𝑥𝑥 ∈ 𝐿𝑏𝑎𝑙. 
Fecho: Qualquer palavra de 𝐿𝑏𝑎𝑙 ou da Base ou do Passo Recursivo. 
Teorema 9.1. Qualquer sequência de parênteses balanceados é gerada pela gramática 𝐺𝑏𝑎𝑙. 
Demonstração. Vamos usar o princípio da indução matemática. 
Base: 𝜆 ∈ 𝐿(𝐺𝑏𝑎𝑙). Realmente 𝑆 ⇒ 𝜆 ∈ 𝐿(𝐺𝑏𝑎𝑙). 
Passo Indutivo: Suponhamos que para todo 𝑛 par e 𝑛 ≥ 0 se 𝑥 é balanceada e |𝑥| ≤ 𝑛 então 
𝑥 ∈ 𝐿(𝐺𝑏𝑎𝑙). 
Seja |𝑥| = 𝑛 + 2 
1) Se 𝑥 = (𝑦), então 𝑦 é balanceada e |𝑦| = 𝑛. Logo, 𝑦 ∈ 𝐿(𝐺𝑏𝑎𝑙) e existe derivação 𝑆 ⇒
∗ 𝑦 
em 𝐺𝑏𝑎𝑙. Então, existe derivação 𝑆 ⇒ (𝑆) ⇒
∗ (𝑦) = 𝑥 em 𝐺. Assim, 𝑥 ∈ 𝐿(𝐺𝑏𝑎𝑙). 
2) Se 𝑥 = (𝑦) e 𝑦 não é balanceada, então 𝑥 = (𝑦1)(𝑦2) = 𝑥1𝑥2, onde 𝑥1 e 𝑥2 são 
balanceados, e |𝑥1| ≤ 𝑛, |𝑥2| ≤ 𝑛. 
Logo, 𝑥1, 𝑥2 ∈ 𝐿(𝐺𝑏𝑎𝑙). Existem derivações em 𝐺 𝑆 ⇒
∗ 𝑥1 e 𝑆 ⇒
∗ 𝑥2. Então, existe derivação 
em 𝐺 𝑆 ⇒ 𝑆𝑆 ⇒∗ 𝑥1𝑆 ⇒
∗ 𝑥1𝑥2 = 𝑥 ∈ 𝐿𝑏𝑎𝑙. 
Assim, qualquer sequência balanceada de comprimento par pertence a linguagem 𝐿(𝐺𝑏𝑎𝑙). 
 Outro exemplo importante onde aplica-se GIC é a linguagem de enunciados condicionais 
(if ... else). Em várias linguagens de programação if pode entrar sem else ou pode ser associado 
com um else. 
 Por exemplo, as palavras ieie, iie, ii são correctas; as palavras ei, ieei não são correctas. 
Exemplo 9.3. (Gramática que gera a linguagem de enunciados condicionais) 
𝐺𝑒𝑐 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {𝑖, 𝑒}, 𝑃 = {𝑆 → 𝑆𝑆| 𝑖𝑆 |𝑖𝑆𝑒|𝜆}. 
 
 
𝑦 
 Linguagens Formais e Autómatos 
103 
Árvores de derivação. Derivações esquerda e direita. 
Ambiguidade 
 
Exemplo 9.4. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝐸) uma GIC para expressões simples, onde 𝑁 = {𝐸, 𝐼}; 
 𝑇 = {+,∗, (, ), 𝑎, 𝑏}; 𝑃 = {𝐸 → 𝐸 + 𝐸| 𝐸 ∗ 𝐸 |(𝐸)|𝐼, 𝐼 → 𝑎|𝑏}. 
 
Representação de produções por árvoresEm geral 
 
 
 
 
E 
E E + 
𝐸 → 𝐸 + 𝐸 
E 
( ) E 
𝐸 → (𝐸) 
E 
𝐼 
𝐸 → 𝐼 
E 
𝜆 
𝐸 → 𝜆 
A 
𝛿 
𝐴 → 𝛿 
 Linguagens Formais e Autómatos 
104 
𝛿 são símbolos de corpo ordenados da esquerda para a direita. 
Consideremos uma derivação na gramática do Exemplo 9.3. Por exemplo, 
𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐸 + 𝐸 ∗ 𝐸 
As árvores correspondentes 
 
 
 
 
 
 
Definição 9.4. (Construção de árvore de derivação). 
Sejam 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma GIC e 𝑆 ⇒∗ 𝑤 uma derivação em 𝐺. A árvore de derivação (AD) 
para 𝑆 ⇒∗ 𝑤 podemos construir da maneira iterativa: 
1) Inicializamos AD com único vértice (raíz) 𝑆; 
2) Se 𝐴 → 𝑥1𝑥2 … 𝑥𝑛 , 𝑥𝑖 ∈ (𝑁 ∪ 𝑇) 𝑖 = 1, 2, … , 𝑛 uma produção que se aplica na 
derivação para a forma sentencial 𝑢𝐴𝑣, então adicionamos 𝑥1, 𝑥2, … , 𝑥𝑛 como filhos de 𝐴 
na árvore de derivação; 
3) Se 𝐴 → 𝜆 é a produção que se aplica na derivação para a forma sentencial 𝑢𝐴𝑣, então 
adicionamos 𝜆 como único filho de 𝐴 em AD; 
No final, as folhas de AD (que é preciso ler da esquerda para a direita) representam a palavra 𝑤 
que é o resultado da derivação 𝑆 ⇒∗ 𝑤. 
Exemplo 9.5. Achar AD’s para duas derivações da palavra 𝑎 + 𝑎 ∗ 𝑎. Gramática do Exemplo 9.4. 
Solução. 
1) 𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐸 + 𝐸 ∗ 𝐸 ⇒ 𝐼 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐼 ∗ 𝐸 ⇒ 𝑎 + 𝑎 ∗ 𝐸 ⇒
 𝑎 + 𝑎 ∗ 𝐼 ⇒ 𝑎 + 𝑎 ∗ 𝑎 
E 
E E + 
𝐸 ⟹ ⟹ 
E 
E E + 
E E * 
 Linguagens Formais e Autómatos 
105 
 
 
 
 
 
 
 
 
 
2) 𝐸 ⇒ 𝐸 ∗ 𝐸 ⇒ 𝐸 + 𝐸 ∗ 𝐸 ⇒ 𝐼 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐼 ∗ 𝐸 ⇒ 𝑎 + 𝑎 ∗ 𝐸 ⇒
 𝑎 + 𝑎 ∗ 𝐼 ⇒ 𝑎 + 𝑎 ∗ 𝑎 
 
 
 
 
 
 
 
 
 
 
 
Definição 9.5. Uma GIC 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) chama-se ambígua se existe pelo menos uma palavra 
𝑤 ∈ 𝐿(𝐺) que tem árvores de derivação diferentes. Se cada palavra de 𝐿(𝐺) tem única árvore de 
derivação, então 𝐺 chama-se não ambígua ou inambígua. 
Como mostrou Exemplo 9.5 a gramática do Exemplo 9.4 é ambígua. A palavra 𝑎 + 𝑎 ∗ 𝑎 ∈ 𝐿(𝐺) 
tem duas árvores de derivação diferentes. 
I 
a 
E 
E E + 
E E * 
I 
a 
I 
a 
I 
a 
E 
E E * 
E E + I 
a I 
a 
 Linguagens Formais e Autómatos 
106 
Por exemplo, se 𝑎 = 3 então o resultado aplicando primeira AD é igual a 3 + 3 ∗ 3 = 12, 
aplicando segunda AD é igual a (3 + 3) ∗ 3 = 18. 
Nota 9.1. As derivações diferentes podem ter AD’s iguais. 
Exemplo 9.6. (GIC do Exemplo 9.4) 
1) 𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐼 + 𝐸 ⇒ 𝑎 + 𝐸 ⇒ 𝑎 + 𝐼 ⇒ 𝑎 + 𝑏 
 
 
 
 
 
 
 
 
 
2) 𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐸 + 𝐼 ⇒ 𝐼 + 𝐼 ⇒ 𝐼 + 𝑏 ⇒ 𝑎 + 𝑏 
 
 
 
 
 
 
 
 
Assim, o problema de ambiguidade não é nas derivações diferentes. O problema de ambiguidade 
nas AD’s diferentes para a mesma palavra. 
 
 
I 
a 
E 
E E + 
I 
b 
I 
a 
E 
E E + 
I 
b 
 Linguagens Formais e Autómatos 
107 
Derivações esquerdas e direitas 
Definição 9.6. Uma derivação 𝛼 ⇒∗ 𝛽 numa GIC 𝐺 chama-se derivação esquerda (direita) se 
em cada passo da derivação a produção aplica-se para o símbolo não terminal que está mais à 
esquerda (direita) na forma sentencial correspondente. Neste caso utilizam-se os símbolos 
𝛼 ⇒𝑒
 ∗ 𝛽 (𝛼 ⇒𝑟
 ∗ 𝛽). De costume, vamos aplicar a derivação esquerda. 
Exemplo 9.7. Achar as derivações esquerdas da palavra 𝑎 + 𝑎 ∗ 𝑎. Gramática do Exemplo 9.4. 
Solução. 
1) 𝐸 ⇒𝑒
 𝐸 + 𝐸 ⇒𝑒
 𝐼 + 𝐸 ⇒𝑒
 𝑎 + 𝐸 ⇒𝑒
 𝑎 + 𝐸 ∗ 𝐸 ⇒𝑒
 𝑎 + 𝐼 ∗ 𝐸 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝐸 ⇒𝑒
 
𝑎 + 𝑎 ∗ 𝐼 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝑎 
Árvore para esta derivação: 
 
 
 
 
 
 
 
 
 
 
 
2) 𝐸 ⇒𝑒
 𝐸 ∗ 𝐸 ⇒𝑒
 𝐸 + 𝐸 ∗ 𝐸 ⇒𝑒
 𝐼 + 𝐸 ∗ 𝐸 ⇒𝑒
 𝑎 + 𝐸 ∗ 𝐸 ⇒𝑒
 𝑎 + 𝐼 ∗ 𝐸 ⇒𝑒
 
𝑎 + 𝑎 ∗ 𝐸 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝐼 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝑎 
 
AD correspondente: 
 
I 
a 
E 
E E + 
E E * 
I 
a 
I 
a 
 Linguagens Formais e Autómatos 
108 
 
 
 
 
 
 
 
 
 
 
Podemos ver que derivações esquerdas diferentes têm AD’s diferentes. 
Teorema 9.2. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma GIC. Uma palavra 𝑤 ∈ 𝐿(𝐺) se e só se existe 𝑆 ⇒𝑒
 ∗ 𝑤. 
Este teorema significa que se existe uma derivação 𝑆 ⇒∗ 𝑤 ∈ 𝐿(𝐺) então existe derivação 
esquerda 𝑆 ⇒𝑒
 ∗ 𝑤 ∈ 𝐿(𝐺). 
Nota 9.2. O teorema 9.2 não é valido para as formas sentenciais. 
Exemplo 9.8. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴, 𝐵}; 𝑇 = {𝑎, 𝑏}; 
𝑃 = {𝑆 → 𝐴𝐵, 𝐴 → 𝑎𝐴|𝜆, 𝐵 → 𝑏𝐵|𝜆}. 
Nesta gramática existe derivação 𝑆 ⇒ 𝐴𝐵 ⇒ 𝐴. Mas não existe derivação esquerda 𝐴 de 𝑆. 
Teorema 9.3. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) uma GIC e 𝐴 uma AD cuja raíz é 𝑆 e as folhas representam 
uma palavra 𝑤 ∈ 𝐿(𝐺). Então, existe uma derivação esquerda 𝑆 ⇒𝑒
 ∗ 𝑤 ∈ 𝐿(𝐺) em 𝐺 cuja AD 
é 𝐴. 
Assim, existe uma bijecção entre as AD’s para as palavras 𝐿(𝐺) e as derivações esquerdas para 
as palavras de 𝐿(𝐺). Então podemos dar uma outra definição de ambiguidade de GIC. 
Definição 9.7. Uma GIC 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) é ambígua se e só se existe pelo menos uma palavra 
𝑤 ∈ 𝐿(𝐺) que tem derivações esquerdas diferentes. 
 
I 
a 
E 
E E * 
E E + I 
a I 
a 
 Linguagens Formais e Autómatos 
109 
Eliminação de ambiguidade 
 
Como uma linguagem pode ser gerada por várias gramáticas parece que ambiguidade é uma 
propriedade da gramática e não é da linguagem. 
Vamos eliminar ambiguidade da gramática do Exemplo 9.4. Por outras palavras, é preciso achar 
uma gramática equivalente que é inambígua. 
Exemplo 9.9. Eliminar ambiguidade da gramática do Exemplo 9.4. 
Solução. No Exemplo 9.5 construímos duas AD’s diferentes para a palavra 𝑎 + 𝑎 ∗ 𝑎 o que 
significa que a gramática correspondente é ambíguia 
1) 2) 
 
 
 
 
 
 
 
 
Para eliminar ambiguidade é preciso achar uma gramática equilavente onde só a primeira AD é 
correcta. 
A sequências de operações idênticas podemos agrupar da esquerda para direita (ou da direita para 
esquerda). As operações + e * são associativas e por isso não é importante que maneira escolher: 
1) ou 2) 
 
 
 
I 
a 
E 
E E + 
E E * 
I 
a 
I 
a 
I 
a 
E 
E E * 
E E + I 
a I 
a 
E 
E E + 
(*) 
 
E E + 
(*) 
 
E 
E E + 
(*) 
 
E E + 
(*) 
 Linguagens Formais e Autómatos 
110 
Mas para eliminar ambiguidade escolhemos o segundo caso. Este significa que 𝐸 + 𝐸 + 𝐸 =
(𝐸 + 𝐸) + 𝐸 e 𝐸 ∗ 𝐸 ∗ 𝐸 = (𝐸 ∗ 𝐸) ∗ 𝐸. 
Para resolver o problema de ambiguidade dividimos as expressões por vários níveis: 
1) Factor é uma expressão que não podemos partir usando operações + e *. Os factores da 
nossa linguagem são identificadores e quaisquer expressões parentisadas. Não é importante 
o que temos dentro de parentesis. 
 
 
 
 
2) Termo é uma expressão que não podemos partir por +. No nosso caso (temos duas 
operações + e *) o termo é um produto de um ou mais que um factor. 
Por exemplo, para termo 𝑎 ∗ 𝑏 podemos adicionar à esquerda 𝑎 ∗ e recebemos 𝑎 ∗ 𝑎 ∗ 𝑏 que 
é igual a (𝑎 ∗ 𝑎) ∗ 𝑏. Logo, partimos o termo 𝑎 ∗ 𝑏. 
Não podemos partir o termo 𝑎 ∗ 𝑏 adicionando 𝑎 + à esquerda ou à direita. Realmente, 
𝑎 + 𝑎 ∗ 𝑏 é igual a 𝑎 + (𝑎 ∗ 𝑏) e 𝑎 ∗ 𝑏 + 𝑎 é igual a (𝑎 ∗ 𝑏) + 𝑎. 
 
 
 
3) Expressão é qualquer expressão possível que podemos partir com operações * ou +. 
Assim, as expressões no nosso caso são somas de um ou mais que um termo. 
 
 
 
Assim, a nova gramática inambígua equivalente (gera a mesma linguagem) é 𝐺1 = (𝑁, 𝑇, 𝑃, 𝑆), 
onde 𝑁 = {𝐸, 𝑇, 𝐹,𝐼}; 𝑇 = {𝑎, 𝑏,∗, +, (, )}; 
𝑃 = {𝐸 → 𝐸 + 𝑇|𝑇, 𝑇 → 𝑇 ∗ 𝐹|𝐹, 𝐹 → (𝐸)|𝐼, 𝐼 → 𝑎|𝑏}; 𝑆 = 𝐸. 
Vamos achar a derivação esquerda e AD para palavra 𝑎 + 𝑎 ∗ 𝑎: 
F 
I 
F 
(E) 
T 
* 
E 
+ 
 Linguagens Formais e Autómatos 
111 
𝐸 ⇒𝑒
 𝐸 + 𝑇 ⇒𝑒
 𝑇 + 𝑇 ⇒𝑒
 𝐹 + 𝑇 ⇒𝑒
 𝐼 + 𝑇 ⇒𝑒
 𝑎 + 𝑇 ⇒𝑒
 𝑎 + 𝑇 ∗ 𝐹 ⇒𝑒
 𝑎 + 𝐹 ∗ 𝐹 ⇒𝑒
 
𝑎 + 𝐼 ∗ 𝐹 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝐹 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝐼 ⇒𝑒
 𝑎 + 𝑎 ∗ 𝑎 
 
 
 
 
 
 
 
 
 
 
 
 
Agora derivação esquerda e AD para palavra 𝑎 + 𝑎 ∗ 𝑎 são únicas. 
 
Linguagens inerentemente ambíguas 
 
Definição 9.8. Uma LIC 𝐿 chama-se inerentemente ambígua se toda a gramática que gera 𝐿 é 
ambígua. 
Exemplo 9.10. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), uma GIC, onde 𝑁 = {𝑆, 𝐴, 𝐵, 𝐶, 𝐷}; 𝑇 = {𝑎, 𝑏, 𝑐, 𝑑}; 
𝑃 = {𝑆 → 𝐴𝐵|𝐶, 𝐴 → 𝑎𝐴𝑏|𝑎𝑏, 𝐵 → 𝑐𝐵𝑑|𝑐𝑑, 𝐶 → 𝑎𝐶𝑑|𝑎𝐷𝑑 , 𝐷 → 𝑏𝐷𝑐|𝑏𝑐}. A linguagem 
𝐿(𝐺) é inerentemente ambígua. 
Solução. Nesta gramática existem as produções para derivar as palavras da forma 
{𝑎𝑛𝑏𝑛𝑐𝑚𝑑𝑚|𝑛, 𝑚 ≥ 1} = 𝐿1 e outras produções para derivar as palavras da forma 
{𝑎𝑛𝑏𝑚𝑐𝑚𝑑𝑛|𝑛, 𝑚 ≥ 1} = 𝐿2. 𝐿(𝐺) = 𝐿1 ∪ 𝐿2 e 𝐿1 ∩ 𝐿2 ≠ ∅, 𝐿1 ∩ 𝐿2 = {𝑎
𝑛𝑏𝑛𝑐𝑛𝑑𝑛|𝑛 ≥ 1}. 
T 
F 
E 
E T + 
T F * 
F 
I 
I 
a I 
a a 
 Linguagens Formais e Autómatos 
112 
As palavras de 𝐿1 ∩ 𝐿2 podemos derivar aplicando as produções para 𝐿1 e tambem podemos 
derivar aplicando as produções para 𝐿2. Por exemplo, 
1) 𝑆 ⇒𝑒
 𝐴𝐵 ⇒𝑒
 𝑎𝐴𝑏𝐵 ⇒𝑒
 𝑎𝑎𝑏𝑏𝐵 ⇒𝑒
 𝑎𝑎𝑏𝑏𝑐𝐵𝑑 ⇒𝑒
 𝑎𝑎𝑏𝑏𝑐𝑐𝑑𝑑 
2) 𝑆 ⇒𝑒
 𝐶 ⇒𝑒
 𝑎𝐶𝑑 ⇒𝑒
 𝑎𝑎𝐷𝑑𝑑 ⇒𝑒
 𝑎𝑎𝑏𝐷𝑐𝑑𝑑 ⇒𝑒
 𝑎𝑎𝑏𝑏𝑐𝑐𝑑𝑑 
É claro que qualquer gramática que gera 𝐿(𝐺) deve ter uma derivação esquerda para as palavras 
de 𝐿1 e ter outra derivação esquerda para palavras de 𝐿2. Assim, devem existir derivações 
esquerdas diferentes para cada palavra de 𝐿1 ∩ 𝐿2. 
Não existe o algoritmo que para qualquer GIC 𝐺 responde 𝐺 é ambígua ou não. Logo o 
problema de ambiguidade para GIC’s é indecidível. 
O problema de saber se uma LIC arbitrátia é inerentemente ambígua também é indecidível. 
Mas existem as técnicas que permitem eliminar ambiguidade em certos casos de interesse. 
 
Lema de Repetição para linguagens independentes de contexto 
 
Teorema 9.4. (Lema de Repetição para LIC’s) 
Seja 𝐿 uma LIC. Existe um número 𝑛 que depende de 𝐿 tal que se 𝑧 ∈ 𝐿 e |𝑧| > 𝑛 então 
𝑧 = 𝑢𝑣𝑤𝑥𝑦 onde: 
1) |𝑣𝑤𝑥| ≤ 𝑛; 
2) |𝑣| + |𝑥| > 0; 
3) 𝑢𝑣𝑖𝑤𝑥𝑖𝑦 ∈ 𝐿 e para todo 𝑖 ≥ 0. 
Exemplo 9.11. Demonstrar que 𝐿 = {𝑎𝑖𝑏𝑖𝑐𝑖| 𝑖 ≥ 0} não é LIC. 
Solução. Suponhamos que 𝐿 é uma LIC. 
Pelo Lema de Repetição existe um número 𝑛. Seja 𝑧 = 𝑎𝑛𝑏𝑛𝑐𝑛. Então, 𝑧 ∈ 𝐿 e |𝑧| = 3𝑛 > 𝑛. 
Logo, 𝑧 = 𝑢𝑣𝑤𝑥𝑦 onde |𝑣𝑤𝑥| ≤ 𝑛 e |𝑣| + |𝑥| > 0. 
 Linguagens Formais e Autómatos 
113 
 
 
Assim, 𝑣𝑤𝑥 ou entre a’s ou entre a’s e b’s, ou entre b’s, ou entre b’s e c’s ou entre c’s. Em qualquer 
caso a palavra 𝑢𝑣2𝑤𝑥2𝑦 ∉ 𝐿. É uma contradição com Lema de Repetição. Logo 𝐿 não é LIC. 
 
Problemas resolvidos 
 
9.1. Achar uma GIC 𝐺 que gera a linguagem de palíndromos 𝐿𝑝𝑎𝑙 = {𝑤|𝑤 ∈ {𝑎, 𝑏}, 𝑤 = 𝑤
𝑅}. 
Solução. 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝜆|𝑎𝑆𝑎|𝑏𝑆𝑏}. 
Produção 𝑆 → 𝜆 significa que 𝜆 é palíndromo. 
Produções 𝑆 → 𝑎𝑆𝑎|𝑏𝑆𝑏 significam que se 𝑆 é palíndromo então 𝑎𝑆𝑎 e 𝑏𝑆𝑏 também são 
palíndromos. 
9.2. Demonstrar que a linguagem de enunciados condicionais 𝐿𝑒𝑐 não é linguagem regular. 
Solução. Vamos usar o lema de repetição para linguagens regulares. 
Suponhamos que 𝐿𝑒𝑐 é LR. Então, 𝐿𝑒𝑐
𝑅 também é LR. Assim, existe uma constante 𝑛 que depende 
de 𝐿𝑒𝑐
𝑅 Escolhemos um número 𝑘 ≥ 𝑛. A palavra 𝑥 = 𝑒𝑘𝑖𝑘 ∈ 𝐿𝑒𝑐
𝑅 e |𝑥| = 2𝑘 > 𝑛. Logo, 
𝑥 = 𝑢𝑣𝑤 onde |𝑢𝑣| ≤ 𝑛 e |𝑣| ≥ 1. Pelo lema de repetição 𝑢𝑣2𝑤 ∈ 𝐿𝑒𝑐
𝑅. Mas 𝑢𝑣2𝑤 = 𝑒𝑚𝑖𝑘 
onde 𝑚 > 𝑛. Assim 𝑢𝑣2𝑤 ∉ 𝐿𝑒𝑐
𝑅. É uma contradição. Logo, 𝐿𝑒𝑐
𝑅 não é LR. Portanto, 𝐿𝑒𝑐 
também não é LR. 
9.3. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝑎𝑆𝑏|𝑎𝑆𝑏𝑏|𝜆}. 
a) Mostrar que 𝐺 é ambígua. 
b) Achar 𝐿(𝐺). 
c) Eliminar ambiguidade (achar 𝐺′ inambígua equivalente). 
d) Construir AD’s para 𝑎2𝑏3 nas gramáticas 𝐺 e 𝐺′. 
vwx 
𝑥 = 𝑎 … 𝑎 𝑏 … 𝑏 𝑐 … 𝑐 
n n n 
 Linguagens Formais e Autómatos 
114 
Solução. 
a) 1) 𝑆 ⇒𝑒
 𝑎𝑆𝑏 ⇒𝑒
 𝑎𝑎𝑆𝑏𝑏𝑏 ⇒𝑒
 𝑎𝑎𝑏𝑏𝑏 = 𝑎2𝑏3 
 2) 𝑆 ⇒𝑒
 𝑎𝑆𝑏𝑏 ⇒𝑒
 𝑎𝑎𝑆𝑏𝑏𝑏 ⇒𝑒
 𝑎𝑎𝑏𝑏𝑏 = 𝑎2𝑏3 
A palavra 𝑎2𝑏3 ∈ 𝐿(𝐺) e tem duas derivações esquerdas diferentes. Logo, 𝐺 é ambígua. 
b) 𝐿(𝐺) = {𝑎𝑛𝑏𝑚|0 ≤ 𝑛 ≤ 𝑚 ≤ 2𝑛} 
c) Uma estratégia para eliminar ambiguidade no início produzir a’s com único b 
correspondente e depois produzir a’s com dois b’s correspondentes. 
Assim, 𝑃′ = {𝑆 → 𝑎𝑆𝑏|𝐴|𝜆, 𝐴 → 𝑎𝐴𝑏𝑏|𝑎𝑏𝑏}. 
Agora a derivação esquerda para palavra 𝑎2𝑏3 ∈ 𝐿(𝐺′) é única 
𝑆 ⇒𝑒
 𝑎𝑆𝑏 ⇒𝑒
 𝑎𝐴𝑏 ⇒𝑒
 𝑎𝑎𝑏𝑏𝑏 = 𝑎2𝑏3 
Assim, 𝐺′ = (𝑁′, 𝑇, 𝑃′, 𝑆), onde 𝑁′ = {𝑆, 𝐴}, 𝑇 = {𝑎, 𝑏}, 
𝑃′ = {𝑆 → 𝑎𝑆𝑏|𝐴|𝜆, 𝐴 → 𝑎𝐴𝑏𝑏|𝑎𝑏𝑏} é inambígua e 𝐿(𝐺′) = 𝐿(𝐺). 
d) AD’s para gramática 𝐺: 
1) 2) 
 
 
 
 
 
 
AD para gramática 𝐺′: 
 
 
 
 
S 
a b S 
 
a b S b 
𝜆 
S 
a b S 
 
a b S 
b 
𝜆 
S 
a b S 
 
a b 
A 
b 
 Linguagens Formais e Autómatos 
115 
9.4. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), onde 𝑁 = {𝑆, 𝐴, 𝐵}, 𝑇 = {𝑎, 𝑏}, 
𝑃 = {𝑆 → 𝑎𝑆|𝑎𝐴, 𝐴 → 𝑎𝐴| 𝑏𝐵, 𝐵 → 𝜆}. 
a) Que tipo tem gramática 𝐺? 
b) Mostrar que 𝐺 é ambígua (achar duas derivações esquerdas diferentes para palavra aab). 
c) Construir AD’s diferentes para palavra aab. 
d) Eliminar ambiguidade. 
e) Achar 𝐿(𝐺). 
Solução. a) 𝐺 é uma gramática regular (Tipo 3). 
b) 1) 𝑆 ⇒𝑒
 𝑎𝑆 ⇒𝑒
 𝑎𝑎𝐴 ⇒𝑒
 𝑎𝑎𝑏𝐵 ⇒𝑒
 𝑎𝑎𝑏 
 2) 𝑆 ⇒𝑒
 𝑎𝐴 ⇒𝑒
 𝑎𝑎𝐴 ⇒𝑒
 𝑎𝑎𝑏𝐵 ⇒𝑒
 𝑎𝑎𝑏 
𝐺 é ambígua. 
c) 
 1) 2) 
 
 
 
 
 
 
 
 
d) 𝐺 é uma gramática regular. Então, para achar uma gramática equivalente que não é ambígua é 
preciso contruir AFD 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐺) e depois achar gramática 𝐺1 tal que 
𝐿(𝐺1) = 𝐿(𝐴) = 𝐿(𝐺). 
Autómato que corresponde a gramática 𝐺 é 
S 
a 
A 
S 
 
𝜆 
B 
a 
b 
S 
a 
A 
A 
 
𝜆 
B 
a 
b 
 Linguagens Formais e Autómatos 
116 
 
 
 
Mas este autómato não é AFD (logo, 𝐺 é ambígua) 
Vamos achar AFD 𝐴: 𝐿(𝐴) = 𝐿(𝐴1) 
 
 
 
 
 
 
 
 
 
 
 
 
 
A gramática inambígua 𝐺1 tal que 𝐿(𝐺) = 𝐿(𝐺1) é 𝐺1 = (𝑁′, 𝑇, 𝑃′, 𝑆), onde 𝑁
′ = {𝑆, 𝐵, 𝐶, 𝐷},
𝑇 = {𝑎, 𝑏}, 𝑃′ = {𝑆 → 𝑎𝐶|𝑏𝐷, 𝐶 → 𝑎𝐶|𝑏𝐵, 𝐵 → 𝑎𝐷|𝑏𝐷|𝜆, 𝐷 → 𝑎𝐷|𝑏𝐷} 
e) Utilizando AFD 𝐴 é fácil ver que 𝐿(𝐴) = 𝑎𝑎∗𝑏 = 𝑎+𝑏 = 𝐿(𝐺). 
9.5. Achar duas gramáticas regulares uma ambígua outra não que geram a linguagem 𝐿 = 𝑎∗. 
Construir autómatos correspondentes. 
Solução. 𝐺1 = (𝑁1, 𝑇1, 𝑃1, 𝑆), onde 𝑁1 = {𝑆}, 𝑇1 = {𝑎, 𝑏}, 𝑃1 = {𝑆 → 𝑎𝑆|𝜆}. 𝐺1 não é 
ambígua. Autómato correspondente é AFD 𝐴1: 
 
𝛿′ 𝑎 𝑏 
→ {𝑆} {𝑆, 𝐴} ∅ 
{𝑆, 𝐴} {𝑆, 𝐴} {𝐵} 
∅ ∅ ∅ 
∗ {𝐵} ∅ ∅ 
a b 
a 
𝑆 𝐴 𝐵 𝐴1: 
a 
{𝑆} − 𝑆 
{𝑆, 𝐴} − 𝐶 
{𝐵} − 𝐵 
∅ − 𝐷 
a b 
a 
b 
𝐴: 
a,b 
𝑆 𝐶 𝐵 
𝐷 
a,b 
a 
𝑆 𝐴1: 
 Linguagens Formais e Autómatos 
117 
𝐺2 = (𝑁2, 𝑇2, 𝑃2, 𝑆), onde 𝑁2 = {𝑆, Φ}, 𝑇2 = {𝑎}, 𝑃2 = {𝑆 → 𝑎𝑆|𝑎|𝜆}. 𝐺2 é ambígua.1) 𝑆 ⇒𝑒
 𝑎𝑆 ⇒𝑒
 𝑎 ∈ 𝐿(𝐺2) 
2) 𝑆 ⇒𝑒
 𝑎 ∈ 𝐿(𝐺2) 
Autómato correspondente é AFND – 𝜆 𝐴2: 
 
 
 
A gramática que corresponde ao autómato 𝐴2 é 
𝐺3 = (𝑁3, 𝑇3, 𝑃3, 𝑆) 
𝑁3 = {𝑆, Φ}, 𝑇3 = {𝑎}, 𝑃3 = {𝑆 → 𝑎𝑆|𝑎Φ|𝜆, Φ → 𝜆}. 
Esta gramática ambígua é equivalente a 𝐺2 e gera 𝑎
∗. 𝐿(𝐺1) = 𝐿(𝐺2) = 𝐿(𝐺3). 
 
Problemas propostos 
 
9.6. Demonstrar que a linguagem 𝐿𝑏𝑎𝑙 não é linguagem regular. 
9.7. Demonstrar que a linguagem 𝐿𝑝𝑎𝑙 não é linguagem regular. 
9.8. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {𝑎}, 𝑃 = {𝑆 → 𝑎𝑆|𝑆𝑎|𝑎}. 
a) Mostrar que 𝐺 é ambígua. 
b) Achar 𝐿(𝐺). 
c) Achar uma gramática inambígua equivalente. 
9.9. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {𝑎}, 𝑃 = {𝑆 → 𝑏𝑆|𝑆𝑏|𝑎}. 
a) Mostrar que 𝐺 é ambígua (achar duas derivações esquerdas diferentes para palavra 
𝑏𝑎𝑏 ∈ 𝐿(𝐺)). 
b) Construir AD’s correspondentes. 
a 
a 
Φ 𝑆 𝐴2: 
 Linguagens Formais e Autómatos 
118 
c) Achar 𝐿(𝐺). 
d) Achar duas gramáticas inambíguas equivalentes a 𝐺. 
9.10. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆) onde 𝑁 = {𝑆}, 𝑇 = {𝑎}, 𝑃 = {𝑆 → 𝑎|𝑆𝑏𝑆}. 
a) Mostrar que 𝐺 é ambígua (achar duas derivações esquerdas diferentes para palavra 
𝑎𝑏𝑎𝑏𝑎 ∈ 𝐿(𝐺)). 
b) Construir AD’s correspondentes. 
c) Achar duas gramáticas inambíguas equivalentes a 𝐺. 
9.11. Seja 𝐺 = (𝑁, 𝑇, 𝑃, 𝑆), 𝑁 = {𝑆, 𝐴}, 𝑇 = {𝑎, 𝑏}, 𝑃 = {𝑆 → 𝐴𝑆|𝜆, 𝐴 → 𝑎|𝜆 }. Mostrar que 
𝐺 é ambígua. Eliminar ambiguidade. 
9.12. Especifique uma GIC 𝐺 sobre alfabeto 𝑇 = {𝑎, 𝑏, (, ),∗, ∅, 𝜆, +} que gere a linguagem de 
todas expressões regulares sobre alfabeto {𝑎, 𝑏}. Demonstra que esta linguagem não é regular. 
9.13. A.V. Aho, Ravi Sethi, J.D, Ullman. COMPILADORES: Princípios, Técnicas e 
Ferramentas, Editora Alfiada, 1995. 
Eliminando a Ambiguidade pp 78–79 (Autoaprendizagem) 
 
Respostas 
 
9.8. a) 
 1) 𝑆 ⇒𝑒
 𝑎𝑆 ⇒𝑒
 𝑎𝑎 
2) 𝑆 ⇒𝑒
 𝑆𝑎 ⇒𝑒
 𝑎𝑎 
b) 𝐿(𝐺) = 𝑎+. 
 
9.9. a) 
1) 𝑆 ⇒𝑒
 𝑏𝑆 ⇒𝑒
 𝑏𝑆𝑏 ⇒𝑒
 𝑏𝑎𝑏 
 2) 𝑆 ⇒𝑒
 𝑆𝑏 ⇒𝑒
 𝑏𝑆𝑏 ⇒𝑒
 𝑏𝑎𝑏 
 Linguagens Formais e Autómatos 
119 
b) 
1) 2) 
 
 
 
 
 
 c) 𝐿(𝐺) = 𝑏∗𝑎𝑏∗. 
 
d) 𝐺1: 𝑆 → 𝑏𝑆|𝑎𝐴, A → 𝑏𝐴|𝜆 
 𝐺2: 𝑆 → 𝑏𝑆|𝐴, A → 𝐴𝑏|𝑎 
 
9.10. a) 
1) 𝑆 ⇒𝑒
 𝑆𝑏𝑆 ⇒𝑒
 𝑆𝑏𝑆𝑏𝑆 ⇒𝑒
 𝑎𝑏𝑆𝑏𝑆 ⇒𝑒
 𝑎𝑏𝑎𝑏𝑆 ⇒𝑒
 𝑎𝑏𝑎𝑏𝑎 
2) 𝑆 ⇒𝑒
 𝑆𝑏𝑆 ⇒𝑒
 𝑎𝑏𝑆 ⇒𝑒
 𝑎𝑏𝑆𝑏𝑆 ⇒𝑒
 𝑎𝑏𝑎𝑆𝑏 ⇒𝑒
 𝑎𝑏𝑎𝑏𝑎 
b) 1) 2) 
 
 
 
 
 
 
c) 𝐺1: 𝑆 → 𝑎𝑏𝑆|𝑎 
𝐺2: 𝑆 → 𝑆𝑏𝑎|𝑎 
9.11. 𝐺: 𝑆 → 𝐴𝑆|𝜆, A → 𝑎 
9.12. 𝐺: 𝑆 → (𝑆 + 𝑆) | (𝑆𝑆) | (𝑆∗) | 𝑎 | 𝑏 | ∅ |𝜆. 
 
S 
b 
b 
S 
 
S 
a 
S 
S 
b 
b 
 
S 
a 
a 
S 
S S b 
S S b a 
a 
a 
S 
S S b 
S S b 
a a 
 Linguagens Formais e Autómatos 
120 
Capítulo 10 
 
Autómatos de Pilha 
 
 Consideremos o seguinte exemplo: 
Exemplo 10.1. Sejam 𝐿5 = {0
𝑛1𝑛| 1 ≤ 𝑛 ≤ 5} e 𝐿 = {0𝑛1𝑛| 1 ≤ 𝑛 ≤ 5}. A linguagem 𝐿5 é 
regular, pois é finita e a linguagem 𝐿 não é regular, 𝐿 é uma LIC (Problema 7.3 e Exemplo 8.1). 
 Vamos construir um AFND – 𝜆 𝐴 que reconhece 𝐿5 (𝐿(𝐴) = 𝐿5). 
 
 
 
 
 
 
 Os estados 𝑞1, 𝑞2, … , 𝑞5 são usados para conter o número de 0’s no inicio da palavra de 
entrada e 𝑞1′, 𝑞2′, … , 𝑞5′ são usados para contar o número de 1’s. É claro que esta técnica não 
funciona para 𝐿. É preciso um número infinito de estados. 
 Vamos construir um autómato 𝑃 com 3 estados 𝑄 = {𝑞0, 𝑞1, 𝑓} que tem uma “memória de 
pilha” sobre alfabeto Γ = {$, 𝐴} onde $ é o símbolo inicial da pilha e a letra vamos utilizar para 
contar 0’s. 
Definimos a função de transição 
𝛿: 𝑄 × (Σ ∪ {𝜆}) × (Γ ∪ {𝜆}) → 𝑄 × Γ∗ 
𝛿(𝑞0, 0, $) = (𝑞0, 𝐴$), 𝛿(𝑞0, 0, 𝐴) = (𝑞0, 𝐴𝐴), 
𝛿(𝑞0, 1, 𝐴) = (𝑞1, 𝜆), 𝛿(𝑞1, 1, 𝐴) = (𝑞1, 𝜆), 
𝛿(𝑞1, 𝜆, $) = (𝑓, $). 
1 
𝑞0 𝑞1 
𝑓 
0 
𝑞2 
1 
𝜆 
0 0 
1 
𝐴: 
𝑞4 𝑞5 𝑞3 
𝑞1′ 𝑞2′ 𝑞4′ 𝑞5′ 𝑞3′ 
0 
1 
0 
1 
𝜆 𝜆 𝜆 𝜆 
 Linguagens Formais e Autómatos 
121 
Ou na forma de tabela: 
 
 
 
 
 
Vamos construir o diagrama de transição para este autómato 𝑃 
 
 
 
 
 
 Um termo (𝑞, 𝑥, 𝛼) onde 𝑞 ∈ 𝑄 é um estado, 𝑥 ∈ Σ∗, 𝛼 ∈ Γ∗ chama-se configuração do 
autómato de pilha. Configuração inicial é (𝑞0, 𝑥, $), 𝑞0 − estado inicial, 𝑥 ∈ Σ
∗, $ − símbolo 
inicial da pilha. 
 Vamos realizar algumas computações no nosso autómato. 
1) (𝑞0, 0011, $) ⊢ (𝑞0, 011, 𝐴$) ⊢ (𝑞0, 11, 𝐴𝐴$) ⊢ (𝑞1, 1, 𝐴$) ⊢ (𝑞1, 𝜆, $) ⊢ (𝑓, 𝜆, $). 
2) (𝑞0, 011, 𝐴$) ⊢ (𝑞0, 11, 𝐴$) ⊢ (𝑞1, 1, $). 
3) (𝑞0, 010, 𝐴$) ⊢ (𝑞0, 10, 𝐴$) ⊢ (𝑞1, 0, $). 
4) (𝑞0, 0
𝑛1𝑛, $) ⊢ (𝑞0, 0
𝑛−11𝑛, 𝐴$) ⊢ (𝑞0, 0
𝑛−21𝑛 𝐴𝐴$) ⊢∗ (𝑞0, 01
𝑛, 𝐴𝑛−1$) ⊢
(𝑞0, 1
𝑛, 𝐴𝑛$) ⊢ (𝑞1, 1
𝑛−1, 𝐴𝑛−1$) ⊢∗ (𝑞1, 1, 𝐴$) ⊢ (𝑞1, 𝜆, $) ⊢ (𝑓, 𝜆, $). 
 Assim, um autómato de pilha tem os elementos seguintes: 
 
 
 
 
𝛿 0 1 𝜆 
𝑞0, $ 𝑞0, 𝐴$ − − 
𝑞0, 𝐴 𝑞0, 𝐴𝐴 𝑞1, 𝜆 − 
𝑞1, 𝐴 − 𝑞1, 𝜆 − 
𝑞1, $ − − 𝑓, $ 
 a . . . 
𝑞0 
0 $/A$ 
𝑃: 𝑞1 
1 A/𝜆 
0 A/𝜆 
0 A/AA 
𝑓 
𝜆 $/$ 
Estados 
Fita 
Cursor
 
Controlo Central 
Pilha
 
 Linguagens Formais e Autómatos 
122 
 Um autómato de pilha tem uma memória infinita (uma pilha). 
 Em cada transição o autómato de pilha pode alterar o estado e o topo da pilha. Uma 
transição é determinada pelo estado actual, pelo símbolo do topo da pilha e pelo símbolo da palavra 
de entrada que está na célula activa (pode ter também transições por 𝜆). 
 Como o resultado de transição o autómato altera o estado actual (pode ser por um conjunto 
finito de estados (não determinístico)), move o cursor por uma célula para a direita (excepto a 
transição por 𝜆) e substitui o elemento no topo da pilha por uma sequência de outros símbolos 
(possivelmente vazia). 
Vamos dar a definição formal 
Definição 10.1. Um Autómato de Pilha (AP) é um sistema de 7 (sete) elementos 
𝑃 = (𝑄, Σ, Γ, 𝛿, 𝐹, 𝑞0, $) onde: 
1) 𝑄 é um conjunto finito de estados; 
2) Σ é o alfabeto de entrada; 
3) Γ é o alfabeto da pilha (letras maiúsculas); 
4) 𝛿: 𝑄 × (Σ ∪ {𝜆}) × (Γ ∪ {𝜆}) → 𝑃𝑓𝑖𝑛(𝑄 × Γ
∗) é a função de transição; 
5) 𝐹 ⊆ 𝑄 é o conjunto de estados finais; 
6) 𝑞0 ∈ 𝑄 é dito estado inicial; 
7) $ é o símbolo inicial da pilha. 
Definição 10.2. Substituição do topo da pilha. Substituir o topo da pilha 𝑋 pela sequência 
𝑋1 … 𝑋𝑘 , 𝑘 ≥ 1, 𝑋, 𝑋𝑖 ∈ Γ, 𝑖 = 1, … , 𝑘 corresponde a retirar 𝑋 e colocar sucessivamente 
𝑋𝑘 … 𝑋1, passando o topo a ser 𝑋1. Substituir o elemento no topo da pilha 𝑌 por 𝜆 corresponde a 
rectificar o elemento no topo da pilha. 
 O topo da pilha no inicio. Quando o autómato começa a processar a palavra, o único 
símbolo que está na pilha é o símbolo inicial da pilha $. 
Definição 10.3. Aceitação por estados finais. Uma palavra 𝑤 ∈ Σ∗ é aceite pelo AP 𝑃 por estados 
finais se e somente se 𝑤 leva o autómato do estado inicial a algum dos estados finais, sendo 
totalmente processada. 
 Linguagens Formais e Autómatos 
123 
 A linguagem que aceita o autómato 𝑃 por estados finais é: 
𝐿𝐹(𝑃) = {𝑤|𝑤 ∈ Σ
∗: (𝑞0, 𝑤, $) ⊢
∗ (𝑞, 𝜆, 𝛼), 𝑞 ∈ 𝐹}. 
Definição 10.4. Aceitação por pilha vazia. Uma palavra 𝑤 ∈ Σ∗ é aceite pelo AP 𝑃 por pilha 
vazia se e somente se 𝑤 leva o autómato do estado inicial a pilha vazia, sendo totalmente 
processada. 
 A linguagem que aceita o autómato 𝑃 por estados finais é: 
𝐿𝑉(𝑃) = {𝑤|𝑤 ∈ Σ
∗: (𝑞0, 𝑤, $) ⊢
∗ (𝑞, 𝜆, 𝜆)}. 
Nestecaso o conjunto de estados finais 𝐹 = ∅. 
Exemplo 10.2. Seja 𝑃 = (𝑄, Σ, Γ, 𝛿, 𝐹, 𝑞0, $) onde 𝑄 = {𝑞0, 𝑞1}, Σ = {0,1}, Γ = {$, 𝐴}, 
𝐹 = ∅. 
𝛿(𝑞0, 𝜆, $) = (𝑞1, $), 𝛿(𝑞0, 0, $) = (𝑞0, 𝐴$), 
𝛿(𝑞0, 0, 𝐴) = (𝑞0, 𝐴𝐴), 𝛿(𝑞0, 1, 𝐴) = (𝑞1, 𝜆), 
𝛿(𝑞1, 1, 𝐴) = (𝑞1, 𝜆), 𝛿(𝑞1, 1, $) = (𝑞1, $), , 𝛿(𝑞1, 1, $) = (𝑞1, 𝜆). 
 
 
 
 
 
 
 
 
 
 
 
 
Vamos faze a computação de 𝑃 quando a palavra de input é 𝑤 = 00111: 
(𝑞0, 00111, $) ⊢ (𝑞0, 0111, 𝐴$) ⊢ (𝑞0, 111, 𝐴𝐴$) ⊢ (𝑞1, 11, 𝐴$) ⊢ (𝑞1, 1, $) ⊢ (𝑞1, 𝜆, 𝜆). 
𝛿 0 1 𝜆 
𝑞0, $ 𝑞0, 𝐴$ − 𝑞1, $ 
𝑞0, 𝐴 𝑞0, 𝐴𝐴 𝑞1, 𝜆 − 
𝑞1, 𝐴 − 𝑞1, 𝜆 − 
𝑞1, $ − 𝑞1, $ − 
𝑞1, $ − 𝑞1, 𝜆 − 
𝑞0 
0 $/A$ 
0 A/AA 
 
𝑞1 
𝜆 $/$ 
1 A/𝜆 
 
1 A/𝜆 
1 $/$ 
1 S/𝜆 
 Linguagens Formais e Autómatos 
124 
Logo, 00111 ∈ 𝐿𝑉(𝑃). 
Analisando o diagrama de transição de 𝑃 é fácil ver que 𝐿𝑉(𝑃) = {0
𝑛1𝑚|𝑚 > 𝑛}. 
Teorema 10.1. Seja 𝐿 uma linguagem. Se existe um AP 𝑃 tal que 𝐿 = 𝐿𝐹(𝑃) então existe um AP 
𝑃′ tal que 𝐿 = 𝐿𝑉(𝑃′ ) e vice-versa se existe um AP 𝑃 tal que 𝐿𝑉(𝑃) = 𝐿 então existe um AP 𝑃′ 
tal que 𝐿 = 𝐿𝐹(𝑃′ ). 
Demonstração. Seja 𝐴 = (𝑄, Σ, Γ, 𝛿, 𝐹, 𝑞0, $) um AP e 𝐿 = 𝐿𝐹(𝐴). Então existe um AP 𝐴′ tal 
que 𝐿 = 𝐿𝑉(𝐴′ ). Realmente 𝐴′ = (𝑄 ∪ {𝑞0
′ , 𝑆}, Σ, Γ ∪ {$′}, 𝛿′, ∅, 𝑞0
′ , $′) onde $′ é um novo 
símbolo de pilha ($′ ∉ Γ) e 𝑞0
′ , 𝑆 são os novos estados (𝑆 vai ser usado para esvaziar a pilha). 
Onde a função de transição 𝛿′ é: 
1) 𝛿′(𝑞, 𝑎, 𝑍) = 𝛿(𝑞, 𝑎, 𝑍) para todos 𝑞 ∈ 𝑄, 𝑎 ∈ Σ ∪ {𝜆}, 𝑍 ∈ Γ; 
2) 𝛿′(𝑞0
′ , 𝜆, $) = {(𝑞0, $$)}; 
3) 𝛿′(𝑓, 𝜆, 𝑍) ∋ {(𝑆, 𝜆)} para todos 𝑓 ∈ 𝐹, 𝑍 ∈ Γ ∪ {$′}; 
4) 𝛿′(𝑆, 𝜆, 𝑍) = {(𝑆, 𝜆)} para todo 𝑍 ∈ Γ ∪ {$′}. 
 Agora, seja 𝐴 = (𝑄, Σ, Γ, 𝛿, ∅, 𝑞0, $) um AP e 𝐿 = 𝐿𝑉(𝐴). Então existe um AP 𝐴′ tal que 
𝐿 = 𝐿𝐹(𝐴′ ). Sejam $′ é um novo símbolo de pilha ($′ ∉ Γ) e 𝑞0
′ , 𝑓 dois novos estados. 
 O autómato 𝐴′ trabalha da mesma maneira que 𝐴, mas quando 𝐴 fica com pilha vazia, 𝐴′ 
tem $′ na pilha passando o estado final 𝑓. Então 𝐴′ = (𝑄 ∪ {𝑞0
′ , 𝑓}, Σ, Γ ∪ {$′}, 𝛿′, {𝑓}, 𝑞0
′ , $′) 
Onde a função de transição 𝛿′ é: 
1) 𝛿′(𝑞, 𝑎, 𝑍) = 𝛿(𝑞, 𝑎, 𝑍) para todos 𝑞 ∈ 𝑄, 𝑎 ∈ Σ ∪ {𝜆}, 𝑍 ∈ Γ; 
2) 𝛿′(𝑞0
′ , 𝜆, $′) = {(𝑞0, $$′)}; 
3) 𝛿′(𝑞, 𝜆, $′) ∋ {(𝑓, $′)} para todo 𝑞 ∈ 𝑄. 
Teorema 10.2. A classe de linguagens reconhecidas por autómatos de pilha é precisamente a 
classe de linguagens independentes de contexto. 
Problemas resolvidos 
10.1. Seja 𝐴 é AP do Exemplo 10.2. 
 Linguagens Formais e Autómatos 
125 
 
 
 
 
 𝐿𝑉(𝑃) = {0
𝑛1𝑚|𝑚 > 𝑛}. 
a) Achar AP 𝐴′ tal que 𝐿𝐹(𝐴′) = 𝐿𝑉(𝐴) = {0
𝑛1𝑚|𝑚 > 𝑛}. 
b) Fazer a computação para palavra de entrada 𝑤 = 00111 no AP 𝐴′. 
Solução. a) Aplicando o teorema 10.1 podemos achar AP 𝐴′: 
 
 
 
 
 
 
 
Então, 𝐿𝐹(𝐴′) = {0
𝑛1𝑚|𝑚 > 𝑛}. 
b) 𝑤 = 00111 
(𝑞0′, 00111, $′) ⊢ (𝑞0, 00111, $$′) ⊢ (𝑞0, 0111, 𝐴$$′) ⊢ (𝑞0, 111, 𝐴𝐴$$′) ⊢
(𝑞1, 11, 𝐴$$′) ⊢ (𝑞1, 1, $$′) ⊢ (𝑞1, 𝜆, $′) ⊢ (𝑓, 𝜆, $′). 
Logo, 00111 ∈ 𝐿𝐹(𝐴′). 
 
10.2. Seja 𝐴 é AP do Exemplo 10.1. 
 
 
 
𝑞0 
0 $/A$ 
0 A/AA 
 
𝑞1 
𝜆 $/$ 
1 A/𝜆 
 
1 A/𝜆 
1 $/$ 
1 $/𝜆 
𝐴: 
𝑞0 
0 $/A$ 
0 A/AA 
 
𝑞1 
𝜆 $/$ 
1 A/𝜆 
 
1 A/𝜆 
1 $/$ 
1 $/𝜆 𝐴′: 
𝜆 $´/$$´ 
𝜆 $´/$´ 
𝜆 $´/$´ 
𝑞0′ 𝑓 
𝑞0 
0 $/A$ 
0 A/AA 
𝐴: 𝑞1 
1 A/𝜆 
0 A/𝜆 
𝑓 
𝜆 $/$ 
 Linguagens Formais e Autómatos 
126 
 𝐿𝐹(𝐴) = {0
𝑛1𝑛|𝑛 ≥ 1}. 
a) Achar AP 𝐴′ tal que 𝐿𝑉(𝐴′) = 𝐿𝐹(𝐴) = {0
𝑛1𝑛|𝑛 ≥ 1}. 
b) Fazer a computação para palavra de entrada 𝑤 = 0011 no AP 𝐴′. 
Solução. a) Aplicando o teorema 10.1 podemos achar AP 𝐴′: 
 
 
 
 
 
 
 
 
 
 
 
Então, 𝐿𝑉(𝐴′) = {0
𝑛1𝑛|𝑛 ≥ 1}. 
b) 𝑤 = 0011 
(𝑞0′, 0011, $′) ⊢ (𝑞0, 0011, $$′) ⊢ (𝑞0, 011, 𝐴$$′) ⊢ (𝑞0, 11, 𝐴𝐴$$′) ⊢ (𝑞1, 1, 𝐴$$′) ⊢
(𝑞1, 𝜆, $$′) ⊢ (𝑆, 𝜆, $′) ⊢ (𝑆, 𝜆, 𝜆). 
Logo, 0011 ∈ 𝐿𝑉(𝐴′). 
 
Problemas propostos 
10.3. Seja 𝐿 = {𝑤|𝑤 ∈ {0,1}∗ , |𝑤|0 = |𝑤|1}. 
a) Achar AP 𝐴1: 𝐿𝐹(𝐴1) = 𝐿. 
b) Fazer a computação para palavra de entrada 𝑤 = 1001 no autómato 𝐴1. 
c) Achar AP 𝐴2: 𝐿𝑉(𝐴2) = 𝐿 (utilizar o teorema 10.1). 
d) Fazer a computação para palavra de entrada 𝑤 = 1001 no autómato 𝐴2. 
𝑞0 
0 $/A$ 
0 A/AA 
𝐴′: 𝑞1 
1 A/𝜆 
0 A/𝜆 
𝑓 
𝜆 $/$ 
𝜆 $´/$$´ 
𝑞0′ 𝑆 
𝜆 $/𝜆 
𝜆 A/𝜆 
𝜆 $´/𝜆 
𝜆 A/𝜆 
𝜆 $/𝜆 
𝜆 $´/𝜆 
 Linguagens Formais e Autómatos 
127 
10.4. Seja 𝐿 − linguagem de enunciados condicionais (if...else) (veja capítulo 9). 
a) Achar AP 𝐴1: 𝐿𝑉(𝐴1) = 𝐿𝑒𝑐. 
b) Fazer a computação para as palavras de entrada 𝑤1 = 𝑖𝑖𝑒, 𝑤2 = 𝑖𝑒𝑒𝑖 no autómato 𝐴1. 
c) Achar AP 𝐴2: 𝐿𝐹(𝐴2) = 𝐿𝑒𝑐 (utilizar o teorema 10.1). 
d) Fazer a computação para as palavras de entrada 𝑤1 = 𝑖𝑖𝑒, 𝑤2 = 𝑖𝑒𝑒𝑖 no autómato 𝐴2. 
 
10.5. Seja 𝐿 = {𝑤𝑐𝑤𝑅|𝑤 ∈ {𝑎, 𝑏}∗}. 
a) Achar AP 𝐴1: 𝐿𝐹(𝐴1) = 𝐿. 
b) Fazer a computação para palavra de entrada 𝑤 = 𝑎𝑏𝑐𝑏𝑎 no autómato 𝐴1. 
c) Achar AP 𝐴2: 𝐿𝑉(𝐴2) = 𝐿 (utilizar o teorema 10.1). 
d) Fazer a computação para palavra de entrada 𝑤 = 𝑎𝑏𝑐𝑏𝑎 no autómato 𝐴2. 
 
Respostas 
10.3. 
 
a) 
 
 
 
 
 
 
b) 𝑤 = 1001 
(𝑞0, 1001, $) ⊢ (𝑞1, 001, 𝐵$) ⊢ (𝑞1, 01, $) ⊢ (𝑞1, 1, 𝐴$) ⊢ (𝑞1, 𝜆, $) ⊢ (𝑓, 𝜆, $). 
 
 
𝑞0 
0 $/A$ 
1 $/B$ 
𝐴1: 𝑞1 
0 A/AA 
0 B/𝜆 
1 B/BB 
1 A/𝜆 
 
𝑓 
𝜆 $/$ 
 Linguagens Formais e Autómatos 
128 
c) 
 
 
 
 
 
 
 
 
 
 
d) 𝑤 = 1001 
(𝑞0′, 1001, $′) ⊢ (𝑞0, 1001, $$′) ⊢ (𝑞1, 001, 𝐵$) ⊢ (𝑞1, 01, $) ⊢ (𝑞1, 1, 𝐴$) ⊢ (𝑞1, 𝜆, $) ⊢
(𝑓, 𝜆, $) ⊢ (𝑆, 𝜆, $′) ⊢ (𝑆, 𝜆, 𝜆). 
 
10.4. 
a) 
 
 
 
10.5. 
a) 
 
 
 
 
𝑞0 
0 $/A$ 
1 $/B$ 
𝐴1: 𝑞1 
0 A/AA 
0 B/𝜆 
1 B/BB 
1 A/𝜆 
 
𝑓 
𝜆 $/$ 
𝜆 $´/$$´ 
𝑞0′ 𝑆 
𝜆 $/𝜆 
𝜆 $´/𝜆 
𝜆 $/𝜆 
𝜆 $´/𝜆 
𝑞0 
i $/A$ 
i A/AA 
e A/𝜆 
 
𝑞1 
𝜆 A/𝜆 
𝜆 $/$ 
𝜆 A/𝜆 
𝜆 $/𝜆 
𝐴1: 
𝑞0 
a $/A$ 
a A/AA 
b $/B$ 
b B/BB 
𝐴1: 𝑞1 
a A/𝜆 
b B/𝜆 
c A/A 
c B/B 
c $/$ 
𝑓 
𝜆 $/$