Autômatos e Linguagens Formais S. C. Coutinho

Autômatos e Linguagens Formais

S. C. CoutinhoUniversidade Federal do Rio de Janeiro

i

ii

c© by S. C. Coutinho 2007

Agradeço a• David Boechat• Gabriel Rosário

pelas correções às notas de aula.

Sumário

Capítulo 1. Conjuntos e linguagens 11. Exercícios 1

Capítulo 2. Autômatos finitos determinísticos 31. Exercícios 3

Capítulo 3. Expressões regulares 51. Introdução 52. Lema de Arden 83. O algoritmo de substituição 104. Expressões regulares 125. Análise formal do algoritmo de substituição 156. Exercícios 17

Capítulo 4. Linguagens que não são regulares 211. Propriedade do bombeamento 212. Lema do bombeamento 233. Aplicações do lema do bombeamento 254. Exercícios 31

Capítulo 5. Autômatos finitos não determinísticos 35

Capítulo 6. Operações com autômatos finitos 391. União 392. Concatenação 453. Estrela 474. Exercícios 51

Capítulo 7. Autômatos de expressões regulares 531. Considerações gerais 532. União 54

Capítulo 8. Gramáticas lineares à direita 591. Exercícios 59

Capítulo 9. Linguagens livres de contexto 611. Gramáticas e linguagens livres de contexto 612. Linguagens sensíveis ao contexto 65

v

vi SUMÁRIO

3. Mais exemplos 664. Combinando gramáticas 695. Exercícios 72

Capítulo 10. Árvores Gramaticais 751. Análise Sintática e línguas naturais 752. Árvores Gramaticais 773. Colhendo e derivando 804. Equivalência entre árvores e derivações 835. Ambigüidade 846. Removendo ambigüidade 887. Exercícios 90

Capítulo 11. Linguagens que não são livres de contexto 931. Introdução 932. Lema do bombeamento 943. Exemplos 984. Exercícios 102

Capítulo 12. Autômatos de Pilha 1031. Heurística 1032. Definição e exemplos 1053. Computando e aceitando 1114. Variações em um tema 1135. Exercícios 118

Capítulo 13. Gramáticas e autômatos de pilha 1231. O autômato de pilha de uma gramática 1232. A receita e mais um exemplo 1263. Provando a receita 1284. Autômatos de pilha cordatos 1305. A gramática de um autômato de pilha 1326. Exercícios 137

Capítulo 14. Máquinas de Turing 1391. Exercícios 139

Capítulo 15. Máquinas de Turing e Linguagens 1431. Conectando Máquinas em Paralelo 1432. Fechamento de linguagens 1453. A máquina de Turing universal 1474. Comportamento de U 1505. Linguagens não recursivas 1516. O problema da parada 152

Referências Bibliográficas 155

CAPíTULO 1

Conjuntos e linguagens

Neste primeiro capítulo, revisamos algumas propriedades básicas dos con-juntos e suas operações e introduzimos o conceito de linguagem formal.

1. Exercícios

1. Sejam A e B conjuntos, prove que:(a) ∅ ∪A = A;(b) ∅ ∩A = ∅;(c) se A ⊂ B então A ∩B = A;(d) se A ⊂ B então A ∪B = B;(e) A ∩A = A = A ∪A;(f) A ∪B = B ∪A e A ∩B = B ∩A;(g) A ∪ (B ∪ C) = (A ∪B) ∪ C;(h) A ∩ (B ∩ C) = (A ∩B) ∩ C;(i) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C);(j) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C);(k) A \ B = A ∩ B onde B é o complemento de B no conjunto universo,

isto é o conjunto que contém todos os conjuntos com que estamos tra-balhando;

(l) (A ∩B) = A ∪B;(m) (A ∪B) = A ∩B;(n) A = A;(o) A \B = A \ (B ∩A);(p) B ⊂ A se, e somente se, A ∩B = ∅;(q) (A \B) \ C = (A \ C) \ (B \ C) = A \ (B ∪ C);(r) A ∩B = ∅ e A ∩B = ∅ se e somente se A = B.

2. Considere as afirmações abaixo: prove as verdaeiras e dê um contra-exemplopara as falsas.(a) se A ∪B = A ∪ C então B = C;

1

2 1. CONJUNTOS E LINGUAGENS

(b) se A ∩B = A ∩ C então B = C.

3. Sejam A, B e C conjuntos, prove que:(a) A× (B ∩ C) = (A×B) ∩ (A× C);(b) A× (B ∪ C) = (A×B) ∪ (A× C);(c) A× (B \ C) = (A×B) \ (A× C);

4. Explique a diferença entre ∅ e {ε}. Calcule L · ∅, onde L é uma linguagemqualquer.

5. Seja w uma palavra em um alfabeto Σ. Definimos o reflexo de w recursi-vamente da seguinte maneira: εR = ε e se w = ax então wR = xRa ondea ∈ Σ.(a) Determine (turing)R e (anilina)R.(b) Se x e y são palavras no alfabeto Σ, determine (xy)R em função de xR

e yR.(c) Determine (xR)R.

6. Sejam L1 e L2 linguagens no alfabeto Σ. Determine as seguintes linguagensem função de LR

1 e LR2 :

(a) (L1 · L2)R;(b) (L1 ∪ L2)R;(c) (L1 ∩ L2)R;(d) L1

R;

(e) (L∗1)R.

7. Mostre, por indução em n, que se L0, . . . , Ln são linguagens no alfabeto Σentão

L0 · (L1 ∪ · · · ∪ Ln) = (L0 · L1) ∪ · · · ∪ (L0 · Ln).

8. Sejam Σ1 e Σ2 dois alfabetos e seja φ : Σ1 → Σ∗2 uma aplicação. Estendaφ a Σ∗1 de acordo com a seguinte definição recursiva:• φ(ε) = ε;• φ(xσ) = φ(a)φ(σ), onde a ∈ Σ∗1.

Se L é uma linguagem no alfabeto Σ1 defina

φ(L) = {φ(w) : w ∈ Σ∗1}.Mostre que se L e L′ são linguagens no alfabeto Σ1 então:(a) φ(L ∪ L′) = φ(L) ∪ φ(L′);(b) φ(L ∩ L′) = φ(L) ∩ φ(L′);(c) φ(L · L′) = φ(L) · φ(L′);

CAPíTULO 2

Autômatos finitos determinísticos

Neste capítulo introduzimos a noção de autômato finito determinísticoatravés de um exemplo concreto e estudamos alguns outros exemplos que ocor-rerão freqüentemente ao longo do livro.

1. Exercícios

1. Seja A um autômato finito determinístico. Quando é que ε ∈ L(A)?

2. Desenhe o grafo de estados e determine a linguagem aceita por cada um dosseguintes autômatos finitos. Em cada caso o estado inicial é q1 e o alfabetoé {a, b, c}(a) F1 = {q5} e a função de transição é dada por:

δ1 a b c

q1 q2 q3 q4

q2 q2 q4 q5

q3 q4 q3 q5

q4 q4 q4 q5

q5 q4 q4 q5(b) F2 = {q4} e δ2 = δ1.(c) F3 = {q2} e a função de transição é dada por:

δ3 a b c

q1 q2 q2 q1

q2 q3 q2 q1

q3 q1 q3 q2

3. Considere o autômato finito determinístico no alfabeto {a, b}, com estados{q0, q1}, estado inicial q0, estados finais F = {q1} e cuja função de transi-ção é dada por:

3

4 2. AUTÔMATOS FINITOS DETERMINÍSTICOS

δ a b

q0 q0 q1

q1 q1 q0

(a) Esboce o diagrama de estados deste autômato.(b) Descreva a computação deste autômato que tem início na configuração

(q0, aabba). Esta palavra é aceita pelo autômato?(c) Descreva a computação deste autômato que tem início na configuração

(q0, aabbab). Esta palavra é aceita pelo autômato?(d) Descreva em português a linguagem aceita pelo autômato definido acima?

4. Seja Σ um alfabeto com n símbolos. Quantos autômatos finitos determinís-ticos existem com alfabeto Σ e m > 0 estados?Sugestão: Não esqueça de considerar todas as possibilidades para o con-junto de estados finais.

5. Invente autômatos finitos determinísticos que aceitem as seguintes lingua-gens sobre o alfabeto {0, 1}:(a) o conjunto das palavras que acabam em 00;(b) o conjunto das palavras com três 0s consecutivos;(c) o conjunto das palavras em que cada 0 está entre dois 1s;(d) o conjunto das palavras cujos quatro símbolos finais são 1101;(e) o conjunto dos palíndromos de comprimento igual a 6.

6. Dê exemplo de uma linguagem que é aceita por um autômato finito deter-minístico com mais de um estado final, mas que não é aceita por nenhumautômato finito determinístico com apenas um estado final. Justifique cui-dadosamente sua resposta.

CAPíTULO 3

Expressões regulares

É hora de abordarmos o primeiro dos problemas propostos ao final do ca-pítulo anterior; isto é, como determinar a linguagem aceita por um autômatofinito? De quebra, descobriremos uma maneira de caracterizar estas lingua-gens.

1. Introdução

Desejamos obter um algoritmo que, dado um autômato finito M, deter-mine a linguagem L(M) que ele aceita. O algoritmo é recursivo, e para poderdescrevê-lo começamos por generalizar a noção de linguagem aceita por umautômato.

Seja M um autômato finito definido pelos ingredientes (Σ, Q, q1, F, δ).Para cada q ∈ Q definimos Lq como sendo a linguagem

Lq = {w ∈ Σ∗ : (q, w) `∗ (f, ε) onde f ∈ F}.

Em outras palavras, Lq é formada pelas palavras que levam o autômato do es-tado q a algum estado final. Quando os estados do autômato forem numeradoscomo q1, . . . , qn, escrevermos Li em vez de Lqi para simplificar a notação.Portanto, se q1 é o estado inicial deM, então

Lq1 = L1 = L(M).

Sejam p e q estados de M, e digamos que δ(p, σ) = q. Esta transi-ção estabelece uma relação entre as lingaugens Lp e Lq . De fato, temos que(p, σ) ` (q, ε) ao passo que, se w ∈ Lq , então (q, w) `∗ (f, ε). Combinadoestas duas computações obtemos

(p, σw) ` (q, w) `∗ (f, ε).

Portanto, {σ}Lq ⊆ Lp. Mais uma vez, com a finalidade de não sobrecarregara notação, eliminaremos as chaves, escrevendo simplesmente σLq ⊆ Lp.

5

6 3. EXPRESSÕES REGULARES

A não ser que o alfabeto Σ tenha apenas um símbolo, não há a menorchance de que σLq ⊆ Lp seja uma igualdade. Isto porque teremos uma in-clusão como esta para cada σ ∈ Σ. Portanto, se Σ = {σ1, . . . , σn} e seδ(p, σi) = qi, então

n⋃i=1

σiLqi ⊆ Lp.

Desta vez, porém, a inclusão é, de fato, uma igualdade, desde que p nãoseja um estado final do autômato! Para ver isto suponhamos que u ∈ Lp.Podemos isolar o primeiro símbolo de u, escrevendo u = σiw, para algumσi ∈ Σ. Mas, pela definição de Lp,

(p, u) = (p, σiw) `∗ (f, ε),

para algum f ∈ F . Por outro lado, como δ(p, σi) = qi, temos que (p, σi) `(qi, ε). Combinando estas duas computações, temos que

(p, u) = (p, σiw) ` (qi, w) `∗ (f, ε),

de onde segue que w ∈ Lqi .Precisamos ainda analisar o que acontece quando p é um estado final do

autômato. Considerando em detalhe o argumento do parágrafo acima, vemosque assumimos implicitamente que u 6= ε, já que estamos explicitando o seuprimeiro símbolo. Entretanto, se p for um estado final, teremos, além disso,que ε ∈ Lp.

Resumindo, provamos que, se Σ = {σ1, . . . , σn}, e se δ(p, σi) = qi, então

Lp =

{⋃ni=1 σiLqi se p /∈ F⋃ni=1 σiLqi ∪ {ε} se p ∈ F

O algoritmo que desejamos segue diretamente desta equação, como mostrao seguinte exemplo.

Considere o autômato finito determinísticoM com alfabeto é {0, 1} e cujografo é

I // ?>=<89:;q10 //

1��

?>=<89:;q21 //

0

~~||||||?>=<89:;76540123q3

0,1vvnnnnnnnnnnn

?>=<89:;q4

0,1

TT

Deste grafo extraímos as seguintes equções

L1 = 0L2 ∪ 1L4

L2 = 1L3 ∪ 0L4

L3 = 0L4 ∪ 1L4 ∪ {ε} (já que q3 é estado final)L4 = 0L4 ∪ 1L4.

1. INTRODUÇÃO 7

Observe que q4 é um estado morto, de modo que nada escapa de q4. Emparticular, nenhuma palavra leva o autômato de q4 a um estado final. Portanto,L4 = ∅. Isto simplifica drasticamente as equações anteriores, que passam a ser

L1 = 0L2

L2 = 1L3

L3 = {ε}L4 = ∅.

Podemos agora resolver este sistema de equações por mera substituição. As-sim, substituindo a terceira equação na segunda, obtemos

L2 = 1L3 = 1{ε} = {1}.

Finalmente, substituindo esta última equação na primeira, obtemos

L1 = 0L2 = 1{0} = {10}.

Como L1 = L(M), obtivemos uma descrição da linguagem aceita porM.Como seria de esperar, as coisas nem sempre são tão diretas. Afinal, o

autômato deste exemplo tinha um comportamento muito simples. Vejamoso que acontece em um exemplo menos elementar. Por exemplo, seja N oautômato finito determinístico de alfabeto {0, 1} e grafo

I // ?>=<89:;q1

0,1++ ?>=<89:;76540123q2

0,1kk

As equações correspondentes a L1 e L2 são:

L1 = 0L2 ∪ 1L2

L2 = 0L1 ∪ 1L1 ∪ {ε} (já que q2 é estado final)

Continuando a denotar {0} e {1} por 0 e 1, podemos reescreer estas equaçõescomo

L1 = (0 ∪ 1)L2

L2 = (0 ∪ 1)L1 ∪ {ε}.

À primeira vista, tudo o que temos que fazer para resolver este sistema é subs-tituir a segunda equação na primeira. Contudo, ao fazer isto obtemos

L1 = (0 ∪ 1)((0 ∪ 1)L1 ∪ {ε}),

ou seja,

(1.1) L1 = (0 ∪ 1)2L1 ∪ (0 ∪ 1),

de modo que L1 fica escrito em termos do próprio L1. Parece claro que ne-nhuma substituição pode nos tirar desta encrenca. O que fazer então?


2. Lema de Arden

Na verdade, ao aplicar o método de substituição para resolver sistemas deequações e achar a linguagem aceita por um autômato vamos nos deparar mui-tas vezes com equações em que uma linguagem é escrita em termos dela pró-pria. Equações que serão, freqüentemente, ainda mais complicadas que (1.1).Convém, portanto, abordar deste já o problema em um grau de generalidadesuficiente para dar cabo de todas as equações que apareçam como resultado doalgoritmo de substituição.

Para isso, suponhamos que Σ é um alfabeto e que A e B são linguagensem Σ. Digamos, que X seja uma outra linguagem em Σ que satisfaça

X = AX ∪B.

O problema que queremos resolver consiste em usar esta equação para deter-minar X .

Uma coisa que podemos fazer é substituir X = AX ∪ B de volta nelaprópria. Isso dá

(2.1) X = A(AX ∪B) ∪B = A2X ∪ (A ∪ ε)B,

e não parece adiantar de nada porque afinal de contas continuamos com um Xdo lado direito da equação. Mas não vamos nos deixar abater por tão pouco:façamos a substituição mais uma vez. Desta vez substituíremos X = AX ∪Bem (2.1), o que nos dá

X = A2(AX ∪B) ∪ (AB ∪B) = A3X ∪ (A2 ∪A ∪ ε)B.

Repetindo o mesmo procedimento k vezes, chegamos à equação

X = Ak+1X ∪ (Ak ∪Ak−1 ∪ · · · ∪A2 ∪A ∪ ε)B.

O problema é que o X continua presente. Mas, e se repetíssemos o processoinfinitas vezes? Neste caso, “perderíamos de vista o termo que contém X queseria empurrado para o infinito”, e sobraria apenas

(2.2) X = (ε ∪A ∪A2 ∪ · · · )B.

Para poder fazer isto de maneira formal precisamos introduzir uma novaoperação com linguagens, a estrela de Kleene. Em geral, seA é uma linguagemno alfabeto Σ, então A∗ é definida como a reunião de todas as potências de A;isto é,

A∗ = {ε} ∪A ∪A2 ∪A3 ∪ · · · .Por exemplo, se Σ = {0, 1} e A = {01}, então

A∗ = {(01)j : j ≥ 0} = {ε, 01, 0101, 010101, . . . }.

Por outro lado, se A = Σ, então A∗ é o conjunto de todas as palavras noalfabeto Σ–que aliás já vínhamos denotando por Σ∗.

A equação (2.2) sugere que, continuando o processo de substituição in-definidamente, deveríamos obter X = A∗B. Este é um conjunto perfeita-mente bem definido, resta-nos verificar se realmente é uma solução da equação

2. LEMA DE ARDEN 9

X = AX∪B. Para isso substituíremosX porA∗B do lado direito da equação:

AX ∪B = A(A∗B) ∪B = AA∗B ∪B.

Como A∗ = {ε} ∪A ∪A2 ∪A3 ∪ · · · , obtemos

AA∗B ∪B = A({ε} ∪A ∪A2 ∪A3 ∪ · · · )B ∪B,

que dáAA∗B ∪B = (A ∪A2 ∪A3 ∪A4 ∪ · · · )B ∪B.

Pondo B em evidência em todo o lado direito, obtemos

AA∗B ∪B = (ε ∪A ∪A2 ∪A3 ∪A4 ∪ · · · )B = A∗B.

Concluímos que A(A∗B) ∪ B = A∗B, de modo que A∗B é, de fato, umasolução da equação X = AX ∪B.

Infelizmente, isto ainda não é suficiente para completar os cálculos doalgoritmo de substituição. O problema é que obtivemos uma solução da equa-ção desejada, mas ainda não sabemos se esta solução corresponde ao maiorconjunto X ⊆ Σ∗ que satisfaz X = AX ∪ B. Se não for este o caso, quandousarmosA∗B como solução estaremos perdendo algumas palavras do conjuntoaceito pelo autômato, o que não queremos que aconteça.

Suponhamos, então, queX é o maior subconjunto de Σ∗ que satisfazX =AX ∪B. Como já sabemos que A∗B satisfaz esta equação, podemos escreverX = A∗B ∪ C, onde C é um conjunto (disjunto de A∗B) que contém aspossíveis palavras excedentes. Substituindo X = A∗B ∪C em X = AX ∪B,temos

(2.3) A∗B ∪ C = A(A∗B ∪ C) ∪B = A∗B ∪AC,

já que, como vimos, A(A∗B) ∪ B = A∗B. Intersectando ambos os membrosde (2.3) com C, e lembrando que, por hipótese, C ∩A∗B = ∅, chegamos a

C = AC ∩ C = (A ∩ ε)C.

Temos, então, duas possibilidades. A primeira é que A não contenha ε. Nestecaso A ∩ ε = ∅, de modo que C = ∅; ou seja, A∗B é o maior conjunto solu-ção da equação X = AX ∪ B. A outra possibilidade é que A contenha ε, eneste caso estamos encrencados. Por sorte, esta segunda possibilidade nuncaocorre na solução das equações que advêm do algoritmo de substituição! Vocêpode confirmar isto lendo a demonstração detalhada do algoritmo de substi-tuição na seção 5. Vamos resumir tudo o que fizemos em um lema, provadooriginalmente por D. N. Arden em 1960.

LEMA DE ARDEN. Sejam A e B linguagens em um alfabeto Σ. Se ε /∈ Aentão o maior subconjunto de Σ∗ que satisfaz X = AX ∪B é X = A∗B.

Vamos aplicar o que aprendemos para resolver a equação (1.1), que re-sultou da aplicação do método de substituição ao segundo exemplo da seçãoanterior. A equação é

L1 = (0 ∪ 1)2L1 ∪ (0 ∪ 1).


Aplicando o Lema de Arden com X = L1, A = (0 ∪ 1)2 e B = (0 ∪ 1),teremos que

L1 = X = A∗B = ((0 ∪ 1)2)∗(0 ∪ 1).

Concluímos, assim, que a linguagem aceita pelo autômato N é

L(N ) = ((0 ∪ 1)2)∗(0 ∪ 1).

3. O algoritmo de substituição

Antes de fazer outro exemplo, vamos descrever em mais detalhes o al-goritmo de substituição que usamos para determinar a linguagem aceita pelosautômatos da seção 1. Este algoritmo foi inventado por J. A. Brzozowski em1964.

Algoritmo de substituição

Entrada: ingredientes (Σ, Q, q1, F, δ) de um autômato finito determinísticoM.Saída: uma descrição da linguagem aceita porM.

Primeira etapa: Seja Q = {q1, . . . , qn}. Escreva as equações para as lingua-gens Lj , para cada 1 ≤ j ≤ n.Segunda etapa: Começando por Ln e acabando em L1, substitua Lj+1 naequação para Lj , aplicando o Lema de Arden sempre que uma linguagem forexpressa em termos dela própria.Terceira etapa: A linguagem aceita por M corresponde à expressão obtidapara L1.

Uma descrição detalhada deste algoritmo, e uma demonstração de que fazo que é pedido, pode ser encontrada na seção 5. Por enquanto, nos contentare-mos com a descrição acima, que vamos aplicar ao autômato no alfabeto {0, 1}cujo grafo é

?>=<89:;q5

0,1��

I // ?>=<89:;q1

1OO

0 // ?>=<89:;q2

0`BBBBBB

1

~~||||||

?>=<89:;q3

0OO

1 // ?>=<89:;76540123q4

0,1��

As equações correspondents a autômato são

L1 = 0L2 ∪ 1L5

L2 = 1L3 ∪ 0L5

L3 = 0L1 ∪ 1L4

L4 = 0L4 ∪ 1L4 ∪ εL5 = 0L5 ∪ 1L5.

3. O ALGORITMO DE SUBSTITUIÇÃO 11

Uma olhada no grafo mostra que q5 é um estado morto, de modo que L5 = ∅.Com isto as equações se simpificam:

L1 = 0L2

L2 = 1L3

L3 = 0L1 ∪ 1L4

L4 = 0L4 ∪ 1L4 ∪ εL5 = ∅.

A equação para L4 nos dá

L4 = (0 ∪ 1)L4 ∪ ε,

de modo que precisamos aplicar o Lema de Arden. fazendo isto obtemos

L4 = (0 ∪ 1)∗ε = (0 ∪ 1)∗.

Substituindo em L3,L3 = 0L1 ∪ 1(0 ∪ 1)∗.

De modo que, da segunda equação, segue que

L2 = 1(0L1 ∪ 1(0 ∪ 1)∗) = 10L1 ∪ 11(0 ∪ 1)∗.

Com isso, resulta da primeira equação que

L1 = 010L1 ∪ 011(0 ∪ 1)∗.

Usando o Lema de Arden mais uma vez,

L1 = 010∗(011(0 ∪ 1)∗),

que é a linguagem aceita pelo autômato.Antes de encerrar a seção precisamos fazer algumas considerações sobre

a aplicação do Lema de Arden.Em primeiro lugar, o que aconteceria se não tivéssemos notado que q5 é um

estado morto? Neste caso teríamos de confrontar a equação L5 = 0L5 ∪ 1L5,ou seja L5 = (0 ∪ 1)L5. Como L5 aparece dos dois lados da equação, seránecessário aplicar o Lema de Arden. Note que, neste casoX = L5,A = (0∪1)e B = ∅, de modo que

L5 = X = (0 ∪ 1)∗∅ = ∅,

que é o resultado esperado.O segundo comentário diz respeito à aplicação do Lema de Arden à equa-

çãoL4 = 0L4 ∪ 1L4 ∪ ε.

Na aplicação que fizemos anteriormente, tomamos A = (0 ∪ 1) e B = ε. Maso que aconteceria se escolhéssemos A = 0 e B = 1L4 ∪ ε? Neste caso,

L4 = 0∗(1L4 ∪ ε) = 0∗1L4 ∪ 0∗,


e continuamos com L4 dos dois lados da equação. Mas, ao invés de nos deixarintimidar, aplicaremos o Lema de Arden a esta última equação, o que nos dá

(3.1) L4 = (0∗1)∗0∗.

Note que se isto estiver correto (e está!) então devemos ter que os conjuntos(0∗1)∗0∗ e (0 ∪ 1)∗ são iguais–quer dizer, têm os mesmos elementos. Por-tanto, deve ser possível mostrar que toda palavra no alfabeto {0, 1} pertenceao conjunto (0∗1)∗0∗. Fica por sua conta se convencer disto. Finalmente,se adotarmos esta última maneira de expressar L4, a descrição da linguagemaceita pelo autômato que resulta do algoritmo de substituição é

010∗(011(0∗1)∗0∗).

Em particular, o algoritmo de substituição pode retornar linguagens diferentes,todas corretas, dependendo da maneira como for aplicado.

4. Expressões regulares

Utilizando o algoritmo de substituição sempre obtemos uma descrição bas-tante precisa da linguagem aceita por um autômato finito determinístico. Alémdisso, por causa da maneira como o algoritmo opera, a linguagem é quasesempre expressa como resultado da aplicação das operações de união, conca-tenação e estrela, aos conjuntos unitários formados pelos símbolos do alfabetodo autômato. As únicas excessões ocorrem quando a linguagem é vazia ou é ε.Formalizaremos isto em uma definição, como segue.

Seja Σ um alfabeto e seja

Σ = Σ ∪ {∪, ·, ∗, (, ), ∅, ε}.

Consideraremos o conjunto Σ como um outro alfabeto, uma extensão de Σ.Além disso, ∪, ·, ∗, (, ), ∅, ε serão considerados apenas como símbolos (isto é,seu dignificado será ignorado) quando estiverem posando de elementos de Σ.

Uma expressão regular é uma palavra no alfabeto Σ, construída recursiva-mente pela aplicação sucessiva das seguintes regras:

(1) se σ ∈ Σ então σ é uma expressão regular;(2) ∅ e ε são expressões regulares;(3) se r1 e r2 são expressões regulares, então (r1∪r2) e (r1 ·r2) também

são;(4) se r é uma expressão regular, então r∗ também é.

Não há nada de misterioso sobre (3) e (4), elas apenas refletem a maneiracorreta de se usar os símbolos ∪, · e ∗, quando são interpretados como operado-res de conjuntos. Portanto, se identificarmos 0, 1, ε e ∅ com os conjuntos {0},{1}, {ε} e ∅, uma expressão regular r ∈ Σ∗ corresponderá a um subconjuntoL(r) em Σ, a linguagem denotada pela expressão regular r.

Suponhamos, por exemplo, que Σ = {0, 1}. Neste caso

Σ = {0, 1,∪, ·, ∗, (, ), ∅, ε}.

4. EXPRESSÕES REGULARES 13

Como 0 e 1 são expressões regulares por (1), então 0∗ também é uma expressãoregular por (4). Mas isto implica, por (3), que (0∗ · 1) é regular. Usando (4)novamente, obtemos (0∗ · 1)∗, e por (3) concluímos que ((0∗ · 1)∗ · 0∗) é umaexpressão regular. Esta é a expressão regular que denota uma das maneiras derepresentar a linguagem L4 do final da seção 3. Entretanto, para obter umaexpressão regular corretamente construída, precisamos acrescentar parêntesisà representação de L4 dada pela equação (3.1). O papel dos parêntesis é apenaso de eliminar qualquer ambigüidade na interpretação das expressões.

A razão para introduzir expressões regulares como palavras em um alfa-beto, em vez de pensá-las simplesmente como a descrição de uma linguagem,é que expressões regulares distintas podem denotar o mesmo conjunto. Este éo caso, por exemplo, das expressões (0 ∪ 1)∗ e ((0∗ · 1)∗ · 0∗), como vimos aofinal da seção anterior.

É claro que qualquer conjunto que possa ser representado a partir dos con-juntos unitários ε e σ ∈ Σ e das operações de união, concatenação e estrelapode ser denotado por uma expressão regular. Em particular, se cuidarmosde pôr os parêntesis no lugar certo, o algoritmo de substituição aplicado a umautômato finitoM sempre retorna uma expressão regular que denota a lingua-gem L(M).

Resta-nos praticar um pouco a construção de uma expressão regular quedenote um conjunto dado, a partir da descrição deste conjunto. Suponhamosque Σ = {a, b, c}. Para obter todas as palavras em um certo subconjunto de Σdevemos usar a estrela de Kleene. Assim,

Linguagem formada por todas as palavras Expressão regular(vazias ou não) que só contêm a a∗

nos símbolos a, b e c ((a ∪ b) ∪ c)∗

que não contêm a (b ∪ c)∗

em a e cujo comprimento é par (a · a)∗

A última expressão merece um comentário. As palavras de comprimentopar tem a forma a2k, para algum k ≥ 0 inteiro. Mas,

a2k = (aa)k ∈ {aa}k.Portanto, o conjunto das palavras de comprimento par será⋃

k≥0

{aa}k = aa∗.

Já as palavras no símbolo a cujo comprimento é ímpar são da forma a2k+1 =a · (aa)k. Assim, a linguagem formada por essas palavras é denotada por(a · (a · a)∗).

Outro exemplo interessante consiste na linguagem formada pelas palavrasque contêm exatamente um a. Isto significa que os outros símbolos da palavratêm que ser bs ou cs. Como estes símbolos tanto podem aparecer antes como


depois do a, uma tal palavra será da forma uav, onde u e v são palavras quecontêm apenas b e c. Isto nos remete à expressão regular (((b∪c)∗·a)·(b∪c)∗)).

Como as expressões regulares já estão ficando bastante complicadas, va-mos suprimir os parêntesis e o ponto que denota concatenação, quando nãoforem absolutamente necessários à interpretação correta da expressão. Eviden-temente, ao fazer isto não obtemos uma expressão regular no sentido da defini-ção formal. Fica como exercício acrescentar os símbolos necessários para quecada uma das expressões dadas abaixo se torne uma expressão regular correta.

Duas variações, dignas de nota, do último exemplo acima são a linguagemformada por todas as palavras que contêm exatamente dois as, que correspondea

(b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗

e a linguagem formada por todas as palavras que contêm um número par de as,que é denotada por

((b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗)∗

Um exemplo um pouco mais difícil é a linguagem formada pelas palavras quecontêm um número ímpar de as. Precisamos adicionar um a extra à expressãoacima. O problema é que este a pode aparecer em qualquer lugar da palavra,de modo que não podemos simplesmente concatená-lo no início ou no fim daexpressão acima. A saída é tomar

((b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗)∗a((b ∪ c)∗a(b ∪ c)∗a(b ∪ c)∗)∗.

Encerramos com três exemplos de natureza mais prática.Um dos primeiros passos do processo de compilação de uma linguagem de

programação é conhecido como análise léxica. Nesta etapa o compilador iden-tifica, por exemplo, quais foram os números inteiros e as variáveis utilizadasno programa. É claro que esta é uma etapa necessária para que seja possívelinterpretar corretamente o programa. Na prática, isto pode ser feito com umautômato finito. Assim, para identificar as variáveis, construímos um autômatofinito que aceita a linguagem que descreve as variáveis de uma linguagem. Istoé feito em duas etapas. Primeiro obtemos uma expressão regular que denoteas variáveis da linguagem de programação. Em seguida, construímos um autô-mato finito que aceite esta linguagem.

Contudo, pôr esta estratégia em prática depende de sermos capazes deresolver algoritmicamente o seguinte problema.

PROBLEMA 3.1. Dada uma expressão regular r, construir um autômatofinito que aceite a linguagem denotada por r.

Abordaremos este problema detalhadamente a partir do próximo capítulo.Entretanto, já estamos em condições de obter expressões regulares para as lin-guagens que descrevem inteiros e variáveis de um programa, como veremos aseguir.

5. ANÁLISE FORMAL DO ALGORITMO DE SUBSTITUIÇÃO 15

Para começar determinaremos uma expressão regular no alfabeto {0, 1, . . . , 9}que denote os inteiros positivos no sistema decimal. À primeira vista pode pa-recer que a expressão seja simplesmente

(0 ∪ 1 ∪ · · · ∪ 9)∗.

O problema é que isto inclui palavras como 00000, que não correspondem a umnúmero formado de maneira correta. A solução é não permitir que as palavrascomecem com o símbolo 0, tomando

(1 ∪ · · · ∪ 9)(0 ∪ 1 ∪ · · · ∪ 9)∗.

Já a expressão que denota os inteiros não negativos é

0 ∪ (1 ∪ · · · ∪ 9)(0 ∪ 1 ∪ · · · ∪ 9)∗.

Finalmente, suponhamos que uma certa linguagem de programação tempor variáveis todas as palavras nos símbolos 0, 1, . . . , 9, A,B,C, . . . , Z quenão começam por um número inteiro. A expressão regular que denota as va-riáveis nesta linguagem de programação é

(A ∪B ∪ · · · ∪ Z)(A ∪B ∪ · · · ∪ Z ∪ 0 ∪ 1 ∪ · · · ∪ 9)∗.

5. Análise formal do algoritmo de substituição

Nesta seção damos uma descrição detalhada do algoritmo de substituição;isto é, uma descrição cuidadosa o suficiente para servir, tanto para programaro algoritmo, quanto para provar que funciona como esperado. Na verdade,encerramos a seção justamente com uma demonstração de que o algoritmoestá correto. Contudo, se você não pretende programar o algoritmo, nem sentenecessidade de uma demonstração formal, talvez seja melhor pular esta seçãoe passar ao próximo capítulo.

Começamos com algumas definições um tanto técnicas. Para t = 0, . . . ,mseja Σt o alfabeto definido por

Σt =

{Σ se t = 0

Σ ∪ {α1, . . . , αt} se t ≥ 1.

Seja agora Θt o conjunto formado pelas expressões regulares em Σt da forma⋃i≤t

ηi · αi,

onde ηi 6= ε é uma expressão regular em Σ0 = Σ. Note que Θ0 é o conjuntodas expressões regulares em Σ.

Dado θ ∈ Θt, seja L(θ) a linguagem obtida de acordo com as seguintesregras:

(1) L(ε) = {ε};(2) L(∅) = ∅;(3) L(αi) = Li;

com Li como definido na seção 1, e se α e β são expressões regulares em Σt

então


(4) L(α · β) = L(α) · L(β);(5) L(α ∪ β) = L(α) ∪ L(β);(6) L(α∗) = L(α)∗.

Estamos, agora, prontos para dar uma descrição minuciosa do funciona-mento do algoritmo.

Algoritmo de Substituição

Entrada: um autômato finito determinísticoA cujos ingredientes são (Σ, Q, q1, F, δ),onde Q = {q1, . . . , qn}.

Saída: uma expressão regular que denota a linguagem aceita por A.

Etapa 1: Para cada estado qi escreva uma expressão regular em Σm da forma

Ei =⋃{(σj · αj(i)) : δ(qi, σj) = qj(i)}

se qm não é estado final, ou

Ei =⋃{(σj · αj(i)) : δ(qi, σj) = qj(i)} ∪ {ε}

se qm é estado final; e inicialize k = m.

Etapa 2: Se Ek já está escrito como uma expressão regular em Θk−1, vápara (3), senão Ek é da forma

Ek = η · αk ∪B

onde B ∈ Θk−1. Neste caso escreva Ek = η∗ · B e vá para para a Etapa 3.Observe que pode acontecer que B = ∅; se isto ocorrer então Ek = ∅.

Etapa 3: Subtraia 1 de k. Se k = 0, então L(A) é denotada pela expressãoregular E1 no alfabeto Σ0 e podemos parar; senão, substitua αk por Ek naexpressão regular Ei para i 6= k e volte à Etapa 2.

Resta-nos apenas dar uma demonstração de que este algoritmo funciona.Faremos isso usando indução finita.

DEMONSTRAÇÃO. Digamos que, para um certo inteiro 0 ≤ k ≤ m esta-mos para executar o (m − k)-ésimo laço deste algoritmo. Queremos mostrarque, ao final deste laço

(1) Ei ∈ Θk−1 e(2) L(Ei) = Li,

para i = 1, . . . ,m. Para fazer isto, podemos supor que, chegados a este laço,temos Ei ∈ Θk e L(Ei) = Li para i = 1, . . . ,m. Observe que estas duasúltimas afirmações são claramente verdadeiras quando k = m.

Começamos considerando a execução da Etapa 2 no (m− k)-ésimo laço.Se já temos que Ek ∈ Θk−1 então nada há a fazer nesta etapa. Por outro lado,se Ek /∈ Θk−1, então como Ek ∈ Θk podemos escrever

(5.1) Ek = ηk · αk ∪B,

6. EXERCíCIOS 17

onde B ∈ Θk−1. Seja F = η∗k ·B. Temos de (5.1) e (2) que

Ak = L(Ek) = L(ηk) ·Ak ∪ L(B).

Logo, pelo lema de Arden,

Ak = L(ηk)∗ · L(B),

mas isto é igual a L(F ). Como o algoritmo manda fazer Ek = F , obtemos, aofinal desta etapa, que Ek ∈ Θk−1 e L(Ek) = Ak.

Finalmente, na etapa 3, basta substituir αk por F na expressão regular deEj sempre que j 6= k. Note que segue imediatamente disto que Ej ∈ Θk−1 eque L(Ej) = Aj .

6. Exercícios

1. Seja Σ = {0, 1}. Se L1 = {0} e L2 = {1}∗, determine:(1) L1 ∪ L2 e L1 ∩ L2;(2) L∗1 e L∗2;(3) (L1 ∪ L2)∗;(4) L∗1 ∩ L2;(5) L1;(6) L2 ∩ L∗1.

2. Se L é uma linguagem em um alfabeto Σ então LR = {wR : w ∈ L}. SeL = {0} · {1}∗ calcule LR.

3. Seja L uma linguagem no alfabeto Σ. O que podemos concluir a respeito deL se L+ = L∗ \ {ε}?

4. Sejam Σ1 e Σ2 dois alfabetos e seja φ : Σ1 → Σ∗2 uma aplicação. Se L éuma linguagem no alfabeto Σ1, mostre que φ(L∗) = φ(L)∗.

5. Para cada um dos autômatos finitos determinísticos, no alfabeto {0, 1}, da-dos abaixo:• esboce o diagrama de estados;• encontre os sorvedouros e os estados mortos;• determine a expressão regular da linguagem aceita pelo autômato usando

o algoritmo de substituição.(a) Os estado são {q1, . . . , q4}, o estado inicial é q1, o conjunto de estados

finais é {q2} e a função de transição é dada por:δ 0 1

q1 q2 q4

q2 q3 q1

q3 q4 q4

q4 q4 q4(b) Os estado são {q1, . . . , q5}, o estado inicial é q1, o conjunto de estados

finais é {q3, q4} e a função de transição é dada por:


δ 0 1

q1 q2 q4

q2 q2 q3

q3 q5 q5

q4 q5 q5

q5 q5 q5(c) Os estado são {q1, . . . , q4}, o estado inicial é q1, o conjunto de estados


q1 q2 q4

q2 q3 q1

q3 q4 q2

q4 q4 q4(d) Os estado são {q1, q2, q3}, o estado inicial é q1, o conjunto de estados


q1 q1 q2

q2 q3 q2

q3 q1 q2(e) Os estado são {q1, . . . , q6}, o estado inicial é q1, o conjunto de estados


q1 q5 q2

q2 q5 q3

q3 q4 q3

q4 q4 q4

q5 q6 q2

q6 q6 q4

6. Descreva em português o conjunto denotado por cada uma das expressõesregulares abaixo:(a) 1∗0;(b) 1∗0(0)∗

(c) 111 ∪ 001;(d) (1 ∪ 00)∗;(e) (0(0)∗1)∗;(f) (0 ∪ 1)(0 ∪ 1)∗00;

7. Expresse cada uma das seguintes linguagens no alfabeto {0, 1} usando umaexpressão regular:(a) o conjunto das palavras de um ou mais zeros seguidos de um 1;

6. EXERCíCIOS 19

(b) o conjunto das palavras de dois ou mais símbolos seguidos por três oumais zeros;

(c) o conjunto das palavras que contêm uma seqüência de 1s, de modo queo número de 1s na seqüência é congruente a 2 módulo 3, seguido deum número par de zeros.

8. Se r e s são expressões regulares, vamos escrever r ≡ s se e somente seL(r) = L(s). Supondo que r, s e t são expressões regulares, mostre que:(a) (r ∪ r) ≡ r;(b) ((r · s) ∪ (r · t)) ≡ (r · (s ∪ t));(c) ((s · r) ∪ (t · r)) ≡ ((s ∪ t) · r);(d) (r∗ · r∗) ≡ r∗;(e) (r · r∗) ≡ (r∗ · r);(f) r∗∗ ≡ r∗;(g) (ε ∪ (r · r∗)) ≡ r∗;(h) ((r · s)∗ · r) ≡ (r · (s · r)∗);(i) (r ∪ s)∗ ≡ (r∗ · s∗)∗ ≡ (r∗ ∪ s∗)∗.

9. Usando as identidades do exercício 4 prove que

((abb)∗(ba)∗(b ∪ aa)) ≡ (abb)∗((ε ∪ (b(ab)∗a))b ∪ (ba)∗(aa)).

Observe que alguns parênteses e o símbolo “·” foram omitidos para facilitara leitura.

CAPíTULO 4

Linguagens que não são regulares

O objetivo deste capítulo é desenvolver um método que nos permita mos-trar que uma dada linguagem não é regular. Nossa estratégia será a seguinte.Em primeiro lugar, mostraremos que toda linguagem regular satisfaz certa pro-priedade, conhecida como propriedade do bombeamento. Assim, para provarque uma dada linguagem não é regular basta constatar que não satisfaz estapropriedade. Isto é, provaremos que uma linguagem não é regular através deuma demonstração por contradição.

1. Propriedade do bombeamento

Começamos por introduzir a terminologia básica e obter uma primeiraaproximação para a propriedade de bombeamento das linguagens regulares.

Considere o autômato M da figura abaixo.

I // ?>=<89:;q10 //

1

%%JJJJJJJJJJJJ?>=<89:;q2

1 //

0

��8888888?>=<89:;q3

0 //

1

��

?>=<89:;q40 //

1

|| ?>=<89:;q51 //

0

yytttttttttttt?>=<89:;76540123q6

0,1

vvmmmmmmmmmmmmmmmmmm

?>=<89:;q7

0,1

UU

FIGURA 1

Entre as palavras aceitas por este autômato temos:

w = 01011001.

Se considerarmos o caminho indexado pela palavra w = 01011001, vemosque inclui um ciclo que começa em q2 e acaba em q4. Este ciclo corresponde à

21

22 4. LINGUAGENS QUE NÃO SÃO REGULARES

subpalavra y = 101 de 01011001. Mais precisamente, podemos decompor wna forma

w = 0︸︷︷︸x

101︸︷︷︸y

1001︸︷︷︸z

= xyz.

Observe que podemos percorrer o ciclo indexado por y várias vezes e aindaassim obter uma palavra que é aceita por M . Por exemplo, percorrendo o ciclo3 vezes obtemos

xy3z = 0︸︷︷︸x

101︸︷︷︸y

101︸︷︷︸y

101︸︷︷︸y

1001︸︷︷︸z

,

que é aceita por M . De fato, podemos até remover a subpalavra y de w eainda assim continuaremos com uma palavra aceita pelo autômato, neste casoxz = 01001. Resumindo, verificamos que a palavra w = xyz é aceita porM e que admite uma subpalavra y 6= ε que pode ser removida ou repetidavárias vezes sem que a palavra resultante fique fora de L(M). Sempre que istoacontecer diremos que y é uma subpalavra de w que é bombeável em L(M).

Naturalmente, o ponto chave é o fato da subpalavra y indexar um ciclo nografo de M . Na verdade, esta não é a única subpalavra bombeável de w umavez que podemos considerar o ciclo como começando em qualquer um de seusvértices. Assim, se tomarmos o início do ciclo como sendo q4, concluímos quea subpalavra 110 também é bombeável; isto é,

010(110)k01 ∈ L(M) para todo k ≥ 0.

É conveniente estabelecer a noção de bombeabilidade em um contextomais geral que o das linguagens regulares. Seja L uma linguagem em umalfabeto Σ e seja w ∈ L. Dizemos que y ∈ Σ∗ é uma subpalavra de wbombeável em L se

(1) y 6= ε;(2) existem x, z ∈ Σ∗ tais que w = xyz;(3) xykz ∈ L para todo k ≥ 0.

A única função da condição (1) é excluir o caso trivial y = ε da definiçãode palavra bombeável; já (2) significa que y é subpalavra de w. Quanto a (3),o ponto crucial a observar é que, para que seja y seja bombeável é precisoque seja possível omiti-la ou repeti-la no interior de w tantas vezes quantodesejarmos sem que a palavra resultante deixe de pertencer a L. Para entendermelhor este ponto, considere o autômato M ′ da figura 2.

É claro que 0 é uma subpalavra de 10 ∈ L(M ′). Além disso, podemosrepetir a subpalavra 0 várias vezes e ainda assim obter uma palavra em L(M ′);de fato, 1, 10, 102, 103 e 104 pertencem a L(M ′). Apesar disto, 0 não é umasubpalavra de 10 bombeável em L(M ′), porque se k ≥ 5 então 10k /∈ L(M ′).

Permanecendo com o autômato M ′ da figura 2, vemos que

L(M ′) = {1, 10, 102, 103, 104}.

Em particular, não há nenhuma palavra de L(M ′) que admita uma subpala-vra bombeável. Isto não é surpreendente. De fato, se uma linguagem admite

2. LEMA DO BOMBEAMENTO 23

I // ?>=<89:;q11 //

0

%%JJJJJJJJJJJJ?>=<89:;76540123q2

0 //

1

��8888888?>=<89:;76540123q3

0 //

1

��

?>=<89:;76540123q40 //

1

��?>=<89:;76540123q5

0 //

1

yytttttttttttt?>=<89:;76540123q6

0,1

vvmmmmmmmmmmmmmmmmmm

?>=<89:;q7

0,1

UU

FIGURA 2

uma palavra que tem uma subpalavra bombeável, então é claro que a lingua-gem é infinita. Há dois pontos importantes nesta discussão que você não deveesquecer:

• nenhuma palavra de uma linguagem finita L admite subpalavra bom-beável em L;

• para que uma subpalavra seja bombeável é preciso que possa ser re-petida qualquer número de vezes sem que a palavra resultante saia deL.

2. Lema do bombeamento

Diante do que acabamos de ver, uma pergunta se impõe de maneira natu-ral:

dada uma linguagem L, como achar uma palavra de L queadmita uma subpalavra bombeável?

Em primeiro lugar, esta pergunta só faz sentido se L for infinita. Além disso,vamos nos limitar, de agora em diante, às linguagens regulares. Sendo assim,vamos supor que L ⊂ Σ∗ é uma linguagem infinita que é aceita por um autô-mato finito determinístico M no alfabeto Σ.

Se conhecemosM o problema é fácil de resolver: basta achar um ciclo emM . Mas suponha que, apesar de conhecer L, sabemos de M apenas que temn estados. Será que esta informação é suficiente para achar uma palavra de Lque tenha uma subpalavra bombeável em L? A resposta é sim, e mais uma veztrata-se apenas de achar um ciclo em M . Só que, como não conhecemos M ,não temos uma maneira de identificar qual é este ciclo. Mesmo assim somoscapazes de saber que um tal ciclo tem que existir. Fazemos isto recorrendo aum princípio que aprendemos a respeitar ainda criança, quando brincamos dedança das cadeiras.

PRINCÍPIO DA CASA DO POMBO. Se, em um pombal, há mais pombosque casas, então dois pombos vão ter que ocupar a mesmo casa.

Nossa aplicação deste princípio depende de termos, de um lado uma lin-guagem infinita, de outro um autômato finito determinístico. De fato, como Lé infinita, terá palavras de comprimento arbitrariamente grande. Em particu-lar, podemos escolher uma palavra w cujo comprimento é muito maior que o


número n de estados de M . Considere o caminho indexado por w no grafo deM . Como M tem n estados e w tem muito mais do que n símbolos, este ca-minho tem que passar duas vezes por um mesmo estado. Mas um caminho nografo de M no qual há estados repetidos tem que conter um ciclo. Entretanto,já sabemos que um ciclo no caminho indexado por w nos permite determinaruma subpalavra bombeável de w. Com isto provamos a seguinte propriedadedo bombeamento das linguagens regulares:

Seja M um autômato finito determinístico. Se w é umapalavra de L(M) de comprimento maior que o número deestados do autômato, entãow admite uma subpalavra bom-beável em L(M).

O lema do bombeamento, que é o principal resultado deste capítulo, nãopassa de uma versão refinada da propriedade do bombeamento enunciada acima.

LEMA DO BOMBEAMENTO. Seja M um autômato finito determinísticocom n estados e seja L a linguagem aceita por M . Se w é uma palavra de Lcom comprimento maior ou igual a n então existe uma decomposição de w naforma w = xyz, onde

(1) y 6= ε;(2) |xy| ≤ n;(3) xykz ∈ L para todo k ≥ 0.

Antes de passar à demonstração, observe que (1) e (3) nos dizem apenasque y é subpalavra de w bombeável em L. A única novidade é a condição(2). Esta condição técnica permite simplificar várias demonstrações de nãoregularidade, reduzindo o número de casos que precisam ser considerados.

DEMONSTRAÇÃO. A estratégia adotada no início da seção consistiu emconsiderar o caminho no grafo de M indexado por w. Como observamos nocapítulo 2, isto é formalizado através da computação de M determinada por w.

Seja Σ o alfabeto de M . Então podemos escrever w = σ1 · · ·σn, ondeσ1, . . . , σn são elementos de Σ não necessariamente distintos. Seja q1 o estadoinicial de M . Temos, então, uma computação

(q1, w) = (q1, σ1 · · ·σn) ` (q2, σ2 · · ·σn) ` · · · ` (qn, σn) ` (qn+1, ε).

Observe que também não estamos supondo que os estados q1, . . . , qn+1 sãotodos distintos. De fato, dois destes estados têm que coincidir, porque M sótem n estados. Digamos que qi = qj , onde 1 ≤ i < j ≤ n + 1. Qualquerescolha de i e j que satisfaça as condições acima é suficiente para provar (1)e (3); mas não (2). Para garantir (2) precisamos escolher qj como sendo oprimeiro estado que coincide com algum estado anterior. Assumindo desde jáque i e j são inteiros entre 1 e n+1, precisamos fazer a seguinte hipótese sobrej:

Hipótese: j é o menor inteiro para o qual existe i < j tal que qi = qj .

3. APLICAÇÕES DO LEMA DO BOMBEAMENTO 25

Levando tudo isto em conta, podemos reescrever a computação na forma

(q1, w) = (q1, σ1 · · ·σn) `∗ (qi, σi · · ·σn) `∗ (qj , σj · · ·σn) `∗ (qn, σn) ` (qn+1, ε).

O ciclo que procuramos está identificado pelo trecho da computação que vaide qi a qj = qi. Isto sugere que devemos tomar

x = σ1 · · ·σi−1, y = σi · · ·σj−1 e z = σj · · ·σn+1.

Além disso, como i < j temos que

y = σi · · ·σj−1 6= ε,

de forma que a condição (1) é satisfeita. Usando esta notação, a computaçãofica

(q1, w) = (q1, xyz) `∗ (qi, yz) `∗ (qj , z) `∗ (qn+1, ε).

Note que, como qi = qj , a palavra y leva a computação do estado qi ao estadoqi. Desta forma, repetindo ou omitindo y, podemos fazer este trecho repetir-sevárias vezes no interior da computação sem alterar o estado em que compu-tação termina, que continuará a ser qn+1. Por exemplo, repetindo y uma veztemos a palavra xy2z, que dá lugar à computação

(q1, xy2z) `∗ (qi, y

2z) `∗ (qj , yz) = (qi, yz) `∗ (qj , z) `∗ (qn+1, ε).

Como xyz ∈ L(M) por hipótese, então qn+1 é um estado final deM . Portanto,xy2z ∈ L(M). De maneira semelhante xykz ∈ L(M) para todo k ≥ 0, o queprova (3).

Falta-nos apenas explicar porque (2) vale. Mas, |xy| = j − 1. Entre-tanto, qj é o primeiro estado que coincide com algum estado anterior. Isto é,q1, . . . , qj−1 são todos estados distintos. ComoM tem n estados, isto significaque j − 1 ≤ n. Portanto, |xy| ≤ n, o que completa a demonstração.

Antes de passar às aplicações é preciso chamar a atenção para o fato de quea recíproca do lema do bombeamento é falsa. Isto é, o fato de uma linguagemL conter palavras que admitem subpalavras bombeáveis não garante que Lseja regular. Portanto, não é possível provar regularidade usando o lema dobombeamento. Voltaremos a discutir este ponto no exemplo 5.

3. Aplicações do lema do bombeamento

O maior obstáculo à aplicação do lema do bombeamento está na inter-pretação correta do seu enunciado. Seja M um autômato finito determinísticocom n estados. Segundo o lema do bombeamento, dada qualquer palavraw ∈ L(M) de comprimento maior que n existe uma subpalavra y 6= ε que ébombeável em L(M). Note que o lema não diz que qualquer subpalavra de wé bombeável, mas apenas que existe uma subpalavra de w que é bombeável.

Por exemplo, considere a linguagem L no alfabeto {0} formada pelas pa-lavras de comprimento par. É fácil construir um autômato finito com 2 estadosque aceita L, portanto esta é uma linguagem regular e n = 2. Vamos escolheruma palavra de L de comprimento maior que 2; digamos, 06. Não é verdade


que qualquer subpalavra de 06 é bombeável em L. Por exemplo, 0 é uma sub-palavra de 06, já que temos uma decomposição 06 = 02 ·0·03; mas bombeando0 obtemos

02 · 0k · 03 = 05+k,

que não pertence a L se k por par. De fato, para que a subpalavra seja bom-beável em L é preciso que tenha comprimento par. Assim, neste exemplo,poderíamos escolher as subpalavras 02, 04 ou 06 para bombear.

Tudo isto pode parecer óbvio. O problema é que um nível adicional dedificuldade surge nas aplicações, porque desejamos usar o lema para provarque uma linguagem não é regular. Imagine que temos uma linguagem L e que,por alguma razão, desconfiamos que L não é regular. Para provar que L de fatonão é regular podemos proceder por contradição.

Suponha, então, por contradição, que L seja aceita por algum autômatofinito determinístico com n estados. De acordo com o lema do bombeamentoqualquer palavra w ∈ L de comprimento maior que n terá que admitir umasubpalavra bombeável. Assim, para obter uma contradição, basta achar umapalavra em L (o que é uma boa notícia!) que não tenha nenhuma subpalavrabombeável (o que é uma má notícia!).

Um último comentário antes de passar aos exemplos. Neste esboço de de-monstração por contradição supusemos que L é aceita por um autômato finitodeterminístico com n estados. Entretanto, ao fazer esta hipótese não podemosespecificar um valor numérico para n. De fato, se escolhermos n = 100, tudoo que teremos provado é que a linguagem não pode ser aceita por um autômatocom 100 estados. Mas nada impediria, em princípio, que fosse aceita por umautômato com 101 estados. Resta-nos aplicar estas considerações gerais emalguns exemplos concretos.

Exemplo 1. Considere a linguagem no alfabeto {0} definida por

Lprimos = {0p : p é um primo positivo}.

A primeira coisa a observar é que esta linguagem é infinita. Isto é uma con-seqüência de teorema provado pelo matemático grego Euclides por volta de300 a. C., segundo o qual existem infinitos números primos.

Em seguida devemos considerar se seria possível construir um autômatofinito que aceitasse esta linguagem. Para isto, seria necessário que o autômatopudesse determinar se um dado número p é primo ou não. Em outras palavras,o autômato teria que se certificar que p não é divisível pelos inteiros positivosmenores que p. Como a quantidade de inteiros menores que p aumenta com p,isto requer uma memória infinita; que é exatamente o que um autômato finitonão tem. Esta é uma boa indicação de que Lprimos não é regular. Vamoscomprovar nosso palpite usando o lema do bombeamento.

Suponha, então, por contradição, que Lprimos é aceita por um autômatofinito determinístico com n estados. Precisamos escolher uma palavra comcomprimento maior que n em Lprimos. Para fazer isto, basta escolher umprimo q > n. A existência de um tal primo é conseqüência imediata do teorema


de Euclides mencionado acima. Portanto, 0q é uma palavra de Lprimos decomprimento maior que n.

Nestas circunstâncias, o lema do bombeamento garante que existe uma de-composição 0q = xyz de modo que y 6= ε é bombeável em Lprimos. Comoo que desejamos é contradizer esta afirmação, temos que mostrar que 0q nãoadmite nenhuma subpalavra bombeável. Neste exemplo é fácil executar estaestratégia neste grau de generalidade. De fato, uma subpalavra não vazia qual-quer de 0q tem que ser da forma 0j para algum 0 < j ≤ q. Mas x e z tambémsão subpalavras de 0q; de modo que também são cadeias de zeros. Tomando,x = 0i, teremos que z = 0q−i−j .

Bombeando y, concluímos que

xykz = 0i(0j)k0q−i−j = 0i+jk+(q−i−j) = 0q+(k−1)j

deve pertencer a Lprimos para todo k ≥ 0. Mas isto só pode ocorrer se q+(k−1)j for um número primo para todo k ≥ 0. Entretanto, tomando k = q + 1,obtemos

q + (k − 1)j = q + qj = q(1 + j)

que não pode ser primo porque tanto q quanto j+1 são números maiores que 1.Temos assim uma contradição, o que confirma nossas supeitas de que Lprimos

não é regular.

Note que a condição (2) do lema do bombeamento não foi usada em ne-nhum lugar nesta demonstração. Como frisamos anteriormente, esta é umacondição técnica que serve para simplificar o tratamento de exemplos maiscomplicados, como veremos a seguir.

Exemplo 2. Nosso próximo exemplo é a linguagem

L = {ambm : m ≥ 0}

no alfabeto {a, b}. Também neste caso é fácil dar um argumento heurístico quenos leva a desconfiar que L não pode ser regular. Lembre-se que o autômatolê a entrada da esquerda para a direita. Assim, ele lerá toda a seqüência de asantes de chegar aos bs. Portanto, o autômato tem que lembrar quantos as viupara poder comparar com o número de bs. Mas a memória do autômato é finita,e não há restrições sobre a quantidade de as em uma palavra de L.

Para provar que L não é regular vamos recorrer ao lema do bombeamento.Suponha, por contradição, queL é aceita por um autômato finito determinísticocom n estados. Em seguida temos que escolher uma palavra w de L comcomprimento maior que n; digamos que w = anbn. Como |w| = 2n > n, temque existir uma decomposição

anbn = xyz

de forma que as condições (1), (2) e (3) do lema do bombeamento sejam satis-feitas.

Mas que decomposições de anbn satisfazem estas condições? Dessa vezcomeçaremos analisando (2), segundo a qual |xy| ≤ n. Isto é, xy é um prefixo


de anbn de comprimento menor ou igual a n. Como anbn começa com n letrasa, concluímos que a é o único símbolo que x e y podem conter. Portanto,

x = ai e y = aj .

Além disso, j 6= 0 pela condição (1). Já z reúne o que sobrou da palavra w, demodo que

z = an−i−jbn.

Observe que não há razão pela qual xy tenha que ser igual a an, de modo quepodem sobrar alguns as em z.

Resta-nos bombear y. Fazendo isto temos que

xykz = ai · (aj)k · an−i−jbn = an+(k−1)jbn,

é um elemento de L para todo k ≥ 0. Contudo, an+(k−1)jbn só pode pertencera L se os expoentes de a e b coincidirem. Porém

n+ (k − 1)j = n para todo k ≥ 0

implica que j = 0, contradizendo a condição (1) do lema do bombeamento.

Antes de passar ao próximo exemplo convém considerar a escolha quefizemos para a palavra de comprimento maior que n. Não parece haver nada deextraordinário nesta escolha, mas a verdade é que nem toda escolha de w seriasatisfatória. Por exemplo, assumindo que n ≥ 2, teríamos que |an−1bn−1| =2n− 2 ≥ n. Entretanto, esta não é uma boa escolha para w. A razão é que

an−1bn−1 = xyz e |xy| ≤ n

não excluem a possibilidade de y conter um b. Isto nos obrigaria a considerardois casos separadamente, a saber, y = aj e y = ajb, o que complicaria umpouco a demonstração. Diante disto, podemos descrever o papel da condição(2) como sendo o de restringir os possíveis y. O problema é que isto não sedá automaticamente mas, como no exemplo acima, depende de uma escolhaadequada para w.

Por sorte, na maioria dos casos, muitas escolhas para w são possíveis.Neste exemplo, bastaria tomar w = arbr com r ≥ n. Entretanto, para algu-mas linguagens a escolha da palavra requer bastante cuidado, como mostra opróximo exemplo.

Exemplo 3. Um argumento heurístico semelhante ao usado para a linguagemanterior sugere que

L = {ambr : m ≥ r}não deve ser regular. Vamos provar isto usando o lema do bombeamento.

Suponhamos, por contradição, que L seja aceita por um autômato finitodeterminístico com n estados. Neste exemplo, como no anterior, uma escolhapossível para uma palavra de comprimento maior que n em L é anbn. Dacondição (2) do lema do bombeamento concluímos que, se anbn = xyz, então

x = ai e y = aj .


Já condição (1) nos garante que j 6= 0. Como z = an−i−jbn, obteremos, aobombear y, que

xykz = ai · (aj)k · an−i−jbn = an+(k−1)jbn.

Mas, para que esta palavra esteja em L é preciso que

n+ (k − 1)j ≥ n,donde segue que (k − 1)j ≥ 0. Por sua vez, j 6= 0 força que k − 1 ≥ 0, ouseja, que k ≥ 1. Mas, para que y seja bombeável é preciso que xykz ∈ L paratodo k ≥ 0, e não apenas k ≥ 1. Portanto, temos uma contradição com o lemado bombeamento, o que prova que L não é regular.

Desta vez estivemos perto de não chegar a lugar nenhum! De fato, umacontradição só é obtida porque tomando k = 0,

an+(k−1)jbn = an−jbn

não pertence a L. Entretanto, neste exemplo, muitas escolhas aparentementeadequadas de w não levariam a nenhuma contradição. Por exemplo, é fácilse deixar sugestionar pelo sinal ≥ e escolher w = an+1bn. Esta palavra temcomprimento maior que n e qualquer decomposição da forma an+1bn = xyzrequer que x e y só tenham as. Entretanto, tomando

x = ai, y = aj e z = an+1−i−jbn,

e bombeando y, obtemos

xykz = an+1+(k−1)jbn

que pertence a L desde que 1 ≥ (1 − k)j. Infelizmente, neste caso isto nãoleva a contradição nenhuma, a não ser que j > 1, e não temos como descartara possibilidade de j ser exatamente 1.

A próxima linguagem requer uma escolha ainda mais sutil da palavra w.

Exemplo 4. Considere agora a linguagem

Luu = {uu : u ∈ {0, 1}∗}.Como nos exemplos anteriores, é fácil descrever um argumento heurístico parajustificar porque seria de esperar que Luu não fosse regular, e deixaremos istocomo exercício. Para provar a não regularidade de Luu pelo lema do bombe-amento, suporemos que esta linguagem é aceita por um autômato finito deter-minístico com n estados.

O principal problema neste caso é escolher uma palavra de comprimentomaior que n que nos permita chegar facilmente a uma contradição. A escolhamais óbvia é u = 0n, que, infelizmente, não leva a nenhuma contradição,como mostra o exercício 5. Felizmente uma variação simples desta palavra semostra adequada, a saber u = 0n1. Neste caso, w = 0n10n1 tem comprimento2n+ 2 > n, e qualquer decomposição

0n10n1 = xyz


satisfazx = 0i, y = 0j e z = 0n−i−j10n1

para algum i ≥ 0 e j ≥ 1. Bombeando y obtemos

xykz = 0n+(k−1)j10n1

Para saber se esta palavra pertence ou não a Luu precisamos descobrir se podeser escrita na forma vv para algum v ∈ {0, 1}∗. Igualando

0n+(k−1)j10n1 = vv

concluímos que v tem que terminar em 1. Como só há um outro 1 na palavra,

v = 0n+(k−1)j1 = 0n1.

Isto é, n + (k − 1)j = n. Como j 6= 0, esta igualdade só é verdadeira sek = 1. Mas isto contradiz o lema do bombeamento, segundo o qual xykzdeveria pertencer a Luu para todo k ≥ 0.

Os exemplos anteriores mostram que a demonstração pelo lema do bom-beamento de que uma certa linguagem L não é regular obedece a um padrão,que esboçamos abaixo:

Suponhamos, por contradição, que L seja aceita por umautômato finito determinístico com n estados.• Escolha uma palavra w ∈ L, de comprimento maior

que n, de modo que as possibilidades para uma de-composição da forma w = xyz sejam bastante limi-tadas.

• Bombeie y e mostre que se xykz ∈ L então uma con-tradição é obtida.

As principais dificuldades em fazer funcionar esta estratégia são as seguintes:• a escolha de uma palavra w adequada;• a identificação correta da condição que a pertinência xykz ∈ L im-

põe sobre os dados do problema.No exercício 7 temos um exemplo de demonstração em que vários erros foramcometidos na aplicação desta estratégia. Resolver este exercício pode ajudá-loa evitar os erros mais comuns que surgem na aplicação do lema do bombea-mento.

Infelizmente o lema do bombeamento está longe de ser uma panacéia in-falível. Para ilustrar isto, vamos considerar mais um exemplo.

Exemplo 5. Seja L a linguagem no alfabeto {a, b, c} formada pelas palavrasda forma aibjcr para as quais i, j, r ≥ 0 e, se i = 1 então j = r. Mostraremosque a única palavra de L que não admite uma subpalavra bombeável é ε.

Há dois casos a considerar. No primeiro, i 6= 1 e j e r não são ambosnulos. Neste caso a subpalavra bombeável é y = b se j 6= 0 ou y = c se r 6= 0.O segundo caso consiste em supor que i = 1, ou que i 6= 1 mas j = r = 0.Desta vez podemos tomar y = a como sendo a palavra bombeável.

4. EXERCíCIOS 31

Como cada palavra de L se encaixa em um destes dois casos, provamosque toda palavra de L admite uma subpalavra bombeável. Entretanto, estalinguagem não é regular. Assim, constatamos neste exemplo que:

• a recíproca do lema do bombeamento é falsa; isto é, não basta queo resultado do lema do bombeamento seja verdadeiro para que a lin-guagem seja regular;

• nem sempre o lema do bombeamento basta para mostrar que umalinguagem não é regular.

Provaremos que a linguagem acima de fato não é regular no capítulo ???. Paraisto, além do lema do bombeamento, vamos precisar usar um resultado sobre aestabilidade das linguagens regulares por intersecção.

4. Exercícios

1. Considere o autômato finito determinísticoM no alfabeto {0, 1}, com es-tado inicial q1, conjunto de estados finais {q5, q6, q8} e função de transiçãoδ dada pela seguinte tabela:

δ 0 1

q1 q2 q6

q2 q6 q3

q3 q4 q2

q4 q2 q5

q5 q5 q5

q6 q7 q4

q7 q8 q4

q8 q4 q5

(a) Esboce o diagrama de estados do autômato M .(b) Ache uma subpalavra de 010011101000 que possa ser bombeada na

linguagem L(M).(c) Sejaw = 00. Verifique quew,w2 ∈ L(M). w é bombeável emL(M)?

2. Considere a linguagem L no alfabeto {0, 1} dada por

L = {10, 10120, 10120130, 10120130140, . . . }.

(a) Mostre que L é infinita mas não admite nenhuma palavra que tenhauma subpalavra bombeável.

(b) Mostre que L não é regular.

3. Seja M um autômato finito determinístico e L a linguagem aceita por M .Vimos que para encontrar uma palavra de L que contém uma subpalavrabombeável basta encontrar um caminho no grafo de M que contenha umciclo. Suponha agora que não conhecemos M , mas que conhecemos uma


expressão regular r que denota L. De que forma podemos usar r para acharuma palavra de L que tem uma subpalavra bombeável?

4. Ache uma palavra que contenha uma subpalavra bombeável na linguagemdenotada pela expressão regular

(1 · 1 · 0) · (((1 · 0)∗ · 0) ∪ 0).

5. Considere a linguagem

Luu = {uu : u ∈ {0, 1}∗}.

Mostre que, tomando u = 0n, a palavra uu admite uma subpalavra bombeá-vel em Luu.SUGESTÃO: Tome uma subpalavra de comprimento par.

6. Mostre que se L é uma linguagem regular infinita, então L admite pelosmenos uma palavra que tem uma subpalavra bombeável.

7. Considere a linguagem

L = {02n

: n ≥ 0}.

Determine os erros cometidos na demonstração abaixo de que L não é regu-lar. Corrija estes erros e dê uma demonstração correta da não regularidadede L.

Suponha que L é aceita por um autômato finito determinístico.Seja w = 02

n

. Pelo lema do bombeamento podemos decompor wna forma w = xyz, onde

x = 0r, y = 0s e z = 02n−r−s.

Bombeando y obtemos

xykz = 02n+(k−1)s.

Mas para que esta palavra pertença a L é preciso que 2n + (k −1)s = 2n, o que só é possível se (k − 1)s = 0. Como s 6= 0,concluímos que k só pode ser igual a 1, o que contradiz o lema dobombeamento.

8. Verifique quais das linguagens dadas abaixo são regulares e quais não são.Em cada caso justifique cuidadosamente sua resposta.(a) {0i12i : i ≥ 1};(b) {(01)i : i ≥ 1};(c) {12n : n ≥ 1};(d) {0n1m0n+m : n,m ≥ 1};(e) {12n : n ≥ 0};(f) {w : w = wr onde w ∈ {0, 1}};(g) {wxwr : w, x ∈ {0, 1}∗ \ {ε}}.

4. EXERCíCIOS 33

Sew é uma palavra em um alfabeto Σ entãowr é a palavra obtida invertendo-se a ordem das letras em w. Portanto se uma palavra satisfaz w = wr entãoé um palíndromo.

9. Uma palavra w no alfabeto {(, )} é balanceada se:(a) em cada prefixo de w o número de (s não é menor que o número de )s

e(b) o número de (s em w é igual ao número de )s.

Isto é,w é balanceada se pode ser obtida a partir de uma expressão aritméticacorretamente escrita pela omissão das variáveis, números e símbolos dasoperações. Mostre que a linguagem L que consiste nas palavras balanceadasno alfabeto {(, )} não é regular.

10. Use o lema do bombeamento para mostrar que, se uma linguagem L contémuma palavra de comprimento maior ou igual a n e é aceita por um autô-mato finito determinístico com n estados, então L é infinita. Use isto paradescrever um algoritmo que permite decidir se a linguagem aceita por umautômato finito determinístico dado é ou não infinita.

11. Seja M um autômato finito determinístico com n estados e seja L a lingua-gem aceita por M .(a) Use o lema do bombeamento para mostrar que seL contém uma palavra

de comprimento maior ou igual que 2n, então ela contém uma palavrade comprimento menor que 2n.

(b) Mostre que L é infinita se e somente se admite uma palavra de compri-mento maior ou igual a n e menor que 2n.

(c) Descreva um algoritmo baseado em (3) que, tendo como entrada umautômato finito determinístico M , determina se L(M) é finita ou infi-nita.

SUGESTÃO: Para provar (a) use o lema do bombeamento com k = 0.

12. SejaM um autômato finito determinístico com n estados e um alfabeto dem símbolos.(a) Use (a) para mostrar que L(M) é não vazia se e somente se contém

uma palavra de comprimento menor ou igual a n.(b) Explique como isto pode ser usado para criar um algoritmo que verifica

se a linguagem de um autômato finito determinístico é ou não vazia.(c) Suponha que a linguagem aceita por M é vazia. Quantas são as pa-

lavras que terão que ser testadas antes que o algoritmo de (b) possachegar a esta conclusão? O que isto nos diz sobre a eficiência destealgoritmo?

CAPíTULO 5

Autômatos finitos não determinísticos

1. Desenhe o diagrama de estados e descreva a linguagem aceita por cada umdos seguintes autômatos finitos não determinísticos. Em cada caso o estadoinicial é q1.(a) F1 = {q4} e a função de transição é dada por:

δ1 a b c

q1 {q1, q2, q3} ∅ ∅q2 ∅ {q4} ∅q3 ∅ ∅ {q4}q4 ∅ ∅ ∅

(b) δ2 = δ1 e F2 = {q1, q2, q3}.(c) F3 = {q2} e a função de transição é dada por:

δ3 a b

q1 {q2} ∅q2 ∅ {q1, q3}q3 {q1, q3} ∅

2. Determine, usando o algoritmo descrito em aula, autômatos finitos não de-terminísticos que aceitem as linguagens cujas expressões regulares são da-das abaixo:(a) (10 ∪ 001 ∪ 010)∗;(b) (1 ∪ 0)∗00101;(c) ((0 · 0) ∪ (0 · 0 · 0))∗.

3. Converta cada um dos autômatos finitos não determinísticos obtidos no exer-cício anterior em um autômato finito determinístico.

4. Seja A um autômato finito determinístico com um único estado final. Con-sidere o autômato finito não determinístico A′ obtido invertendo os papéis

35

36 5. AUTÔMATOS FINITOS NÃO DETERMINÍSTICOS

dos estados inicial e final e invertendo também a direção de cada seta nodiagrama de estado. Descreva L(A′) em termos de L(A).

5. Seja Σ = {0, 1}. Seja L1 ⊂ Σ∗ a linguagem que consiste das palavras ondehá pelo menos duas ocorrências de 0, e L2 ⊂ Σ∗ a linguagem que consistedas palavras onde há pelo menos uma ocorrência de 1. Para cada uma daslinguagens L abaixo dê uma expressão regular para L e use os algoritmosdescritos em aula para criar um autômato finito não determinístico que aceitaL.(a) L = L1 ∪ L2;(b) L = Σ∗ \ L1;(c) L = L1 ∩ L2.

6. Sejam L e L′ linguagens regulares. Mostre que L \ L′ é regular

7. Sejam L e L′ linguagens tais que L é regular, L∪L′ é regular e L∩L′ = ∅.Mostre que L′ é regular.

8. Sejam M e M ′ autômatos finitos não determinísticos em um alfabeto Σ.Neste exercício discutimos uma maneira de definir um autômato finito nãodeterminístico N que aceita a concatenação L(M) ·L(M ′) diferente da quefoi vista em aula. Seja δ a função de transição de M . Para construir o grafode N a partir dos grafos de M e M ′ procedemos da seguinte maneira. Todavez que um estado q de M satisfaz

para algum σ ∈ Σ, o conjunto δ(q, σ) contém um estadofinal,

acrescentamos uma transição de q para o estado inicial de M ′, indexada porσ.(a) Descreva detalhadamente todos os ingredientes de N . Quem são os

estados finais de N?(b) Mostre que se ε /∈ L(M) então N aceita L(M) · L(M ′).(c) Se ε ∈ L(M) então pode ser necessário acrescentar mais uma transição

para que o autômato aceite L(M) · L(M ′). Que transição é esta?

9. Seja M um autômato finito determinístico no alfabeto Σ, com estado inicialq1, conjunto de estados Q e função de transição δ. Dizemos que M temreinício se existem q ∈ Q e σ ∈ Σ tais que

δ(q, σ) = q1.

Em outras palavras, no grafo de M há uma seta que aponta para q1. Mos-tre como é possível construir, a partir de um autômato finito determinís-tico M qualquer, um autômato finito determinístico M ′ sem reinício tal queL(M) = L(M ′).

10. SejamA eA′ autômatos finitos determinísticos com alfabeto Σ, conjunto deestados Q e Q′, estados iniciais q1 e q′1, conjuntos de estados finais F e F ′

e funções de transição δ e δ′. Seja M o autômato finito determinístico comalfabeto Σ, conjunto de estados Q1 × Q2, estado inicial (q1, q

′1), conjunto

5. AUTÔMATOS FINITOS NÃO DETERMINÍSTICOS 37

de estados finais F1 × F2 e função de transição dada por

δ((q, q′), σ) = (δ1(q, σ), δ2(q′, σ)),

onde q ∈ Q, q′ ∈ Q′ e σ ∈ Σ.(a) Mostre que L(M) = L(A) ∩ L(A′).(b) Use (a) para dar uma outra demonstração de que a interseção de lingua-

gens regulares é regular.(c) Use esta construção para obter um autômato finito determinístico que

aceita a linguagem L do exercício 6(c).

11. Seja L uma linguagem que é regular. Definimos o posto de L como sendo omenor inteiro positivo k para o qual existe um autômato finito determinísticoA com k estados e tal que L = L(A).(a) Se L1 e L2 são linguagens regulares cujos postos são k1 e k2 respecti-

vamente, determine m (em termos de k1 e k2) de modo que o posto deL1 · L2 seja menor ou igual a m.

(b) Considere a afirmação: se L1 ⊆ L2 são linguagens regulares entãoo posto de L1 tem que ser menor ou igual que o posto de L2. Estaafirmação é verdadeira ou falsa? Justifique sua resposta com cuidado!

CAPíTULO 6

Operações com autômatos finitos

No capítulo 3 vimos como obter a expressão regular da linguagem aceitapor um autômato finito. Agora, começamos a preparar o terreno para poder re-solver o problema inverso; isto é, dada uma expressão regular r em um alfabetoΣ, como construir um autômato finito M que aceita L(r)? Nossa estratégiaconsistirá em usar r como uma receita recursiva para construirM. Contudo, ré construída, a partir dos símbolos de Σ, por aplicações repetidas das operaçõesde união, concatenação e estrela. Assim, para poder usar r como uma receitapara construirM precisamos antes solucionar o seguinte problema:

dados autômatos finitosM eM′ em um alfabeto Σ cons-tuir autômatos finitos que aceitemL(M)∪L(M′), L(M)·L(M′) e L(M)∗.

É exatamente isto que faremos neste capítulo.

1. União

Suponhamos queM eM′ são autômatos finitos não determinísticos emum mesmo alfabeto Σ. Mais precisamente, digamos que

(1.1) M = (Σ, q1, Q, F, δ) e M′ = (Σ, q′1, Q′, F ′, δ′).

Assumiremos, também, que Q∩Q′ = ∅. Observe que esta hipótese não repre-senta nenhuma restrição expressiva, já que para alcançá-la basta renomear osestados deM′, no caso de serem denotados pelo mesmo nome que os estadosdeM.

Um outro detalhe que vale a pena mencionar é que, tanto nesta construção,como na da concatenação, estamos supondo que ambos os autômatos estãodefinidos para um mesmo alfabeto. Novamente, esta restrição é apenas apa-rente já que os autômatos não precisam ser determinísticos. De fato, podemosaumentar o alfabeto de entrada de um autômato não determinístico o quantoquisermos, sem alterar o seu comportamento. Para isso basta decretar que as

39

40 6. OPERAÇÕES COM AUTÔMATOS FINITOS

transições pelos novos estados são todas vazias. No caso da união, isto sig-nifica que, seM eM′ tiverem alfabetos de entrada Σ e Σ′ diferentes, entãopodemos considerar ambos como autômatos no alfabeto Σ ∪ Σ′. Para maisdetalhes veja o exercício 1.

Vejamos como deve ser o comportamento de um autômato finitoMu paraque aceite L(M) ∪ L(M′). O autômato Mu aceitará uma palavra w ∈ Σ∗

somente quando w for aceita por M ou por M′. Mas, para descobrir isto,Mu deve ser capaz de simular estes dois autômatos. Como estamos partindodo princípio de queMu é não determinístico, podemos deixá-lo escolher qualdos dois autômatos vai querer simular em uma dada computação. Portanto, aoreceber uma palavra w, o autômatoMu:

• escolhe se vai simularM ouM′;• executa a simulação escolhida e aceita w apenas se for aceita pelo

autômato cuja simulação está sendo executada.Uma maneira de realizar isto em um autômato finito é criar um novo estadoinicial q0 cuja única função é realizar a escolha de qual dos dois autômatos serásimulado. Mais uma vez, como Mu não é determinístico, podemos deixá-lodecidir, por si próprio, qual o autômato que será simulado.

Ainda assim, resta um problema. De fato, todos os símbolos de w serãonecessários para que as simulações deM eM′ funcionem corretamente. Con-tudo, nossos autômatos precisam consumir símbolos para efetuar suas transi-ções. Digamos, por exemplo, que ao receber w no estado q0 o autômatoMu

escolhe simularM com entrada w. Entretanto, para poder simularM em w,Mu precisa deixar q0 e chegar ao estado inicial q1 de M ainda tendo w porentrada, o que não é possível. Resolvemos este problema fazendo com queq0 comporte-se, simultaneamente, como q1 ou como q′1, dependendo de qualautômatoMu escolheu simular. Mais precisamente, seMu escolheu simularM, então q0 realiza a transição a partir do primeiro símbolo dew como se fosseuma transição deM a partir de q1 por este mesmo símbolo.

Para poder formalizar isto, digamos que w = σu, onde σ ∈ Σ e u ∈ Σ∗.Neste caso, seMu escolheu simularM, devemos ter que

(q0, w) ` (p, u) se, e somente se, p ∈ δ(q1, σ).

Podemos dissecar o comportamento deMu a partir de q0 como duas escolhassucessivas:

(1) primeiroMu decide se vai simularM ouM′;(2) a seguir,Mu escolhe qual a transição que vai ser executada por σ, a

partir de q1 ou q′1–dependendo da escolha feita em (1).Denotando por δu a função de transição deMu, podemos resumir isto escre-vendo

δu(q0, σ) = δ(q1, σ) ∪ δ′(q′1, σ).

O comportamento geral de Mu pode ser ilustrado em uma figura, comosegue. As transições que foram acrescentadas como parte da construção deMu aparecem tracejadas.

1. UNIÃO 41

• '&%$ !"#•/.-,()*+q1

77oooooooo

''OOOOOOOO M '&%$ !"#•• '&%$ !"#•

/.-,()*+q0

77oooooooooo

??��

��

��

��

��

��

''OOOOOOOOOO

##GG

GG

GG

GG

GG

G

��?

??

??

??

??

??

?

• '&%$ !"#•/.-,()*+q1

77oooooooo

''OOOOOOOO // • M′

• '&%$ !"#•

Como a figura sugere, os estados de Mu são os mesmos de M e M′,exceto por q0. Quanto aos estados finais, precisamos ser mais cuidadosos. Emprimeiro lugar, uma vez tendo passado por q0, o autômato Mu meramentesimulaM ouM′. Portanto, a descrição dos estados finais deMu só apresentaalgum problema se q1 ∈ F ou q′1 ∈ F ′. Por exemplo, se q1 for final, entãoM e, portanto,Mu, deverá aceitar ε. Mas isto só pode ocorrer se q0 for final.Portanto, q0 deverá ser declarado como final sempre que q1 ou q′1 forem finais.

Vamos formalizar a construção, listando os vários elementos deMu um aum:

Alfabeto: Σ;Estados: {q0} ∪Q ∪Q′;Estado inicial: q0;Estados finais:

{q0} ∪ F ∪ F ′ se q1 ∈ F ou q′1 ∈ F ′

F ∪ F ′ se q1 /∈ F e q′1 /∈ F ′

Função de transição:

δu(q, σ) =

δ(q1, σ) ∪ δ′(q′1, σ) se q = q0

δ(q, σ) se q ∈ Qδ′(q, σ) se q ∈ Q′


Vejamos como a construção se comporta em um exemplo. Considere oautômato finito determinísticoMpar, com grafo

I // GFED@ABC?>=<89:;q1

b

�� a++ GFED@ABCq2

b

��

akk

e o autômato finito não determinísticoMab cujo grafo é

I // GFED@ABCq′1a // GFED@ABCq′2

b // GFED@ABC?>=<89:;q′3

Já sabemos queM aceita a linguagem formada pelas palavras no alfa-beto {a, b} que têm uma quantidade par de as, e que L(M′) = {ab}.Aplicando a construção discutida acima para construir um autômatoMu que aceita L(M) ∪ L(M′), obtemos

GFED@ABC?>=<89:;q1

b


b

��

akk

I // GFED@ABC?>=<89:;q0a

::

b

EE

a

##GFED@ABCq′1a // GFED@ABCq′2

b // GFED@ABC?>=<89:;q′3

Há dois detalhes importantes a serem observados neste exemplo.O primeiro é que, como há uma seta de q1 nele próprio, indexada pora, você poderia esperar encontrar emMu uma seta de q0 nele própriocom o mesmo índice. No entanto, não é isto que acontece. De fato,denotando por δ a função de transição de M temos, pela definição deMu, que

δ(q1, b) = q1 implica q1 ∈ δu(q0, b).

Em outras palavras, a transição por b emM, que leva q1 nele próprio,dá lugar a uma transição por b de q0 em q1.

O segundo detalhe diz respeito à eliminação de estados redundantes.À primeira vista, como q0 passa a desempenhar o papel de estado inicial,em substituição a q1 e q′1, então estes últimos estados deveriam ter-setornado redundantes. Entretanto, embora q′1 seja, de fato, redundante,o mesmo não ocorre com q1. Por exemplo, o autômatoM retorna a q1

1. UNIÃO 43

durante a computação

(q1, a2) ` (q2, a) ` (q1, ε).

Simulando a mesma computação emMu, teremos

(q0, a2) ` (q2, a) ` (q1, ε).

Note que emboraMu parta de q0, na terceira etapa da computação elealcança q1, exatamente comoM. Assim, q0 substitui q1 apenas quandoeste último está desempenhando o papel de estado inicial.

Para esclarecer, de forma definitiva, todos os detalhes da construçãodeMu, provaremos formalmente que

L(Mu) = L(M) ∪ L(M′).Faremos isto no caso geral, admitindo queM eM′ são os autômatosnão determinísticos definidos em (1.1). Nossa demonstração consisteem provar que w ∈ Σ∗ é aceita porMu se, e somente se, for aceita porM ouM′. Se w = ε não há muito o que dizer, por isso deixamos estecaso aos seus cuidados. De agora em diante estaremos assumindo quew 6= ε. Com isso, podemos escrever w na forma

w = σu, onde σ ∈ Σ e u ∈ Σ∗.

Antes de prosseguir, convém enunciar claramente as propriedadesde Mu que serão utilizadas na demonstração. Em primeiro lugar, osestados e transições deM e deM′ correspondem um a um, aos estadose transições deMu, exceto por q0 e suas transições. Assim,

• toda computação emM pode ser reproduzida literalmente (querdizer, com os mesmos estados e transições) como uma compu-tação deMu;• reciprocamente, qualquer computação de Mu a partir de um

estado deM pode ser reproduzida literalmente emM.Naturalmente, as mesmas afirmações valem se substituímosM porM′.Em segundo lugar,

(1.2) se p ∈ δ(q1, σ) então p ∈ δu(q0, σ).

Digamos, primeiramente, quew ∈ L(M). Temos, então, uma com-putação

(q1, σu) ` (p, u) `∗ (f, ε),

onde p ∈ Q e f ∈ F . Mas, por (1.2),

se (q1, σu) ` (p, u) em M, então (q1, σu) ` (p, u) em Mu.

Por outro lado, da primeira propriedade acima, a computação (p, u) `∗(f, ε) em M pode ser reproduzida, passo a passo, e com os mesmos


estados e transições, como uma computação deMu. Obtemos, assim, acomputação

(q0, σu) ` (p, u) `∗ (f, ε),

emMu. Como f é final emM, ele também será final emMu, de modoque toda palavra aceita por M será aceita por Mu; isto é L(M) ⊆L(Mu). Um argumento análogo mostra que L(M′) ⊆ L(Mu).

Esta primeira parte do argumento pressupõe que todos os estadosnão redundantes de M e M′ sejam também estados de Mu. Mas háuma exceção a esta afirmação. Digamos, por exemplo, que q1 seja ina-cessível a partir de qualquer estado deM, inclusive dele próprio. Nestecaso, q1 vai se tornar redundante em Mu. Isto acontece porque umacomputação só pode passar por q1 uma vez e, mesmo assim, somente secomeçar deste estado, ao passo que as computações de Mu começamde q0. Este fenômeno ocorre, por exemplo, com o estado q′1 no exemplodescrito acima.

Suponha, agora, que

w = σu ∈ L(Mu).

Teremos, então, uma computação emMu da forma

(1.3) (q0, σu) ` (p, u) `∗ (f, ε),

onde f é um estado final de Mu. Pela definição das transições emMu devemos ter que p ∈ Q ou p ∈ Q′. Suporemos, sem perda degeneralidade, que p ∈ Q. Contudo, qualquer transição emMu a partirde um estado deM também é uma transição deM. Como p ∈ Q, istosignifica que

(p, u) `∗ (f, ε)

terá que corresponder, passo a passo, a uma computação em M. Por-tanto, usando (1.2), obtemos uma computação

(q1, σu) ` (p, u) `∗ (f, ε),

emM. Como fé um estado final deMu que pertence a Q, concluímosque f ∈ F . Logo, w é aceita porM.

Observe que a segunda parte da demonstração está ancorada no fatode nenhuma transição deMu poder chegar em q0. Se isto pudesse acon-tecer,Mu poderia executar parte da computação emM, retornar a q0, econtinuar com uma computação deM′. Entretanto, o argumento acimasó funciona porque, uma vez queMu tenha alcançado um estado deM,ele fica preso neste último autômato, e assim é obrigado a se comportarcomoM.

2. CONCATENAÇÃO 45

2. Concatenação

A segunda operação de linguagens que precisamos transcrever paraos autômatos é a concatenação. Suponhamos, mais uma vez, que temosdois autômatosM eM′ no mesmo alfabeto Σ, cujos elementos são

M = (Σ, q1, Q, F, δ) e M′ = (Σ, q′1, Q′, F ′, δ′).

Continuaremos assumindo que Q ∩Q′ = ∅.Nosso objetivo é construir um autômatoMc que aceite a concate-

nação L(M) · L(M′). Assim, dada uma palavra w ∈ Σ∗, o autômatoMc precisa verificar se existe um prefixo de w que é aceito por M eque é seguido de um sufixo aceito por M′. Naturalmente isto sugereconectar os autômatos M e M′ ‘em série’; quer dizer, um depois dooutro. Além disso, para que o prefixo esteja em L(M) o último estadodeM alcançado em uma computação por w deve ser final. Finalmente,é mais fácil construir um modelo não determinístico deMc, já que nãotemos como saber exatamente onde acaba o prefixo de w que pertence aL(M).

Nossa experiência com a união deixa claro que não adianta conec-tar os autômatos através de transições de um estado final de M parao estado inicial deM′. Isto só seria possível se nossos autômatos pu-dessem efetuar transições sem consumir nenhum símbolo da entrada.Contornamos o problema, como fizemos no caso da união, construindoas transições diretamente dos estados finais de M para os sucessoresdo estado inicial deM′. Podemos ilustrar a construção em uma figura,como segue.

• '&%$ !"#◦ ,,d b a _ ] \ Z

++

MO

QR

TU W

• '&%$ !"#•76540123q1

77ooooooooo

''OOOOOOOOO // • M ?>=<89:;q′1

77ooooooooo

''OOOOOOOOO M′ '&%$ !"#•• '&%$ !"#◦ 22Z \ ] _ a b d

33

qo

nl

ji g

• '&%$ !"#•

As setas correspondentes às transições entre os autômatosM eM′foram tracejadas para dar maior clareza à figura. Observe também queos estados que seriam finais em M aparecem com a bolinha centralvazada (◦ em vez de •). Fizemos isto porque nem sempre um estadofinal deM continuará final emMc. Na verdade, se todo estado em Ffor final emMc então toda computação emM que acabar em F será


aceita por Mc. Quer dizer, toda palavra em L(M) também pertencea L(Mc) = L(M) · L(M′). Entretanto, isto só pode acontecer seε ∈ L(M′); ou, o que é equivalente, se q′1 é estado final deM′. Casocontrário, apenas os estados finais deM′ serão finais emM.

Formalizaremos a construção, listando os vários elementos deMc

um a um:Alfabeto: Σ;Estados: Q ∪Q′;Estado inicial: q1;Estados finais:

F ∪ F ′ se q′1 ∈ F ′

F ′ se q′1 /∈ F ′


δc(q, σ) =

δ(q, σ) se q ∈ Q \ Fδ(q, σ) ∪ δ′(q′1, σ) se q ∈ Fδ′(q, σ) se q ∈ Q′

A demonstração de que esta construção funciona corretamente ébastante simples e segue a linha da demonstração para a união dadana seção anterior, por isso vamos omiti-la. Vejamos como a construçãose comporta quando é aplicada aos autômatos utilizados no exemplo daseção 1. Começaremos concatenandoMpar comMab:

GFED@ABCq1

b

�� a++

a

55

GFED@ABCq2

b

��

akk

GFED@ABCq′1a // GFED@ABCq′2

b // GFED@ABC?>=<89:;q′3

Observe que o estado q1 deixou de ser final nesta concatenação,porque q′1 não é estado final deMab. Por outro lado, se concatenarmosMab com Mpar, então q′3 continuará sendo final, já que q1 é final emMpar. O grafo do autômato resultante desta concatenação é o seguinte:

GFED@ABCq′1a // GFED@ABCq′2

b // GFED@ABC?>=<89:;q′3b //

a>>

GFED@ABC?>=<89:;q1

b


b

��

akk

3. ESTRELA 47

Neste caso temos duas transições a partir do estado final de Mab,porque q1 tem como sucessores q2 e o próprio q1.

3. Estrela

Tendo mostrado como construir um autômato para a concatenação,não parece tão difícil lidar com a estrela. Afinal, se L é uma linguagem,então L∗ é obtida concatenando L com ela própria mais e mais vezes;isto é, calculando a união das Lj , para todo j ≥ 0. Portanto, uma ma-neira de realizar um autômatoM, que aceite L, consistiria em conectara saída deM com sua entrada. Com isso a concatenação passaria infini-tas vezes pelo próprioM, e teríamos um novo autômatoM∗ que aceitaL∗. Vamos testar esta idéia em um exemplo e ver o que acontece.

Considere o autômato finitoN no alfabeto {a, b}, cujo grafo é dadopor

GFED@ABCq1a // GFED@ABCq2

b

~~}}}}}}}}}

GFED@ABC?>=<89:;q3

a

ÀAAAAAAAA

A linguagem aceita por N é denotada pela expressão regular (aba)∗ab,como é fácil de ver.

Para concatenarN com ele próprio precisamos criar transições entreseus estados finais e os sucessores do estado inicial. Neste exemplo, háapenas o estado final q3, e q1 tem apenas um sucessor; a saber, o estadoq2 que é acessível a partir de q1 por a. Por isso precisamos criar umanova transição de q3 para q2 por a, obtendo o seguinte autômato


bxxGFED@ABC?>=<89:;q3

a88

�}

sa

ÀAAAAAAAA

A transição acrescentada foi desenhada tracejada para que possa sermais facilmente identificada.

Infelizmente, não pode ser verdade que este autômato aceitaL(N )∗.Afinal, ε pertence a L(N )∗ e não é aceito pelo autômato que acabamosde construir. A essa altura, sua reação pode ser:

“Não seja por isso! Para resolver este problema bastamarcar q1 como sendo estado final do novo autômato.”


Vamos fazer isto e ver o que acontece. O grafo do autômato passaria aser o seguinte:

GFED@ABC?>=<89:;q1a // GFED@ABCq2


a88

�}

sa

ÀAAAAAAAA

Contudo, este autômato aceita a palavra aba que não pertence a

L(N )∗ = ((aba)∗ab)∗.

O problema não está em nossa idéia original de concatenar um autô-mato com ele próprio, mas sim na emenda que adotamos para resolvero problema de fazer o novo autômato aceitar ε. Ao declarar q1 comosendo estado final, não levamos em conta que o autômato admite transi-ções que retornam ao estado q1. Isto fez com que outras palavras, alémde ε, passassem a ser aceitas pelo novo autômato. Mas não é isso quequeremos. A construção original funcionava perfeitamente, exceto por-que ε não era aceita. Uma maneira simples de contornar o problema éinspirar-se na união, e criar um novo estado q0 para fazer o papel de es-tado inicial. Este estado vai comportar-se como q1, e também será final.Entretanto, como no caso da união, as transições por q0 são exatamenteas mesmas que as transições por q1. Em particular, nenhuma transiçãodo novo autômato aponta para q0. Isto garante que a introdução de q0leva à aceitação de apenas uma nova palavra, que é ε. Esboçamos abaixoo grafo do autômato resultante desta construção, no exemplo que vimosconsiderando.

GFED@ABC?>=<89:;q0a

$$

V T R PN

K



a88

�}

sa

ÀAAAAAAAA

Em geral, quando é dado um autômato

M = (Σ, q1, Q, F, δ)

podemos construir um autômatoM∗ que aceita L(M∗) segundo o mo-delo estabelecido no exemplo anterior. Como no caso da união e da con-catenação, podemos ilustrar o autômatoM∗ em uma figura nas quais as

3. ESTRELA 49

novas transições aparecem tracejadas.

• '&%$ !"#•BCED�

��

GF_ _ _ _ _ _ _

@A��

76540123'&%$ !"#q0//

n l i g e c a

//

P R U W Y [ ]

76540123q1

77ooooooo

''OOOOOOO M

• '&%$ !"#• EDBC�

��

@A_ _ _ _ _ _ _

GF��

Formalizaremos a construção, listando os vários elementos deM∗,como segue:

Alfabeto: Σ;Estados: {q0} ∪Q;Estado inicial: q0;Estados finais: F ∪ {q0}Função de transição:

δ∗(q, σ) =

δ(q1, σ) se q = q0

δ(q, σ) se q ∈ Q \ Fδ(q, σ) ∪ δ(q1, σ) se q ∈ F

Encerramos a seção com a demonstração de que esta construçãofunciona corretamente. Em primeiro lugar, como ε é aceita por constru-ção, podemos limitar nossa discussão a uma palavra w 6= ε que pertençaa Σ∗.

Como em nossa discussão do autômato que aceita a união de lin-guagens, isolaremos duas propriedades da definição de M∗ que serãoutilizadas na demonstração. Em primeiro lugar, se (q1, σ) ` (p, ε) emM, então existirão transições emM∗ da forma

(q0, σ) ` (p, ε),

e, também, da forma

(f, σ) ` (p, ε) para cada estado final f de M.

Que q0 comporta-se como se fosse q1 é óbvio da maneira como suastransições foram definidas. Já a segunda parte da afirmação segue dofato de que também fizemos cada estado final deM∗ comportar-se comose fosse q1 ao concatenarM com ele próprio. Outro ponto importante éque toda computação emM pode ser simulada porM∗ com os mesmos


estados e transições, já queM foi inteiramente preservado “dentro” deM∗.

Seja L = L(M). Como sempre, temos que provar que toda pa-lavra que pertence a L∗ é aceita por M∗, e vice-versa. Começaremosmostrando L∗ ⊆ L(M∗). Digamos que w ∈ L∗. Neste caso, podemosescrever w na forma

w = w1w2 · · ·wk onde w1, w2, . . . , wk ∈ L.

Digamos que wj = σjuj , com σj ∈ Σ e uj ∈ Σ∗. Como cada wjpertence a L, tem que existir uma computação

(q1, wj) ` (pj , uj) `∗ (fj , ε),

onde pj ∈ Q e fj ∈ F . Mas o estado inicial q0 de M∗ simula ocomportamento de q1, e M∗ é capaz de simular qualquer computaçãoemM. Portanto, podemos construir uma computação emM∗ da forma:

(q0, σ1u1w2 · · ·wk) ` (p1, u1w2 · · ·wk) `∗ (f1, w2 · · ·wk).

Por outro lado, também podemos construir computações da forma

(fj , wj+1 · · ·wk) = (fj , σj+1uj+1 · · ·wk) ` (pj+1, uj+1 · · ·wk)`∗ (fj+1, wj+2 · · ·wk),

para todo 1 ≤ j < k. Emendando o início de cada uma dessas compu-tações ao final da outra, obtemos

(q0, w1w2 · · ·wk) `∗ (f1, w2 · · ·wk) `∗ (f2, w3 · · ·wk) · · · `∗ (fk−1, wk)

`∗ (fk, ε),

provando, assim, queM∗ aceita w.

Passamos, agora, a mostrar que L(M∗) ⊆ L∗. Para facilitar a dis-cussão, distinguiremos dois tipos de transição emM∗:

Primeiro tipo: as transições a partir de q0, além de todas aquelasque já eram transições deM;

Segundo tipo: transições queM∗ faz a partir dos estados finaisdeM, como se fossem q1.

Suponha, agora, que w é aceita porM∗. Neste caso existe uma compu-tação

(q0, w) ` ∗(f, ε),emM∗. Percorrendo, agora, esta computação, vamos dividi-la em par-tes de modo que a primeira transição de cada segmento, a partir do se-gundo, seja uma transição do segundo tipo. Se wj for a subpalavra de

4. EXERCíCIOS 51

w consumida ao longo do j-ésimo segmento, podemos escrever os seg-mentos na forma

(q0, w) `∗ (f1, w2 · · ·wk)(f1, w2 · · ·wk) `∗ (f2, w3 · · ·wk)

...

(fk−1, wk) `∗ (fk, ε),

onde f1, . . . , fk ∈ F . Além disso, se wj = σjuj , com σj ∈ Σ euj ∈ Σ∗, então a transição do segundo tipo pode ser isolada em cadasegmento

(fj , wjwj+1 · · ·wk) = (fj , σjujwj+1 · · ·wk) ` (pj , ujwj+1 · · ·wk)`∗ (fj+1, wj+1 · · ·wk),

para todo 1 ≤ j < k, onde pj ∈ Q. Temos, assim, computações daforma

(fj , wj) = (fj , σjuj) ` (pj , uj) `∗ (fj+1, ε),

emM∗, que por sua vez dão lugar a computações da forma

(q1, wj) = (fj , σjuj) ` (pj , uj) `∗ (fj+1, ε),

emM. Portanto, w2, . . . , wk ∈ L. Um argumento semelhante mostraque w1 ∈ L, e nos permite concluir que

w = w1w2 · · ·wk ∈ L∗,como nos faltava mostrar.

4. Exercícios

1. Sejam Σ ⊂ Σ′ dois alfabetos. Suponha que M é um autômato fi-nito não determinístico no alfabeto Σ. Construa formalmente umautômato finito não determinísticoM′ no alfabeto Σ′, de modo queL(M) = L(M′). Prove que sua construção funciona corretamente.SUGESTÃO: Defina todas as transições deM′ por símbolos de Σ′ \Σcomo sendo vazias.

2. Seja Σ = {0, 1}. Suponha que L1 ⊂ Σ∗ é a linguagem que consistedas palavras onde há pelo menos duas ocorrências de 0, e que L2 ⊂Σ∗ é a linguagem que consiste das palavras onde há pelo menos umaocorrência de 1.(a) Construa autômatos finitos não determinísticos que aceitem L1 e

L2.(b) Use os algortimos desta seção para criar autômatos finitos não

determinísticos que aceitem L1 ∪ L2, L1 · L2, L∗1 e L∗2.


3. Sejam M e M ′ autômatos finitos não determinísticos em um alfabetoΣ. Neste exercício discutimos uma maneira de definir um autômatofinito não determinísticoN , que aceita a concatenaçãoL(M)·L(M ′),e que é diferente do que foi vista na seção 2. Seja δ a função detransição de M . Para construir o grafo de N a partir dos grafos de Me M ′ procedemos da seguinte maneira. Toda vez que um estado q deM satisfaz

para algum σ ∈ Σ, o conjunto δ(q, σ) contém umestado final,

acrescentamos uma transição de q para o estado inicial de M ′, inde-xada por σ.(a) Descreva detalhadamente todos os elementos de N . Quem são

os estados finais de N?(b) Mostre que se ε /∈ L(M) então N aceita L(M) · L(M ′).(c) Se ε ∈ L(M) então pode ser necessário acrescentar mais uma

transição para que o autômato aceite L(M) ·L(M ′). Que transi-ção é esta?

4. Seja M um autômato finito determinístico no alfabeto Σ, com estadoinicial q1, conjunto de estados Q e função de transição δ. Dizemosque M tem reinício se existem q ∈ Q e σ ∈ Σ tais que

δ(q, σ) = q1.

Em outras palavras, no grafo de M há uma seta que aponta para q1.Mostre como é possível construir, a partir de um autômato finito de-terminístico M qualquer, um autômato finito determinístico M ′ semreinício tal que L(M) = L(M ′).

5. Sejam M e M ′ autômatos finitos determinísticos no alfabeto Σ cujoselementos são (Σ, Q, q1, F, δ) e (Σ, Q′, q′1, F

′, δ′), respectivamente.Defina um novo autômato finito determinístico N construído a partirde M e M ′ como segue:

Alfabeto: Σ;Estados: pares (q, q′) onde q ∈ Q e q′ ∈ Q′;Estado inicial: (q1, q

′1);

Estados finais: pares (q, q′) onde q ∈ F ou q′ ∈ F ′;Transição: a função de transição é definida em um estado (q, q′)

de N e símbolo σ ∈ Σ por

δ((q, q′), σ) = (p, p′),

onde p = δ(q, σ) e p′ = δ′(q′, σ).Calcule L(N) em função de L(M) e L(M ′) e prove que a sua res-posta está correta.

CAPíTULO 7

Autômatos de expressões regulares

No capítulo ?? vimos como obter a expressão regular da linguagemaceita por um autômato finito. Neste capítulo, resolvemos o problemainverso; isto é, dada uma expressão regular r em um alfabeto Σ, cons-truímos um autômato finito que aceita L(r). Na verdade, o autômatoque resultará de nossa construção não será determinístico. Mas isto nãoé um problema, já que sabemos como convertê-lo em um autômato de-terminístico usando a construção de subconjuntos.

1. Considerações gerais

Seja r uma expressão regular r no alfabeto Σ. Nossa estratégiaconsistirá em utilizar a expressão regular r como uma receita para aconstrução de um autômato finito não determinísticoM(r) que aceitaL(r). Entretanto, como vimos no capítulo ??, r é definida, de maneirarecursiva, a partir dos símbolos de Σ, ε e ∅, por aplicação sucessivadas operações de união, concatenação e estrela. Por isso, efetuaremos aconstrução deM(r) passo à passo, a partir dos autômatos que aceitamos símbolos de Σ, ε e ∅.

Contudo, para que isto seja possível, precisamos antes de resolveralguns problemas. O primeiro, e mais simples, consiste em construirautômatos finitos que aceitem um símbolos de Σ, ou ε ou ∅. Estes autô-matos funcionarão como os átomos da construção. Os problemas maisinteressantes dizem respeito à construção de novos autômatos a partir deautômatos já existentes. Suponhamos, então, queM1 eM2 são autô-matos finitos não determinísticos. Precisamos saber construir

(1) um autômatoMu que aceita L(M1) ∪ L(M2);(2) um autômatoMc que aceita L(M1) · L(M2); e(3) um autômatoM1∗ que aceita L(M1)

∗.

53

54 7. AUTÔMATOS DE EXPRESSÕES REGULARES

Se formos capazes de inventar maneiras de construir todos estes autô-matos, então seremos capazes de reproduzir a montagem de r passo àpasso no domínio dos autômatos finitos, o que nos levará a um autômatofinito que aceita L(r), como desejamos.

Começaremos descrevendo os átomos desta construção; isto é, osautômatos que aceitam símbolos de Σ, ε e ∅. Seja σ ∈ Σ. Um autômatosimples que aceita σ é dado pelo grafo

I // GFED@ABCq1σ

// GFED@ABC?>=<89:;q2

O autômato que aceita ε é ainda mais simples

I // GFED@ABC?>=<89:;q1

Para obter o que aceita ∅ basta não declarar nenhum estado como sendofinal. A maneira mais simples de fazer isto é alterar o autômato acima,como segue.

I // GFED@ABCq1

Construídos os átomos, falta-nos determinar como podem ser conecta-dos para obter estruturas maiores e mais complicadas. Passamos, assim,à solução dos problemas enunciados acima.

2. União

Suponhamos queM eM′ são autômatos finitos não determinísticosem um mesmo alfabeto Σ. Mais precisamente, digamos que

M = (Σ, q1, Q, F, δ) e M′ = (Σ, q′1, Q′, F ′, δ′).

Suporemos, também, que Q ∩ Q′ = ∅. Isto não representa nenhumarestrição expressiva. Significa, no máximo, que pode ser necessário re-nomear os estados deM′ caso sejam denotados pelo mesmo nome queos estados deM.

Vejamos como deve ser o comportamento de um autômato finitoMu para que aceite L(M) ∪ L(M′). Dada uma palavra w ∈ Σ∗ aMu ele deve aceitá-la apenas se w for aceita porM ou porM′. Mas,para descobrir isto,Mu deve ser capaz de simular estes dois autômatos.Como estamos partindo do princípio queMu é não determinístico, po-demos deixá-lo escolher qual dos dois autômatos ele vai querer simular

2. UNIÃO 55

em uma dada computação. Portanto, dada uma palavra w a Mu, eleexecuta a seguinte estratégia:

• escolhe se vai simularM ouM′;• executa a simulaç ao escolhida e aceita w apenas se for aceita

pelo autômato cuja simulação está sendo executada.

Uma maneira de realizar isto em um autômato finito é criar um novoestado inicial q0 cuja única função é realizar a escolha de qual dos doisautômatos será simulado. Mais uma vez, comoMu não é determinís-tico, podemos deixá-lo decidir, por si próprio, qual o autômato que serásimulado.

Ainda assim, resta um problema. De fato, todos os símbolos de wserão necessários para que as simulações deM eM′ funcionem corre-tamente. Contudo, nossos autômato precisam consumir símbolos parase mover. Digamos, por exemplo, que ao receber w no estado q0 o autô-mato Mu escolhe simular M com entrada w. Entretanto, para podersimularM em w,Mu precisa deixar q0 e chegar ao estado inicial q1 deM ainda tendo w por entrada, o que não é possível. Resolvemos esteproblema fazendo com que q0 comporte-se, simultaneamente, como q1ou como q′1, dependendo de qual autômatoMu escolheu simular. Maisprecisamente, seMu escolheu simularM, então q0 realiza a transiçãoa partir do primeiro símbolo de w como se fosse uma transição deM apartir de q1 por este mesmo símbolo.

Para poder formular isto formalmente, digamos que w = σu, ondeσ ∈ Σ e u ∈ Σ∗. Neste caso, seMu escolheu simularM, devemos terque

(q0, w) ` (p, u) se, e somente se, p ∈ δ(q1, σ).

Podemos dissecar o comportamento de Mu a partir de q0 como duasescolhas sucessivas:

(1) primeiroMu decide se vai simularM ouM′;(2) a seguir,Mu escolhe qual a transição que vai ser executada por

σ, a partir de q1 ou q′1–dependendo da escolha feita em (1).

Denotando por δu a função de transição deMu, podemos resumir istoescrevendo

δu(q0, σ) = δ(q1, σ) ∪ δ′(q′1, σ).

O comportamento geral de Mu pode ser ilustrado em uma figura,como segue.

56 7. AUTÔMATOS DE EXPRESSÕES REGULARES

• '&%$ !"#•76540123q1

77ooooooooo

''OOOOOOOOO M '&%$ !"#•• '&%$ !"#•

76540123q0

77oooooooooooooooooooo

??��

''OOOOOOOOOOOOOOOOOOOO

##GGGGGGGGGGGGGGGGGGGGGG

��??????????????????????????

• '&%$ !"#•76540123q1

77ooooooooo

''OOOOOOOOO // • M′

• '&%$ !"#•

Como a figura sugere, a parte q0, os estados deMu são os mesmosdeM eM′. Quanto aos estados finais, precisamos ser mais cuidado-sos. Como, uma vez tendo passado por q0, o autômatoMu meramentesimulaM ouM′, só pode haver algum problema se um dos estados q1ou q′1 for final. Por exemplo, se q1 for final, entãoM e, portanto,Mu,deverá aceitar ε. Mas isto só pode ocorrer se q0 for final. Portanto, q0deverá ser declarado como final sempre que q1 ou q′1 forem finais.

Vamos formalizar a construção deMu antes de fazer um exemplo.Listando os vários elementos deMu um a um temos

Alfabeto: Σ;Estados: {q0} ∪Q ∪Q′;Estado inicial: q0;Estados finais:

{q0} ∪ F ∪ F ′ se q1 ∈ F ou q′1 ∈ F ′

F ∪ F ′ se q1 /∈ F e q′1 /∈ F ′

2. UNIÃO 57


δu(q, σ) =

δ(q1, σ) ∪ δ′(q′1, σ) se q = q0

δ(q, σ) se q ∈ Qδ′(q, σ) se q ∈ Q′

Vejamos como a construção se comporta em um exemplo. Consi-dere os autômatos finitosM eM′ cujos grafos são, respectivamente

I // GFED@ABC?>=<89:;q1

b


b

akk e I // GFED@ABCp1

a // GFED@ABCp2b // GFED@ABC?>=<89:;p3

CAPíTULO 8

Gramáticas lineares à direita

Neste capítulo começamos o estudo das gramáticas formais, queserão introduzidas a partir da noção de autômato finito.

1. Exercícios

1. Determine gramáticas lineares à direita que gerem as linguagens de-notadas pelas seguintes expressões regulares:(a) (0∗ · 1) ∪ 0;(b) (0∗ · 1) ∪ (1∗ · 0);(c) ((0∗ · 1) ∪ (1∗ · 0))∗.

2. Ache a expressão regular que denota a linguagem regular gerada pelagramática com variáveis S,A,B, terminais a, b, símbolo inicial S eregras:

S → bA | aB | ε

A→ abaS

B → babS.

3. Ache uma gramática linear à direita que gere a seguinte linguagem

{w ∈ {0, 1}∗ : w não contém a seqüência aa}.

4. Ache gramáticas lineares à direita que gerem cada uma das lingua-gens regulares do exercício 2 da 2a lista de exercícios.

5. Ache autômatos finitos que aceitem as linguagens geradas pelas gra-máticas lineares à direita no alfabeto {0, 1} e símbolo inicial S, comas seguintes regras:(a) S → 011X , S → 11S, X → 101Y , Y → 111.(b) S → 0X , X → 1101Y , X → 11X , Y → 11Y , X → 1.

59

60 8. GRAMÁTICAS LINEARES À DIREITA

6. Seja L uma linguagem regular no alfabeto Σ. Mostre que L \ {ε}pode ser gerada por uma gramática linear à direita cujas regras sãodos tipos• X → σY ou• X → σ,

onde X,Y são variáveis e σ é um símbolo de Σ.

CAPíTULO 9

Linguagens livres de contexto

Neste capítulo começamos a estudar uma classe de gramáticas fun-damental na descrição das linguagens de programação: as gramáticaslivres de contexto. 1

1. Gramáticas e linguagens livres de contexto

Já vimos no capítulo anterior que uma gramática é descrita pelosseguintes ingredientes: terminais, variáveis, símbolo inicial e regras.É claro que, em última análise, quando pensamos em uma gramáticao que nos vem a cabeça são suas regras; os outros ingredientes são,de certo modo, circunstanciais. Assim, o que diferencia uma classe degramáticas da outra é o tipo de regras que nos é permitido escrever. Nocaso de gramáticas lineares à direita, as regras são extremamente rígidas:uma variável só pode ser levada na concatenação de uma palavra nosterminais com alguma variável, além disso a variável tem que estar àdireita dos terminais.

Já as linguagens livres de contexto, que estaremos estudando nestecapítulo, admitem regras muito mais flexíveis. De fato a única restriçãoé que à esquerda da seta só pode aparecer uma variável. Talvez vocêesteja se perguntando: mas o que mais poderia aparecer à esquerda de

1Agradeço ao David Boechat pelas correções a uma versão anterior deste capítulo

61

62 9. LINGUAGENS LIVRES DE CONTEXTO

uma seta? Voltaremos a esta questão na seção 2, depois de considerarvários exemplos de linguagens que são livres de contexto. Mas antes dosexemplos precisamos dar uma definição formal do que é uma gramáticalivre de contexto.

Seja G uma gramática com conjunto de terminais T , conjunto de va-riáveis V e símbolo inicial S ∈ V . Dizemos que G é livre de contexto setodas as suas regras são do tipo X → w, onde X ∈ V e w ∈ (T ∪ V )∗.

Observe que as regras de uma gramática linear à direita são destetipo. Portanto, toda gramática linear à direita é livre de contexto. Poroutro lado, é evidente que nem toda gramática livre de contexto é linearà direita. Um exemplo simples é dado pela gramática G1 com terminaisT = {0, 1}, variáveis V = {S}, símbolo inicial S e conjunto de regras

{S → 0S1, S → ε}.

Como do lado esquerdo de cada seta só há uma variável, G1 é livre decontexto. Contudo, G1 não é linear à direita porque S → 0S1 tem umterminal à direita de uma variável.

Outro exemplo simples é a gramática G2 com terminais T = {0, 1},variáveis V = {S,X}, símbolo inicial S e conjunto de regras

{S → X1X,X → 0X, X → ε}.

Mais uma vez, apesar de ser claramente livre de contexto, esta gramáticanão é linear à direita, por causa da regra S → X1X .

Os dois exemplos construídos acima estão relacionados a lingua-gens que são velhas conhecidas nossas. Entretanto, para constatar istoprecisamos entender como é possível construir uma linguagem a partirde uma gramática livre de contexto. Isto se faz de maneira análoga aoque já ocorria com linguagens lineares à direita.

Seja G uma gramática livre de contexto com terminais T , variáveisV , símbolo inicial S e conjuntoR de regras, e sejam w,w′ ∈ (T ∪ V)∗.Dizemos que w′ pode ser derivada em um passo a partir de w em G, eescrevemos w ⇒G w′, se w′ pode ser obtida a partir de w substituindo-se uma variável que aparece em w pelo lado direito de alguma regra dagramática G. Em outras palavras, para que w ⇒G w′ é preciso que:

• exista uma decomposição da forma w = uXv, onde u, v ∈(T ∪ V) e X ∈ V , e• exista uma regra X → α emR tal que w′ = uαv.

Como já estamos acostumados a fazer, dispensaremos o G subscrito nanotação acima quando não houver dúvidas quanto à gramática que estásendo considerada (isto é, quase sempre!).

1. GRAMÁTICAS E LINGUAGENS LIVRES DE CONTEXTO 63

Como já ocorria com as gramáticas lineares à direita, estaremos ge-rando palavras a partir de uma gramática livre de contexto pelo encade-amento de várias derivações de um passo. Assim, dizer que w′ pode serderivada a partir de w em G em n passos significa que existem palavrasw1, . . . , wn−1 ∈ (T ∪ V)∗ tais que

w = w0 ⇒ w1 ⇒ · · · ⇒ wn−1 ⇒ wn = w′

Chamamos a isto uma derivação de w′ a partir de w em G e escrevemosw ⇒n w′. Caso não seja conveniente indicar o número de passos daderivação substituímos o n por uma ∗ como já estamos acostumadosa fazer. É conveniente também adotar a convenção de que w pode serderivada dela própria em zero passos, de modo que faz sentido escreverw ⇒∗ w.

O conjunto de todas as palavras de T ∗ que podem ser derivadas apartir do símbolo inicial S na gramática G é a linguagem gerada por G.Denotando L(G) a linguagem gerada por G, e usando a notação definidaacima, temos que

L(G) = {w ∈ T ∗ : existe uma derivação S ⇒∗ w em G}.

Vejamos alguns exemplos. Seja G1 a gramática definida acima. Te-mos que

S ⇒ 0S1⇒ 02S12 ⇒ 0212.

Note que S ⇒ 0S1 e 0S1 ⇒ 02S12 são derivações de um passo emG1 porque, em ambos os casos a palavra à direita de ⇒ foi obtida daque está à esquerda trocando-se S por 0S1. Isto é permitido porqueS → 0S1 é uma regra de G1. Já 02S12 ⇒ 0212 foi obtida trocando-seS por ε. Podemos fazer isto por que S → ε também é uma regra de G1.Toda esta cadeia de derivações pode ser abreviada como

S ⇒3 0211 ou S ⇒∗ 0211.

Por outro lado, 02S12 ⇒ 0213 não é uma derivação legítima em G1porque neste caso a regra usada foi S → 1, que não pertence a G1.

Do que fizemos acima segue que 0212 ∈ L(G1). Mas podemos sermuito mais ambiciosos e tentar determinar todas as palavras de L(G1).Para começar, note que se S ⇒n w em G1 e w /∈ T ∗, então w = 0nS1n.Para provar isto basta usar indução em n. Por outro lado, como a únicaregra de G1 que permite eliminar a variável S é S → ε, concluímos quetoda palavra derivada a partir de S em G1 é da forma 0n1n, para alguminteiro n ≥ 0. Assim,

L(G1) = {0n1n : n ≥ 0}.


Já vimos no capítulo 4, que esta linguagem não é regular. Em particular,não existe nenhuma gramática linear à direita que gere L(G1).

Passando à gramática G2, temos a derivação

S ⇒ X1X ⇒ 0X1X ⇒ 02X1X ⇒ 02X1⇒ 021.

Note que, na derivação acima, algumas ocorrências da variávelX foramsublinhadas. Fizemos isto para indicar à qual instância da variávelX foiaplicada a regra da gramática que leva ao passo seguinte da derivação.Assim, no segundo passo da derivação, aplicamos a regra X → 0Xao X mais à esquerda X1X . Com isto este X foi trocado por 0X ,mas nada foi feito ao segundo X . Coisa semelhante ocorreu no passoseguinte. Além disso, a regra X → 0X nunca foi aplicada ao segundoX . Fica claro deste exemplo que:

A cada passo de uma derivação apenas uma ocorrên-cia de uma variável pode ser substituída pelo lado di-reito de uma seta. Além disso, cada ocorrência deuma variável é tratada independentemente da outra.

Sempre que for conveniente, sublinharemos a instância da variável àqual a regra está sendo aplicada em um determinado passo da derivação.

Vamos tentar, também neste caso, determinar todas as palavras quepodem ser derivadas a partir de S em G2. Suponhamos que S ⇒∗ w emG2. É fácil ver que em w

• há um único 1;• pode haver, no máximo, duas ocorrências de X , uma de cada

lado do 1.Assim, w pode ser de uma das seguintes formas

0nX10mX ou 0n10mX ou 0nX10m ou 0n10m

Portanto, se w ∈ T ∗ e S ⇒∗ w, então w = 0n10m, para inteirosm,n ≥ 0. Concluímos que

L(G2) = {0n10m : n,m ≥ 0}.Mas esta é, na verdade, uma linguagem regular, que pode ser descrita naforma L(G2) = 0∗10∗. Temos assim um exemplo de gramática livre decontexto que não é linear à direita mas que gera uma linguagem regular.

Voltando ao caso geral, seja L uma linguagem no alfabeto Σ. Dize-mos que L é livre de contexto se existe pelo menos uma gramática livrede contexto G, com conjunto de terminais Σ, tal que L(G) = L.

Portanto, toda linguagem regular é livre de contexto. Isto ocorreporque, pelo teorema de Kleene, uma linguagem regular sempre podeser gerada por uma gramática linear à direita. Mas, como já vimos, todagramática linear à direita é livre de contexto.

2. LINGUAGENS SENSíVEIS AO CONTEXTO 65

Por outro lado, nem toda linguagem livre de contexto é regular. Porexemplo, vimos na seção 3 do capítulo 4 que a linguagem {0n1n : n ≥0} não é regular. No entanto, ela é gerada pela gramática G1 e, portanto,é livre de contexto. Na seção 3 veremos mais exemplos de linguagenslivres de contexto, incluindo várias que não são regulares.

Antes que você comece a alimentar falsas esperanças, é bom es-clarecer que existem linguagens que não são livres de contexto. Paramostrar, diretamente da definição, que uma linguagem L não é livre decontexto seria necessário provar que não existe nenhuma gramática li-vre de contexto que gere L, o que não parece possível. Como no casode linguagens regulares, a estratégia mais prática consiste em mostrarque há uma propriedade de toda linguagem livre de contexto que não ésatisfeita por L. Veremos como fazer isto no capítulo 11.

2. Linguagens sensíveis ao contexto

É hora de voltar à questão de como seria uma gramática que não élivre de contexto.

Lembre-se que o que caracteriza as gramáticas livres de contexto éo fato de que todas as suas regras têm apenas uma variável (e nenhumterminal) do lado esquerdo da seta. Na prática isto significa que sempreque X aparece em uma palavra, ele pode ser trocado por w, desde queX → w seja uma regra da gramática.

Para uma gramática não ser livre de contexto basta que, do lado es-querdo da seta de alguma de suas regras, apareça algo mais complicadoque uma variável isolada. Um exemplo simples, mas importante, é agramática com terminais {a, b, c}, variáveis {S,X, Y }, símbolo inicialS e regras

S → abc

S → aXbc

Xb→ bX

Xc→ Y bc2

bY → Y b

aY → a2

aY → a2X.

Considere uma derivação nesta gramática que comece com S ⇒ aXbc.Queremos, no próximo passo, substituir o X por alguma coisa. Mas,apesar de haver duas regras com X à esquerda da seta na gramática, sóuma delas pode ser aplicada. Isto ocorre porque na palavra aXbc o X


vem seguido de b, e a única regra em que X aparece neste ‘contexto’ éXb→ bX . Aplicando esta regra, obtemos

S ⇒ aXbc⇒ abXc⇒ abY bc2.

Continuando desta forma, podemos derivar a palavra a2b2c2 nesta gra-mática. A derivação completa é a seguinte:

S ⇒ aXbc⇒ abXc⇒ abY bc2 ⇒ aY b2c2 ⇒ a2b2c2.

De maneira semelhante, podemos derivar qualquer palavra da formaanbncn, com n ≥ 1. De fato, pode-se mostrar que o conjunto das pala-vras desta forma constitui toda a linguagem gerada pela gramática dadaacima.

Este exemplo se encaixa em uma classe de gramáticas chamadas desensíveis ao contexto. A definição formal é a seguinte. Seja G uma gra-mática com conjunto de terminais T , conjunto de variáveis V e símboloinicial S. Dizemos que G é sensível ao contexto se todas as regras de Gsão da forma u → v, onde u, v ∈ (T ∪ V )∗ e |u| ≤ |v|. Esta últimacondição é claramente satisfeita pelas regras de uma gramática livre decontexto, de modo que toda gramática livre de contexto é sensível aocontexto

Diremos que uma linguagem L no alfabeto Σ é sensível ao contextose existe uma gramática sensível ao contexto, com conjunto de terminaisΣ, que gera L. Portanto, toda linguagem livre de contexto é sensível aocontexto

A discussão acima mostra que a linguagem

{anbncn : n ≥ 1}

é sensível ao contexto. Entretanto, como provaremos no capítulo 11não existe nenhuma gramática livre de contexto que gere esta lingua-gem. Temos, assim, que a classe das linguagens livres de contexto estápropriamente contida na classe das linguagens sensíveis ao contexto. Arelação entre os diversos tipos de linguagens é detalhada na hierarquiade Chomsky, que discutiremos em um capítulo posterior.

3. Mais exemplos

Nesta seção veremos mais exemplos de linguagens livres de con-texto. Começamos com uma gramática que gera fórmulas que sejamexpressões aritméticas envolvendo apenas os operadores soma e multi-plicação, além dos parênteses. Isto é, expressões da forma

(3.1) ((x+ y) ∗ x) ∗ (z + w) ∗ y),

3. MAIS EXEMPLOS 67

onde x, y, z e w são variáveis (no sentido em que o termo é usado emálgebra).

Note que, para saber se uma dada expressão é legítima, não precisa-mos conhecer as variáveis que nela aparecem, mas apenas sua localiza-ção em relação aos operadores. Assim, podemos construir uma gramá-tica mais simples, em que as posições ocupadas por variáveis em umaexpressão são todas marcadas com um mesmo símbolo. Este símboloé chamado de identificador, e abreviado id. Portanto, o identificadorid será um terminal da gramática que vamos construir, juntamente comos operadores + e ∗ e os parênteses ( e ). Substituindo as variáveis daexpressão (3.1) pelo identificador, obtemos

(3.2) ((id + id) ∗ id) ∗ (id + id) ∗ id).

Em resumo, queremos construir uma gramática livre de contextoGexp , com conjunto terminais {+, ∗, (, ), id}, que gere todas as expres-sões aritméticas legítimas nos operadores + e ∗. Note que Gexp devegerar todas as expressões legítimas, e apenas estas. Isto é, queremosgerar expressões como (3.2), mas não como

(+id)id ∗ .Na prática estas expressões aritméticas são produzidas recursiva-

mente, somando ou multiplicando expressões mais simples, sem esque-cer de pôr os parênteses no devido lugar. Para obter a gramática, pode-mos criar uma variávelE (de expressão), e introduzir as seguintes regraspara combinação de expressões:

E → E + E

E → E ∗ EE → (E).

Finalmente, para eliminar E e fazer surgir o identificador, adicionamosa regra E → id.

Vejamos como derivar a expressão id + id ∗ id nesta gramática.Para deixar claro o que está sendo feito em cada passo, vamos utilizara convenção, estabelecida na seção em 1, de sublinhar a instância davariável à qual uma regra está sendo aplicada:(3.3)E ⇒ E+E ⇒ E+E ∗E ⇒ id+E ∗E ⇒ id+ id∗E ⇒ id+ id∗ id.

Construímos esta derivação aplicando em cada passo uma regra dagramática a uma variável escolhida sem nenhum critério especial. En-tretanto podemos ser mais sistemáticos. Por exemplo, poderíamos, em


cada passo da derivação, aplicar uma regra sempre à variável que estámais à esquerda da palavra. Usando esta estratégia chegamos a umaderivação de id + id ∗ id diferente da que foi obtida acima:

E ⇒ E + E ⇒ id + E ⇒ id + E ∗ E ⇒ id + id ∗ E ⇒ id + id ∗ id.

Neste caso não há necessidade de sublinhar a variável à qual a regra estásendo aplicada já que, em cada passo, escolhemos sempre a que estámais à esquerda da palavra.

As derivações deste tipo são muito importantes no desenvolvimentoda teoria e em suas aplicações. Por isso é conveniente ter um nomeespecial para elas. Seja G uma gramática livre de contexto e w ∈ L(G).Uma derivação mais à esquerda de w em G é aquela na qual, em cadapasso, a variável à qual a regra é aplicada é a que está mais à esquerdada palavra. Analogamente, podemos definir derivação mais à direitaem uma gramática livre de contexto.

Uma gramática como Gexp é usada em uma linguagem de programa-ção com duas finalidades diferentes. Em primeiro lugar, para verificarse as expressões aritméticas de um programa estão bem construídas; emsegundo, para informar ao computador qual é a interpretação corretadestas expressões. Por exemplo, o computador tem que ser informadosobre a precedência correta entre os operadores soma e multiplicação.Isto é necessário para que, na ausência de parêntesis, o computador saibaque deve efetuar primeiro as multiplicações e só depois as somas. Docontrário, confrontado com id + id ∗ id ele não saberia como efetuar ocálculo da forma correta. Voltaremos a esta questão em mais detalhesno próximo capítulo.

Analisando Gexp com cuidado, verificamos que permite derivar (id).Apesar do uso dos parênteses ser desnecessário neste caso, não se tratade uma expressão aritmética ilegítima. Entretanto, não é difícil resol-ver este problema introduzindo uma nova variável, como é sugerido noexercício 5.

O segundo exemplo que desejamos considerar é o de uma gramáti-ca que gere a linguagem formada pelos palíndromos no alfabeto {0, 1}.Lembre-se que um palíndromo é uma palavra cujo reflexo é igual a elaprópria. Isto é, w é um palíndromo se e somente se wR = w. Precisa-mos de dois fatos sobre palíndromos que são conseqüência imediata dadefinição. Digamos que w ∈ (0 ∪ 1)∗ e que σ é 0 ou 1; então:

(1) w é palíndromo se e somente se w começa e termina com omesmo símbolo;

(2) σwσ é palíndromo se e somente se w também é palíndromo.

4. COMBINANDO GRAMÁTICAS 69

Isto sugere que os palíndromos podem ser construídos recursivamenteonde, a cada passo, ladeamos um palíndromo já construído por duasletras iguais.

Com isto podemos passar à construção da gramática. Vamos chamá-la de Gpal: terá terminais {0, 1} e apenas uma variável S, que fará opapel de símbolo inicial. As observações acima sugerem as seguintesregras

S → 0S0

S → 1S1

Estas regras ainda não bastam, porque apenas com elas não é possíveleliminar S da palavra. Para fazer isto precisamos de, pelo menos, maisuma regra. A primeira idéia seria introduzir S → ε. Entretanto, se fizer-mos isto só estaremos gerando palíndromos que não têm um símbolo nomeio; isto é, os que têm comprimento par. Para gerar os de comprimentoímpar é necessário também introduzir regras que permitam substituir Spor um terminal; isto é,

S → 0 e S → 1.

Podemos resumir o que fizemos usando a seguinte notação. Supo-nha que G é uma gramática livre de contexto que tem várias regras

X → w1, . . . , X → wk

todas com uma mesma variável do lado esquerdo. Neste caso escreve-mos abreviadamente

X → w1 |w2 . . . |wk,

onde a barra vertical tem o valor de ‘ou’. Como Gpal tem uma únicavariável, podemos escrever todas as suas regras na forma

S → 0S0 | 1S1 | ε | 0 | 1.

De quebra, obtivemos a gramática G+pal que gera os palíndromos decomprimento par. A única diferença entre as duas gramáticas é que oconjunto de regras de G+pal é ainda mais simples:

S → 0S0 | 1S1 | ε.

4. Combinando gramáticas

Muitas vezes é possível decompor uma linguagem livre de contextoL como união, concatenação ou estrela de outras linguagens livres decontexto. Nesta seção introduzimos técnicas que facilitam a construção


de uma gramática livre de contexto para L a partir das gramáticas dassuas componentes.

Começaremos com um exemplo cuja verdadeira natureza só serárevelada no próximo capítulo. Considere a linguagem

Lin = {aibjck : i, j, k ≥ 0 e i = j ou j = k}.Podemos decompô-la, facilmente, como união de outras duas, a saber

L1 = {aibjck : i, j, k ≥ 0 e i = j}, e

L2 = {aibjck : i, j, k ≥ 0 e j = k}.Além disso, L1 = L3 · c∗ e L2 = a∗ · L4, onde

L3 = {aibj : i, j ≥ 0 e i = j}, e L4 = {bjck : j, k ≥ 0 e j = k}.Chegados a este ponto, já conseguimos obter uma decomposição de

Lin em linguagens para as quais conhecemos gramáticas. De fato, a∗

e c∗ são linguagens regulares para as quais existem gramáticas linearesà direita bastante simples. Por outro lado, a gramática G1 definida naseção 1 gera uma linguagem análoga a L3 e L4. Resta-nos descobrircomo esta decomposição pode ser usada para construir uma gramáticapara Lin. Contudo, é preferível discutir o problema de combinar gramá-ticas em geral, e só depois aplicá-lo no exemplo acima.

Suponhamos, então, que G1 e G2 são gramáticas livres de contextoque geram linguagens L1 e L2, respectivamente. O que queremos sãoreceitas que nos permitam obter gramáticas livres de contexto que geremL1 ∪ L2 e L1 · L2 a partir de G1 e G2.

Digamos que G1 tem ingredientes (T ,V1,S1,R1) e G2 ingredientes(T ,V2,S2,R2). Observe que estamos supondo que as duas gramáticastêm os mesmos terminais, e que os conjuntos de variáveis são disjuntos;isto é, V1 ∩ V2 = ∅.

Vamos começar com L1 ∪ L2. Neste caso a nova gramática, quechamaremos de G∪, deve gerar uma palavra que pertença a L1 ou a L2.Assim, o conjunto de regras de G∪ precisa conter R1 e R2. Mas quere-mos também que, depois do primeiro passo, a derivação só possa pro-ceder usando regras de uma das duas gramáticas. Fazemos isto criandoum novo símbolo inicial S e duas novas regras

S → S1 e S → S2.

Assim, o primeiro passo da derivação força uma escolha entre S1 e S2.Esta escolha determina de maneira inequívoca se a palavra a ser geradaestará em L1 ou L2. Em outras palavras, depois do primeiro passo a de-rivação fica obrigatoriamente restrita às regras de uma das duas gramá-ticas. Mais precisamente, G∪ fica definida pelos seguintes ingredientes:

4. COMBINANDO GRAMÁTICAS 71

Terminais: T1 ∪ T2;Variáveis: V1 ∪ V2 ∪ {S};Símbolo inicial: S;Regras: R1 ∪R2 ∪ {S → S1, S → S2}.

Podemos proceder de maneira semelhante para criar uma gramáticaG• que gere a concatenação L1 · L2. Neste caso, as palavras que quere-mos derivar são construídas escrevendo uma palavra de L1 seguida deuma palavra de L2. Como as palavras de L1 são geradas a partir de S1e as de L2 a partir de S2, basta acrescentar S → S1S2 às regras de G1 eG2. Os ingredientes da gramática G• são:

Terminais: T1 ∪ T2;Variáveis: V1 ∪ V2 ∪ {S};Símbolo inicial: S;Regras: R1 ∪R2 ∪ {S → S1S2}.

Finalmente, há uma receita semelhante às que foram dadas acimapara criar uma gramática livre de contexto para L∗ a partir de uma gra-mática livre de contexto que gere L. Deixamos os detalhes desta cons-trução para o exercício 7.

Podemos, agora, voltar à linguagem Lin. Como Lin = L3 · c∗∪a∗ ·L4, precisamos começar criando gramáticas que gerem as linguagensL3, L4, c∗ e a∗. Para L3 e L4 podemos usar adaptações da gramática G1da seção 1. Já c∗ e a∗ são regulares, geradas por gramáticas lineares àdireita extremamente simples. Resumimos os ingredientes destas váriasgramáticas na tabela abaixo:

Linguagem L3 L4 a∗ c∗

Terminais {0, 1} {0, 1} {0, 1} {0, 1}Variáveis S1 S2 S3 S4

Símbolo inicial S1 S2 S3 S4

Regras S1 → aS1b S2 → bS2c S3 → aS3 S4 → cS4

S1 → ε S2 → ε S4 → ε S3 → ε

Seguindo a receita dada acima para a gramática de uma concatena-ção, obtemos:


Linguagem L3 · c∗ a∗ · L4

Terminais {0, 1} {0, 1}Variáveis {S′, S1, S4} {S′′, S2, S3}Símbolo inicial S′ S′′

Regras S′ → S1S4 S′′ → S2S3

S1 → aS1b S2 → bS2c

S1 → ε S2 → ε

S4 → cS4 S3 → aS3

S3 → ε S4 → ε

Resta-nos, apenas, proceder à união destas gramáticas, o que nos dáuma gramática livre de contexto para Lin, com os seguintes ingredien-tes:

Terminais: {0, 1};Variáveis: S, S′, S′′, S1, S2, S3, S4;Símbolo inicial: S;Regras: {S → S′, S → S′′, S′ → S1S4, S

′′ → S2S3, S1 →aS1b, S2 → bS2c, S1 → ε, S2 → ε, S4 → cS4, S3 → aS3, S3 →ε, S4 → ε}.

5. Exercícios

1. Considere a gramática G com variáveis S,A, terminais a, b, símboloinicial S e regras

S → AA

A→ AAA | a | bA |Ab

(a) Quais palavras de L(G) podem ser produzidas com derivações deaté 4 passos?

(b) Dê pelo menos 4 derivações distintas da palavra babbab.(c) Para m,n, p > 0 quaisquer, descreva uma derivação em G de

bmabnabp.

2. Determine gramáticas livres de contexto que gerem as seguintes lin-guagens:(a) {(01)i : i ≥ 1};(b) {12n : n ≥ 1};(c) {0i12i : i ≥ 1};(d) {w ∈ {0, 1}∗ : w em que o número de 0s e 1s é o mesmo};(e) {wcwr : w ∈ {0, 1}∗};

5. EXERCíCIOS 73

(f) {w : w = wr onde w ∈ {0, 1}}.

3. Considere o alfabeto Σ = {0, 1, (, ),∪, ∗, ∅}. Construa uma gramá-tica livre de contexto que gere todas as palavras de Σ∗ que são ex-pressões regulares em {0, 1}.

4. A gramática livre de contexto G cujas regras são

S → 0S1 | 0S0 | 1S0 | 1S1 | εnão é linear à direita. Entretanto, L(G) é uma linguagem regular.Ache uma gramática linear à direita G′ que gere L(G).

5. Modifique a gramática Gexp (introduzindo novas variáveis) de modoque não seja mais possível derivar a expressão (id) nesta gramática.

6. Seja G uma gramática livre de contexto com conjunto de terminais T ,conjunto de variáveis V e símbolo inicial S. Dizemos que G é linearse todas as suas regras são da forma

X → αY β ou X → α,

onde X e Y são variáveis e α, β ∈ T ∗. Isto é pode haver no máximouma variável do lado direito de cada regra de G. Uma linguagem élinear se pode ser gerada por alguma gramática linear. Mostre quese L é linear então L pode ser gerada por uma gramática cujas regrassão de um dos 3 tipos seguintes:

X → σY ou X → Y σ ou X → σ

onde X é uma variável e σ é um terminal ou σ = ε.

7. Seja G uma gramática livre de contexto que gere uma linguagem L.Mostre como construir, a partir de G, uma gramática livre de contextoque gera L∗.SUGESTÃO: S → SS.

8. Seja L uma linguagem livre de contexto. Mostre que Lr = {wr :w ∈ L} também é livre de contexto.

CAPíTULO 10

Árvores Gramaticais

No capítulo anterior vimos como gerar palavras a partir de uma gra-mática livre de contexto, por derivação. Neste capítulo consideramosoutra maneira pela qual uma gramática livre de contexto gera palavras:as árvores gramaticais. Esta noção tem origem na necessidade de dia-gramar a análise sintática de uma sentença em uma língua natural, comoo português ou o javanês.

1. Análise Sintática e línguas naturais

Até agora as gramáticas formais que introduzimos têm servido basi-camente para gerar palavras que pertencem a uma dada linguagem. Já agramática da língua portuguesa não serve apenas para gerar frases comsintaxe correta, mas também para analisar a estrutura de uma frase e de-terminar o seu significado. A isso se chama análise sintática. Descobrirquem fez o quê, e a quem, é uma questão de identificar sujeito, verbo eobjetos de uma frase. Entretanto, a noção de derivação não é uma ferra-menta adequada para realizar a análise sintática em uma gramática; paraisto precisamos das árvores gramaticais.

Vejamos como usar uma árvore para diagramar a análise sintáticada frase

Pedro ligou o computador.

O sujeito da sentença é Pedro e o predicado é ligou o computador. Porsua vez o predicado pode ser decomposto no verbo ligou seguido doobjeto direto, o computador. Esta análise da frase pode ser diagramadaem uma árvore como a da figura abaixo.

75

76 10. ÁRVORES GRAMATICAIS

〈sentença〉

ppppppppppp

PPPPPPPPPPPP

〈sujeito〉〈predicado〉

nnnnnnnnnnnn

QQQQQQQQQQQQQ

〈verbo〉〈objeto〉

Pedro ligou o computador

Note que as palavras sentença, sujeito, predicado, verbo e objetodireto aparecem entre 〈〉. Fizemos isto para diferenciar o conceito,da palavra da língua portuguesa que o denota. Em outras palavras, 〈sujeito 〉 indica que na gramática da língua portuguesa há uma variávelchamada de sujeito.

Existe uma estreita relação entre a estrutura da árvore acima e asregras da gramática da língua portuguesa. Lendo esta árvore de cimapara baixo, cada bifurcação corresponde a uma regra da gramática por-tuguesa. As regras que aparecem na árvore da figura acima são as se-guintes:

〈sentença〉 → 〈sujeito〉〈predicado〉〈predicado〉 → 〈verbo〉〈objeto direto〉〈sujeito〉 → Pedro〈verbo〉 → ligou〈objeto direto〉 → o computador.

Assim podemos usar esta árvore para derivar a frase “Pedro ligou o com-putador” a partir das regras acima:

〈sentença〉 ⇒ 〈sujeito〉〈predicado〉 ⇒ 〈sujeito〉〈verbo〉〈objeto direto〉 ⇒Pedro〈verbo〉〈objeto direto〉 ⇒ Pedro ligou 〈objeto direto〉

⇒ Pedro ligou o computador

O principal resultado deste capítulo mostra que existe uma estreitarelação entre árvores gramaticais e derivações. Antes, porém, precisa-remos definir formalmente a noção de árvore gramatical de uma lingua-gem livre de contexto.

2. ÁRVORES GRAMATICAIS 77

2. Árvores Gramaticais

Nesta seção, além de introduzir formalmente o conceito de árvoregramatical de uma linguagem livre de contexto, estabelecemos a relaçãoentre árvores e derivações.

Lembre-se que uma árvore é um grafo conexo que não tem ciclos.As árvores que usaremos são na verdade grafos orientados. Entretanto,não desenharemos as arestas destas árvores como setas. Em vez disso,indicaremos que o vértice v precede v′ desenhando v acima de v′. Alémdisso suporemos sempre que estamos lidando com árvores que satisfa-zem as seguintes propriedades:

• há um único vértice, que será chamado de raiz, e que não éprecedido por nenhum outro vértice;• os sucessores de um vértice estão totalmente ordenados.

Se v′ e v′′ são sucessores de v, e se v′ precede v′′ na ordenação dosvértices, então desenharemos v′ à esquerda de v′′. De agora em diante apalavra árvore será usada para designar um grafo com todas as proprie-dades relacionadas acima.

————–Falta um grafo aqui—————

Um exemplo de árvore com estas propriedades, é a árvore genealó-gica que descreve os descendentes de uma dada pessoa. Note que, emuma árvore genealógica, os irmãos podem ser naturalmente ordenadospela ordem do nascimento. A terminologia que passamos a descrever éinspirada neste exemplo. Suponhamos que T é uma árvore e que v′ é umvértice de T . Então há um único caminho ligando a raiz a v′. Digamosque este caminho contém um vértice v. Neste caso,

• v é ascendente de v′ e v′ é descendente de v;• se v e v′ estão separados por apenas uma aresta então v é pai

de v′ e v′ é filho de v;• se v′ e v′′ são filhos de um mesmo pai, então são irmãos;• um vértice sem filhos é chamado de folha;• um vértice que não é uma folha é chamado de vértice interior.

A ordenação entre irmãos, que faz parte da definição de árvore, podeser estendida a uma ordenação de todas as folhas. Para ver como istoé feito, digamos que f ′ e f ′′ são duas folhas de uma árvore. Começa-mos procurando o seu primeiro ascendente comum, que chamaremos dev. Observe que f e f ′′ têm que ser descendentes de filhos diferentesde v, a não ser que sejam eles próprios filhos de v. Digamos que f édescendente de v′ e f ′′ de v′′. Como v′ e v′′ são irmãos, sabemos queestão ordenados; digamos que v′ precede v′′. Neste caso dizemos que


f ′ precede f ′′. Esta é uma ordem total; isto é, todas as folhas de umatal árvore podem ser escritas em fila, de modo que a seguinte sucede àanterior.

Nenhuma preocupação adicional com esta ordenação é necessáriaãona hora de desenhar uma árvore; basta obedecer à convenção de sempreordenar os vértices irmãos da esquerda para a direita. Se fizermos isto,as folhas ficarão automaticamente ordenadas da esquerda para a direita.

Seja G uma gramática livre de contexto com terminais T e variá-veis V . De agora em diante estaremos considerando árvores, no sentidoacima, cujos vértices estão rotulados por elementos de T ∪V . Contudo,não estaremos interessados em todas estas árvores, mas apenas naquelasresultantes de um procedimento recursivo bastante simples, as árvoresgramaticais. Como se trata de uma definição recursiva, precisamos esta-belecer quem são os átomos da construção, que chamaremos de árvoresbásicas, e de que maneira podemos combiná-las.

As árvores gramaticais são definidas recursivamente da seguintemaneira:

Árvores básicas: se σ ∈ T , X ∈ V e X → ε é uma regra de G, então

•σ e X

ε

são árvores gramaticais e suas colheitas são, respectivamente, σ e ε.

Regras de combinação: sejam T1, . . . , Tn árvores gramaticais, e supo-nhamos que o rótulo da raiz de Tj é αj . Se X → α1 · · ·αn é uma regrade G, então a árvore T definida por

X

jjjjjjjjjjjjjjjjjjjj

VVVVVVVVVVVVVVVVVVVVVVVVVV

α1

��

//////////////// α2

��

22222222222222222αn

��

................

T1 T2 · · · · · · Tn

também é uma árvore gramatical.

Um exemplo simples é a árvore na gramática Gexp (definida na seção3 do capítulo 7) esboçada abaixo.

2. ÁRVORES GRAMATICAIS 79

E

~~~~~~~

PPPPPPPPPPPPPP

E + E

~~~~~~~

@@@@@@@

id id ∗ id

FIGURA 1. Árvore gramatical

Uma conseqüência muito importante desta definição recursiva, euma que usaremos em várias oportunidades, é a seguinte. Suponha-mos que uma árvore gramatical T tem um vértice v rotulado por umavariável X . Então podemos trocar toda a parte de T que descende de vpor qualquer outra árvore gramatical cuja raiz seja rotulada por X .

Segue também da definição que os únicos vértices de uma árvoregramatical que podem ser rotulados por elementos de T ∪ {ε} são asfolhas. Portanto, um vértice interior de uma árvore gramatical só podeser rotulado por uma variável.

Por outro lado, se o vértice v de uma árvore gramatical T está rotu-lado por uma variável X , e seus filhos por α1, . . . , αn ∈ T ∪ V entãoX → α1 · · ·αn tem que ser uma regra da gramática G. Diremos que estaé a regra associada ao vértice v. No caso de v ser a raiz, T é uma X-árvore. Caso a árvore gramatical consista apenas de uma folha rotuladapor um terminal σ, diremos que se trata de uma σ-árvore.

Uma vez tendo introduzido árvores gramaticais temos uma outramaneira de gerar palavras a partir de uma gramática livre de contexto.Para isso, definimos a colheita c(T ) de uma árvore gramatical T . Comoa definição de árvore é recursiva, assim será a definição de colheita. Ascolheitas das árvores básicas são

c(•σ) = σ e c

X

ε

= ε

Por outro lado sejam T1, . . . , Tn árvores gramaticais, e suponhamos queo rótulo da raiz de Tj é αj . Se X → α1 · · ·αn é uma regra de G, entãoa árvore T construída de acordo com a regra de combinação satisfaz

c(T ) = c(T1) · c(T2) · · · c(Tn).

Como conseqüência da definição recursiva, temos que a colheita deuma árvore gramatical T é a palavra obtida concatenando-se os rótulos


de todas as folhas de T , da esquerda para a direita. Como as folhasde uma árvore gramatical estão totalmente ordenadas, não há nehumaambigüidade nesta maneira de expressar a colheita. Para uma demons-tração formal deste fato veja o exercício 1. Portanto, a árvore da figura1 tem colheita id + id ∗ id.

Digamos quew é uma palavra que pode ser derivada em uma gramá-tica livre de contexto G com símbolo inicial S. Uma árvore de derivaçãopara w é uma S-árvore de G cuja colheita é w. Note que reservamos onome de árvore de derivação para o caso especial das S-árvores.

3. Colhendo e derivando

No capítulo 7 vimos como gerar uma palavra em terminais a partirdo símbolo inicial de uma linguagem livre de contexto por derivação. Anoção de colheita de uma árvore gramatical nos dá uma segunda maneirade produzir uma tal palavra. Como seria de esperar, há uma estreitarelação entre estes dois métodos, que será discutida em detalhes nestaseção.

Para explicitar a relação entre árvores gramaticais e derivações va-mos descrever um algoritmo que constrói uma derivação mais à es-querda de uma palavra a partir de sua árvore gramatical. Heuristica-mente falando, o algoritmo desmonta a árvore gramatical da raiz às fo-lhas. Contudo, ao remover a raiz de uma árvore gramatical, não obtemosuma nova árvore gramatical, mas sim uma seqüência ordenada de árvo-res. Isto sugere a seguinte definição. Seja G uma gramática livre decontexto com terminais T e variáveis V . Se

w = α1 · · ·αn ∈ (T ∪ V )∗

então uma uma w-floresta F é uma seqüência ordenada T1, . . . , Tn deárvores gramaticais, onde Tj é uma αj-árvore. A colheita da floresta Fé a concatenação das colheitas de suas árvores; isto é

c(F) = c(T1) · · · c(Tn).

Podemos agora descrever o algoritmo. Lembre-se que quando di-zemos ‘remova a raiz da árvore T ’ estamos implicitamente assumindoque as arestas incidentes à raiz também estão sendo removidas. Se v éa raiz de uma árvore T da floresta F , denotaremos por F \ v a florestaobtida quando v é removido de T .

Precisamos considerar, separadamente, o efeito desta construçãoquando T é a árvore básica que tem a raiz rotulada pela variável X euma única folha rotulada por ε. Neste caso, quando removemos a raizsobra apenas um vértice rotulado por ε, que não constitui uma árvore

3. COLHENDO E DERIVANDO 81

gramatical. Suporemos, então, que remover a raiz de uma tal árvore temo efeito de apagar toda a árvore.

ALGORITMO 10.1. Constrói uma derivação a partir de uma árvoregramatical.

Entrada: uma X-árvore T , onde X é uma variável.Saída: uma derivação mais à esquerda de c(T ).

Etapa 1: Inicialize F com T .Etapa 2: SeF é umaw-floresta, então imprimaw. Páre se todas

as árvores de F são rotuladas por terminais.Etapa 3: Seja v a raiz da árvore mais à esquerda de F que é

rotulada por uma variável. Faça F = F \ v e volte à etapa 2.

À seguir, você encontrará um exemplo da aplicação passo a passodeste algoritmo a uma árvore na gramática Gexp.

Inicialização Passo 1

E

}}}}PPPPPPPPP

E + E

}}}}AAAA E + E

}}}}AAAA

id E ∗ E id E ∗ E

id id id id

Imprime: E Imprime: E + E

Passo 2 Passo 3

+ E

}}}}AAAA +

id E ∗ E id E ∗ E

id id id id

Imprime: id+ E Imprime: id+ E ∗ E


Passo 4 Passo 5

+ +

id ∗ E id ∗

id id id id

Imprime: id+ id ∗ E Imprime: id+ id ∗ id

Resta-nos demonstrar que este algoritmo funciona. Começamospor analisar o que o algoritmo faz quando um de seus passos é execu-tado. Suponhamos que, ao final do k-ésimo passo, temos uma α1 · · ·αn-floresta F formada pelas árvores T1, . . . , Tn. Portanto, a palavra im-pressa pelo algoritmo no passo k é

α1 · · ·αn.

Digamos que αj é uma variável, mas que α1, . . . , αj−1 são termi-nais. Portanto, a árvore mais à esquerda de F , cuja raiz é rotulada poruma variável, é Tj . Assim, ao executar o (k + 1)-ésimo passo do al-goritmo deveremos remover a raiz de Tj . Mas ao fazer isto estamossubstituindo Tj em F por uma β1 · · ·βr-floresta, onde αj → β1 · · ·βré a regra associada à raiz de Tj . Ao final deste passo, o algoritmo teráimpresso

α1 · · ·αj−1β1 · · ·βrαj+1 · · ·αn.Entretanto, αj era a variável mais à esquerda de α1 · · ·αn, e

α1 · · ·αj−1αjαj+1 · · ·αn ⇒ α1 · · ·αj−1β1 · · ·βrαj+1 · · ·αn.

Como o algoritmo começa imprimindo X , podemos concluir que pro-duz uma derivação mais à esquerda em G, a partir de X . Falta apenasmostrar que o que é derivado é mesmo c(T ). Contudo, a colheita das flo-restas a cada passo da aplicação do algoritmo é sempre a mesma. Alémdisso, as árvores gramaticais que constituem a floresta no momento queo algoritmo termina têm suas raízes indexadas por terminais. Como oalgoritmo não apaga nenhum vértice indexado por terminal diferente deε, concluímos que a concatenação das raízes das árvores no momentoem que o algoritmo pára é c(T ), como desejávamos.

4. EQUIVALÊNCIA ENTRE ÁRVORES E DERIVAÇÕES 83

4. Equivalência entre árvores e derivações

Passemos à recíproca da questão considerada na seção 3. Mais pre-cisamente, queremos mostrar que se G é uma gramática livre de contextoentão toda palavra que tem uma derivação em G é colheita de algumaárvore de derivação de G.

Para resolver este problema usando um algoritmo precisaríamos in-ventar uma receita recursiva para construir uma árvore de derivação apartir de uma derivação qualquer em G. Isto é possível, mas o algoritmoresultante não é tão enxuto quanto o anterior. Por isso vamos optar pordar uma demonstração indireta, por indução.

PROPOSIÇÃO 10.2. Seja X uma variável da gramática livre decontexto G. Se existe uma derivação X ⇒∗ w, então w é colheita deuma X-árvore em G.

DEMONSTRAÇÃO. Suponhamos que a gramática livre de contextoG tem terminais T e variáveis V . A proposição será provada por induçãono número p de passos de uma derivação X ⇒p w.

A base da indução consiste em supor que existe uma derivaçãoX ⇒w de apenas um passo. Mas isto só pode ocorrer se existem terminaist1, . . . , tn e uma regra da formaX → t1 · · · tn. Assim, w é a colheita deuma X-árvore que tem a raiz rotulada por X e as folhas por t1, . . . , tn,o que prova a base da indução.

A hipótese de indução afirma que, se Y ∈ V e se existe uma deriva-ção

Y ⇒p u ∈ T ∗,então u é colheita de uma Y -árvore de G. Digamos, agora, que w ∈T ∗ pode ser derivado a partir de X ∈ V em p + 1 passos. O pri-meiro passo desta derivação será da forma X ⇒ v1v2 · · · vn, ondev1, . . . , vn ∈ T ∪ V e X → v1v2 · · · vn é uma regra de G. A derivaçãocontinua com cada vi deflagrando uma derivação da forma vi ⇒∗ uionde u1 · · ·un = w. Como cada uma destas derivações tem compri-mento menor ou igual a p, segue da hipótese de indução que existemvi-árvores Ti com colheita ui, para cada i = 1, . . . , n. Mas T1, . . . , Tné uma v1 · · · vn-floresta, e a primeira regra utilizada na derivação de wfoi X → v1 · · · vn. Portanto, pela definição de árvore gramatical, pode-mos colar as raízes desta floresta de modo a obter uma X-árvore cujacolheita é

c(T1) · · · c(Tn) = u1 · · ·un = w,

o que prova o passo de indução. O resultado desejado segue pelo prin-cípio de indução finita.


Só nos resta reunir, para referência futura, tudo o que aprendemossobre a relação entre derivações e árvores gramaticais em um único te-orema. Antes de enunciar o teorema, porém, observe que tudo o quefizemos usando derivações mais à esquerda vale igualmente para deri-vações mais à direita.

TEOREMA 10.3. Seja G uma gramática livre de contexto e w ∈L(G). Então:

(1) existe uma árvore de derivação cuja colheita é w;(2) a cada árvore de derivação cuja colheita éw corresponde uma

única derivação mais à esquerda de w;(3) a cada árvore de derivação cuja colheita éw corresponde uma

única derivação mais à direita de w.

Temos que (1) segue da proposição acima e que (2) é conseqüên-cia do algoritmo da seção 3. Já (3) segue de uma modificação óbviadeste mesmo algoritmo. A importância deste teorema ficará clara nospróximos capítulos.

5. Ambigüidade

Como vimos na seção 1, as árvores gramaticais são usadas na gra-mática da língua portuguesa para representar a análise sintática de umafrase em um diagrama. Portanto, têm como finalidade ajudar-nos a in-terpretar corretamente uma frase.

Contudo, é preciso não esquecer que é possível escrever sentençasgramaticalmente corretas em português que, apesar disso, admitem duasinterpretações distintas. Por exemplo, a frase

a seguir veio uma mãe com uma criança empurrandoum carrinho,

pode significar que a mãe empurrava um carrinho com a criança dentro;ou que a mãe vinha com uma criança que brincava com um carrinho.Ambos os sentidos são admissíveis, mas a função sintática das palavrasnum, e noutro caso, é diferente. No primeiro caso o sujeito que corres-ponde ao verbo empurrar é mãe, no segundo caso é criança. Assim,teríamos que escolher entre duas árvores gramaticais diferentes para re-presentar esta frase, cada uma correspondendo a um dos sentidos acima.

No caso de uma gramática livre de contexto G, formalizamos estanoção de dupla interpretação na seguinte definição. A gramática G éambígüa se existe uma palavra w ∈ L(G) que admite duas árvores dederivação distintas em G.

É bom chamar a atenção para o fato de que nem toda frase comduplo sentido em português se encaixa na definição acima. Por exemplo,

5. AMBIGÜIDADE 85

“a galinha está pronta para comer” tem dois significados diferentes, masem ambos as várias palavras da frase têm a mesma função sintática.Assim, não importa o significado que você dê à frase, o sujeito é sempre‘a galinha’.

Frases que admitem significados diferentes são uma fonte inesgo-tável de humor; mas para o compilador de uma linguagem de progra-mação uma instrução que admite duas interpretações distintas pode serum desastre. Voltemos por um momento à gramática Gexp. Na figuraabaixo, à direita, reproduzimos a árvore de derivação de id + id ∗ id quejá havíamos esboçado na seção 2. Uma árvore de derivação diferentepara a mesma expressão pode ser encontrada à esquerda, na mesma fi-gura.

E

nnnnnnnnn

MMMMMMM E

}}}}PPPPPPPPP

E

}}}} AAAA ∗ E E + E

}}}} AAAA

E + E id id E ∗ E

id id id id

FIGURA 2. Duas árvores e uma mesma colheita

A existência desta segunda árvore de derivação significa que, se umcomputador estiver usando a gramática Gexp, ele não saberá como dis-tinguir a precedência correta entre os operadores + e ∗. Dito de outramaneira, esta gramática não permite determinar que, quando nos depa-ramos com id + id ∗ id devemos primeiro efetuar a multiplicação e sódepois somar o produto obtido com a outra parcela da soma.

Uma saída possível é tentar inventar uma outra gramática que gerea mesma linguagem, mas que não seja ambígüa. A idéia básica consisteem introduzir novas variáveis e novas regras que forcem a precedênciacorreta. Para fazer isto, compare novamente as duas árvores gramaticaiscom colheita id + id ∗ id da figura 2.

Observe que, na árvore da direita, id ∗ id é obtida a partir da ex-pressão E ∗ E, e os vértices que correspondem a estes três rótulos sãotodos irmãos. Por outro lado, o único vértice do qual descendem todosos símbolos da expressão id + id ∗ id é a própria raiz. Portanto, inter-pretando a expressão id + id ∗ id conforme a árvore da direita, teremosprimeiro que calcular o produto, e só depois a soma. Interpretando amesma expressão de acordo com a árvore da esquerda, vemos que nestecaso a adição id + id é efetuada antes, e o resultado, então, multiplicado


por id. Isto é, a árvore que dá a interpretação correta da precedência dosoperadores é a que está à direita da figura 2.

Assim, precisamos construir uma nova gramática na qual uma ár-vore como a que está à direita da figura possa ser construída, mas nãouma como a da esquerda.

A estratégia consiste em introduzir novas variáveis de modo a forçara precedência correta dos operadores. Faremos isto deixando a variávelE controlar as adições, e criando uma nova variável F (de fator) paracontrolar a multiplicação. O conjunto de regras resultante é o seguinte:

E → E + F

E → F

F → F ∗ FF → (E)

F → id

Não há nada de mais a comentar sobre a primeira e a terceira regras; e asegunda apenas permite passar de somas a multiplicações. A regra querealmente faz a diferença é a quarta. Ela nos diz que, após efetuar umamultiplicação, só podemos voltar à variável E (que controla as somas)colocando os parêntesis.

Embora esta nova gramática não permita a construção de uma ár-vore como a da esquerda na figura 2, ainda assim ela é ambígüa. Porexemplo, as árvores da figura 3 estão de acordo com a nova gramáticamas, apesar de diferentes, têm ambas colheita id ∗ id ∗ id.

E E

F

PPPPPPPPP

}}}}F

AAAA

nnnnnnnnn

F ∗ FAAAA

}}}}F

AAAA}}}}

∗ F

id F ∗ F F ∗ F id

id id id id

FIGURA 3. Outras duas árvores com mesma colheita

A saída é introduzir mais uma variável, que vamos chamar de T(para termo). A nova gramática, que chamaremos de G′exp, tem variáveis

5. AMBIGÜIDADE 87

E, T e F , símbolo inicial E, e as seguintes regras:

E → E + T | T

T → T ∗ F | F

F → (E)| id

A gramática G′exp não é ambígüa, mas provar isto não é fácil, e nãofaremos os detalhes aqui.

Ainda há um ponto que precisa ser esclarecido. A discussão anteriorpode ter deixado a impressão de que, para estabelecer a precedênciacorreta entre os operadores aritméticos, basta eliminar a ambigüidadeda gramática. Mas isto não é verdade. Por exemplo, a gramática G”expcujas regras são:

S → E

E → (E)R | V R

R→ +E | ∗ E | A

V → id

A→ ε

gera Lexp. Além disso, não é difícil provar que esta gramática não podeser ambígüa. Isto decorre dos seguintes fatos:

• não há mais de duas regras em G”exp cujo lado esquerdo sejaocupado por uma mesma variável;• se há duas regras a partir de uma mesma variável, o lado di-

reito de uma começa com uma variável, e o da outra com umterminal;• cada terminal só aparece uma vez como prefixo do lado direito

de alguma regra de G”exp.Imagine, então, que estamos tentando calcular uma derivação à esquerdaem G”exp para uma dada palavra w ∈ Lexp. Digamos que, isolando on-ésimo passo da derivação, obtivemos o seguinte

S ⇒∗ uEv ⇒ w,

onde u só contém terminais, mas v pode conter terminais e variáveis.Precisamos decidir qual a regra a ser aplicada a seguir. Neste exemplo, avariável mais à esquerda no n-ésimo passo da derivação é E. Assim, háduas regras que podemos aplicar. Para saber qual das duas será escolhidavoltamos nossa atenção para a palavra w que está sendo derivada. Éclaro que w tem u como prefixo; digamos que o terminal seguinte a uem w seja σ. Temos então duas possibilidades. Se σ = ( então a regra


a ser aplicada tem que ser E → (E)R. Por outro lado, se σ 6= ( entãosó nos resta a possibilidade de aplicar E → V R. Assim, a regra a seraplicada neste passo está completamente determinada pela variável maisà esquerda presente, e pela seqüência de terminais da palavra que estásendo derivada.

Entretanto, apesar de G”exp não ser ambígüa, a árvore de derivaçãode id + id ∗ id em G”exp não apresenta a precedência desejada entre osoperadores, como mostra a figura abaixo.

S

E

@@@@@@@

~~~~~~~

V R

@@@@@@@

~~~~~~~~

id ∗ E

@@@@@@@

~~~~~~~

V R

@@@@@@@

~~~~~~~

id + E

@@@@@@@

~~~~~~~

V R

id A

ε

Voltaremos a discutir G”exp quando tratarmos de autômatos de pilhadeterminísticos.

6. Removendo ambigüidade

O que fizemos na seção anterior parece indicar que, ao se depararcom uma gramática ambígüa, tudo o que temos que fazer é adicionaralgumas variáveis e alterar um pouco as regras de maneira a remover a

6. REMOVENDO AMBIGÜIDADE 89

ambigüidade. É verdade que criar novas variáveis e regras para removerambigüidade pode não ser muito fácil, e é bom não esquecer que nãochegamos a provar que a gramática G′exp não é ambígüa.

Por outro lado, isto parece bem o tipo de problema que poderia serdeixado para um computador fazer, bastaria que descobríssemos o al-goritmo. É aí justamente que está o problema. Um computador nãoconsegue sequer detectar que uma linguagem é ambígüa. De fato:

não pode existir um algoritmo para determinar se umadada linguagem livre de contexto é ou não ambígüa.

Voltaremos a esta questão em um capítulo posterior.Infelizmente, as más notícias não acabam aí. Há linguagens livres

de contexto que não podem ser geradas por nenhuma gramática livrede contexto que não seja ambígüa. Tais linguagens são chamadas deinerentemente ambígüas. Note que ambigüidade é uma propriedade dagramática, mas ambigüidade inerente é uma propriedade da própria lin-guagem.

Um exemplo bastante simples de linguagem inerentemente ambígüaé

Lin = {aibjck : i, j, k ≥ 0 e i = j ou j = k}.

Com isso você descobre porque demos este nome a Lin. Não é fácilmostrar que esta linguagem é inerentemente ambígüa, e por isso nãovamos fazer a demonstração aqui. Os detalhes podem ser encontradosem [1, theorem 7.2.2, p. 236] ou [2, theorem 4.7, p. 100].

Para não encerrar o capítulo num clima pessimista, vamos analisaro problema da ambigüidade para o caso particular das linguagens regu-lares. Sabemos que estas linguagens podem ser geradas por gramáticaslivres de contexto de um tipo bastante especial: as gramáticas lineares àdireita. Assim a primeira pergunta é: uma gramática linear à direita podeser ambígüa? A resposta é sim. Por exemplo, considere a gramática comterminal {0}, que tem S como única variável, e cujas regras são

S → 0 | 0S | 02.

A palavra 02 tem duas árvores gramaticais distintas que estão esboçadasna abaixo.

S

�� ???? S

��>>>>

0 S 0 0

0


Felizmente, no caso de gramáticas lineares à direita é sempre possí-vel remover a ambigüidade. Em outras palavras, não existem linguagensregulares inerentemente ambígüas. Além disso, existe um algoritmosimples que, tendo como entrada uma gramática linear à direita, cons-trói uma outra que gera a mesma linguagem regular mas não é ambígüa.O algoritmo é conseqüência do seguinte fato:

a gramática linear à direita construída a partir de umautômato finito determinístico pelo algoritmo do ca-pítulo 8 não é ambígüa.

Para entender porque isto é verdade, suponha que M seja um autômatofinito determinístico e G seja a gramática construída a partir de M peloalgoritmo do capítulo ??. Vimos que as derivações em G simulam com-putações em M e vice-versa. Como M é determinístico, só há umacomputação possível para cada palavra de L(M). Logo cada palavrade L(G) = L(M) só tem uma derivação possível. Como G é linear àdireita, toda derivação em G é mais à esquerda. Logo G não é ambígüapelo teorema da seção 4.

Diante deste resultado, é claro que, ao receber uma gramática linearà direita G como entrada, o algoritmo procede da seguinte maneira:

Etapa 1: determina um autômato finito não determinístico M talque L(M) = L(G);

Etapa 2: determina um autômato finito determinísticoM ′ tal queL(M) = L(M ′);

Etapa 3: determina uma gramática G′, obtida a partir de M ′, eque gera L(M ′).

Como já vimos, G′ não pode ser uma gramática ambígüa.

7. Exercícios

1. Prove, por indução no número de vértices internos, que a colheita deuma árvore gramatical T é igual à palavra obtida concatenando-se osrótulos das folhas de T da esquerda para a direita.

2. Seja G uma gramática livre de contexto e seja X uma variável de G.Seja w uma palavra somente em terminais e que pode ser derivadaem G a partir de X . Prove, por indução no número de passos de umaderivação de w a partir de X que existe uma X-árvore em G cujacolheita é w.

3. Considere a gramática não ambígua G′exp que gera as expressões arit-méticas.

7. EXERCíCIOS 91

(a) Esboce as árvores de derivação de id + (id + id) ∗ id e de (id ∗id + id ∗ id)

(b) Dê uma derivação à esquerda e uma derivação à direita da ex-pressão (id ∗ id + id ∗ id).

4. Repita o exercício anterior para a gramática G”exp.

5. Descreva detalhadamente um algoritmo que, tendo como entrada aderivação de uma palavra w em uma gramática livre de contexto,constrói uma árvore gramatical cuja colheita é w. O principal pro-blema consiste em, tendo dois passos consecutivos da derivação, de-terminar qual a regra que foi aplicada.

6. Prove que a gramática G”exp não é ambígüa.SUGESTÃO: Use indução no número de passos de uma derivação àesquerda.

7. Mostre que a gramática cujas regras são

S → 1A | 0BA→ 0 | 0S | 1AAB → 1 | 1S | 0BB

é ambígua.

8. Seja G a gramática linear à direita com terminais {0, 1}, variáveis {}e símbolo inicial S, cujas regras são dadas por

S → 0X

X → 10Y | 1ZZ → 01W | 1

Y → 1 |0W → ε

(a) Mostre que G é ambígüa.(b) Use o algoritmo descrito em 6 para construir uma gramática li-

near à direita G′ não ambígüa que gere L(G).

CAPíTULO 11

Linguagens que não são livres de contexto

Neste capítulo, finalmente, confrontamos a inevitável pergunta: comoprovar que uma dada linguagem não é livre de contexto? A estratégia émuito semelhante à adotada para linguagens regulares, apesar do lemado bombeamento resultante ser um pouco mais difícil de aplicar na prá-tica.

1. Introdução

Já conhecemos muitas linguagens livres de contexto, mas ainda nãotemos nenhum exemplo de uma linguagem que não seja deste tipo. Querdizer, já dissemos no capítulo 9 que a linguagem

Labc = {anbncn : n ≥ 0}

não é livre de contexto, mais ainda não provamos isto. É claro queisto não é satisfatório. O problema é que nada podemos concluir dosimples fato de não termos sido capazes de inventar uma gramática livrede contexto que gere esta linguagem. Talvez a gramática seja muitocomplicada, ou quem sabe foi só falta de inspiração.

Mas como será possível provar que não existe nenhuma gramáticalivre de contexto que gere uma dada linguagem? A estratégia é a mesmaadotada para o caso de linguagens regulares. Isto é, provaremos que todalinguagem livre de contexto satisfaz uma propriedade de bombeamento.Portanto, uma linguagem que não satisfizer esta propriedade não podeser livre de contexto. Começamos com um resultado relativo a árvoresque será necessário na demonstração do lema do bombeamento.

Como no capítulo anterior, consideraremos apenas árvores enraiza-das. Dizemos que uma árvore ém-ária se cada vértice tem, no máximo,

93

94 11. LINGUAGENS QUE NÃO SÃO LIVRES DE CONTEXTO

m filhos. Desejamos relacionar o número de folhas de uma árvore m-ária com a altura desta árvore. Lembre-se que a altura de uma árvore éo mais longo caminho entre a raiz e alguma de suas folhas.

Quando todos os vértices internos da árvore têm exatamente m-filhos, a árvore m-ária é completa. Seja f(h) o número de folhas deuma árvore m-ária completa de altura h. Como a árvore m-ária com-pleta é aquela que tem o maior número possível de folhas, o problemaestará resolvido se formos capazes de encontrar uma fórmula para f(h)em função de h e m. Faremos isto determinando uma relação de recor-rência para f(h) e resolvendo-a.

Para começar, se a árvore tem altura zero, então consiste apenas deum vértice. Neste caso há apenas uma folha, de modo que f(0) = 1.Para estabelecer a relação de recorrência podemos imaginar que T éuma árvore m-ária completa de altura h. É claro que, removendo todasas folhas de T , obtemos uma árvorem-ária completa T ′ de altura h−1.Para reconstruir T a partir de T ′ precisamos repor as folhas. Fazemosisso dando m-filhos a cada folha de T ′. Como T ′ tem f(h− 1) folhas,obtemos

f(h) = mf(h− 1).

Assim,

f(h) = mf(h− 1) = m2f(h− 2) = · · · = mhf(0) = mh.

Portanto, f(h) = mh é a fórmula desejada.Para estabelecer a relação entre este resultado e o lema do bombe-

amento precisamos de uma definição. Seja G uma linguagem livre decontexto. A amplitude α(G) de uma gramática livre de contexto G é ocomprimento máximo das palavras que aparecem à direita de uma setaem uma regra de G. Por exemplo, para as gramáticas Gexp e G′′exp defi-nidas no capítulo anterior, temos α(Gexp) = 3 e α(G′′exp) = 4.

Se uma gramática livre de contexto tem amplitude α, então todasas suas árvores gramaticais são α-árias. A fórmula para o número defolhas de uma árvore α-ária completa nos dá então seguinte lema.

LEMA 11.1. Seja G uma linguagem livre de contexto. Se X é umavariável de G e se w é colheita de uma X-árvore de G de altura h então

|w| ≤ α(G)h.

2. Lema do bombeamento

Antes de enunciar e provar o lema do bombeamento de maneiraformal, vamos considerar o seu funcionamento de maneira informal.


Suponhamos que G é uma gramática livre de contexto que gera umalinguagem infinita. Segundo o lema da seção 1, quanto maior o com-primento da colheita de uma árvore gramatical maior tem que ser a suaaltura. Portanto, se o comprimento da colheita de uma árvore de deri-vação T é suficientemente grande, então o caminho mais longo entre araiz e alguma folha conterá mais vértices interiores do que há variáveisna gramática. Em particular, haverá dois vértices diferentes em T cujosrótulos são iguais. Vamos chamar de ν1 e ν2 estes vértices, e de A avariável que os rotula, como na figura 1.

FIGURA 1. Decompondo a palavra para bombear

Observe que as regras associadas a ν1 e ν2 têm ambas A do seulado esquerdo. Mas isto significa que podemos construir a partir deT uma nova árvore T ′ da seguinte maneira. Comece construindo T ′exatamente como T até chegar a ν2. Como ν2 é rotulado pela mesmavariável que ν1, podemos construir a partir dele a mesma A-árvore queestava associada a ν1 em T , como mostra a figura 2. Note que os trechosda colheita da árvore T da figura 1 marcados como v e y aparecemrepetidos em T ′. Como T ′ é uma árvore de derivação em G, sua colheitaé um elemento de L(G) no qual os trechos x e y de c(T ) aparecembombeados. Naturalmente o processo acima pode ser repetido quantasvezes quisermos, de modo que podemos bombear estes trechos qualquernúmero de vezes.

Para que esta propriedade do bombeamento possa ser usada paraprovar que uma linguagem não é livre de contexto precisamos formulá-la de maneira mais precisa. Além disso, como no caso do lema cor-respondente para linguagens regulares, incluiremos algumas condições


FIGURA 2. Bombeando uma vez

técnicas extras que reduzem o número de possíveis decomposições dapalavra a ser bombeada que precisamos considerar. De fato, há váriasversões diferentes do lema do bombeamento para linguagens livres decontexto. A que apresentamos aqui não é a mais forte, mas é suficientepara cobrir muitos dos exemplos mais simples. Versões mais sofistica-das são discutidas em [2, Chapter 6, p. 125].

LEMA DO BOMBEAMENTO. Seja G uma gramática livre de con-texto. Existe um número inteiro ρ, que depende de G, tal que, se w ∈L(G) e |w| ≥ ρ, então existe uma decomposição de w na forma w =uvxyz, onde

(1) vy 6= ε;(2) |vxy| ≤ ρ;(3) uvnxynz ∈ L(G), para todo n ≥ 0.

DEMONSTRAÇÃO. Suponhamos que G tem k variáveis; neste casoescolheremos ρ = α(G)k+1. Seja w ∈ L(G) uma palavra com compri-mento maior que ρ. Já sabemos, pelo teorema da seção 4 do capítulo10, que têm que existir árvores de derivação com colheita w. Entre to-das estas árvores escolha uma, que chamaremos de T , que satisfaça aseguinte propriedade:

Hipótese 1: T tem o menor número possível de folhas entre to-das as árvores de derivação de colheita w em G.


Como a colheita de T tem comprimento maior que ρ = α(G)k+1,segue do lema da seção 1 que T tem altura pelo menos k+1. Chamandode C o mais longo caminho em T que vai de sua raiz a uma folha, con-cluímos que C tem, pelo menos, k+1 arestas. Logo C tem, no mínimo,k + 2 vértices. Como só pode haver uma folha num tal caminho, entãoC tem k + 1 vértices interiores. Contudo k é o número de variáveisda gramática, e cada vértice de C está rotulado por uma variável. Por-tanto, pelo princípio da casa do pombo, há dois vértices diferentes emC rotulados pela mesma variável. Entre todos os pares de vértices deC rotulados pela mesma variável, escolha aquele que satisfaz a seguintepropriedade:

Hipótese 2: o vértice ν1 precede o vértice ν2 e todos os vérticesde C entre ν1 e a folha são rotulados por variáveis distintas.

Lembre-se que as árvores que estamos considerando são grafos orien-tados. Portanto, C é um caminho orientado; logo faz sentido dizer, dedois vértices de C, que um precede o outro.

Seja A a variável que rotula ν1 e ν2. Temos então duas A-árvores:T1, com raiz em ν1, e T2 com raiz em ν2. Denotaremos por x a colheitade T2. Observe que, como ν1 precede ν2 ao longo de C, então x é umasubpalavra da colheita de T1. Assim, podemos decompor a colheitade T1 na forma vxy. A relação entre estas árvores e suas colheitas éilustrada na figura 1.

Entretanto, pela hipótese 2, o caminho (ao longo de C) que vai deν1 à folha tem, no máximo, k + 2 vértices (contando com a folha, queé rotulada por um terminal!). Além disso, como C é o mais longo ca-minho que vai da raiz de T a uma folha, o trecho de C que começa emν1 é o mais longo caminho em T1 entre sua raiz (que é ν1) e uma fo-lha. Portanto, T1 tem altura no máximo k + 1. Concluímos, utilizandonovamente o lema da seção 1 que, como vxy é a colheita de T1, então

|vxy| ≤ α(G)k+1 = ρ.

Isto prova (2) do enunciado do lema.Considere agora o que acontece na construção de T quando chega-

mos a ν2. Este vértice é rotulado pela variável A e a ele está associ-ada uma regra que tem A do lado esquerdo da seta. Mas suponha que,chegados a ν2, decidimos aplicar a mesma regra que aplicamos quandochegamos a ν1. Podemos fazer isto porque esta também é uma regra quetem A do lado esquerdo. Se continuarmos, vértice a vértice, copiando otrecho da árvore T hachurado na figura, teremos uma nova árvore gra-matical em G, cuja colheita é uv2xy2z. Se repetirmos este procedimento


n vezes, obteremos uma árvore cuja colheita é uvnxynz. Isto prova (3)quando n > 0.

Por outro lado, ao chegar ao vértice ν1, também podemos usar aregra associada a ν2 e continuar a construir a árvore como se fosse T2.Neste caso obteremos uma árvore T0 com menos vértices que T e comcolheita uxz, que corresponde a tomar n = 0 em (3).

Só nos resta mostrar que vy 6= ε. Mas se vy fosse igual a ε entãoa árvore T0, construída no parágrafo anterior, teria colheita igual a w,e menos folhas que T , o que contradiz a hipótese 1. Portanto, vy 6= εe provamos (1), concluindo assim a demonstração do lema do bombea-mento.

3. Exemplos

Veremos a seguir que várias das linguagens que já encontramos an-teriormente, e outras que ainda vamos encontrar à frente, não são li-vres de contexto. Antes, porém, precisamos discutir como o lema dobombeamento é utilizado para provar que uma linguagem não é livre decontexto.

Digamos que L é uma linguagem que você suspeita não ser livre decontexto. Para aplicar o lema do bombeamento a L usamos a mesmaestratégia já utilizada no caso de linguagens regulares. Assim,

(1) suporemos, por contradição, que L é gerada por uma gramáticalivre de contexto;

(2) escolheremos uma palavra w ∈ L de comprimento maior queρ;

(3) mostraremos que não há nenhuma maneira possível de decom-por w na forma do lema do bombeamento, de modo que wtenha subpalavras bombeáveis.

Com isto podemos concluir que L não é livre de contexto.É claro que, se o seu palpite estiver errado e L for livre de contexto,

então você não chegará a nenhuma contradição. Por outro lado, o fatode uma contradição não ter sido obtida não significa que L é livre decontexto.

Como no caso das linguagens regulares, a escolha da palavra em (2)depende de ρ, uma variável inteira positiva. Além disso, escolher w demaneira a obter facilmente uma contradição envolve uma certa dose detentativa e erro. Finalmente, por causa da maneira mais complicada dedecompor w, podemos ter vários casos a analisar antes de esgotar todasas possibilidades. Vejamos alguns exemplos.

3. EXEMPLOS 99

Exemplo 1. Já havíamos dito no capítulo 7 que a linguagem

Labc = {anbncn : n ≥ 0}

não é livre de contexto. Temos, agora, as ferramentas necessárias paraprovar que isto é verdade.

Suponha, por contradição, que Labc é livre de contexto. Pelo lemado bombeamento existe um inteiro positivo ρ tal que, se n > ρ, então épossível decompor w = anbncn na forma w = uvxyz, onde:

(1) vy 6= ε;(2) |vxy| ≤ ρ;(3) uvnxynz ∈ Labc para todo n ≥ 0.

Como n > ρ mas |vxy| ≤ ρ, temos que vxy não pode conter, aomesmo tempo, as, bs e cs. Digamos que vxy só contenha as e bs. Nestecaso, nem v, nem y, podem conter c, mas vy tem que conter pelo menosum a ou um b. Assim, quando n > 1 o número de as ou bs em uvnxynztem que ser maior que n, ao passo que o número de cs não foi alterado, econtinua sendo n. O caso em que vxy só contém bs e cs pode ser tratadode maneira análoga. Portanto, uvnxynz /∈ Labc o que contradiz o lemado bombeamento. Concluímos que, de fato, L não é uma linguagemlivre de contexto.

Exemplo 2. No capítulo 3 vimos que a linguagem

Lprimos = {0p : p é um primo positivo},

não é regular. Como já sabemos que há linguagens livres de contextoque não são regulares, faz sentido perguntar se esta linguagem é livre decontexto. A resposta é não.

Suponhamos, por contradição, que Lprimos seja livre de contexto.Então, de acordo com o lema do bombeamento, deve existir um inteiropositivo ρ tal que se p é um primo maior que ρ, então podemos decompor0p na forma 0p = uvxyz, onde

(1) vy 6= ε;(2) |vxy| ≤ ρ;(3) uvnxynz ∈ Lprimos para todo n ≥ 0.

Mas u, v, x, y e z são todas palavras em 0∗. Logo existem inteirosm, r, s, t ≥ 0 tais que

u = 0m, v = 0r, x = 0s, y = 0t e z = 0p−r−s−t.

Além disso, segue de (1) que r + t > 0, e de (3) que

uvnxynz = 0m(0r)n0s(0t)n0p−r−s−t = 0p+(r+t)(n−1)


pertence aLprimos para todo n > 0. Mas, para que esta última afirmaçãoseja verdadeira, os números p+ (r+ t)(n− 1) têm que ser primos paratodo n ≥ 0. Tomando n = p+ 1 temos que

p+ (r + t)(n− 1) = p(1 + r + t),

é composto, pois r + t > 0; uma contradição. Portanto, Lprimos não éuma linguagem livre de contexto.

Exemplo 3. Considere, agora, a linguagem

Lrr = {rr : s ∈ (0 ∪ 1)∗}.Já vimos no capítulo 3 que esta linguagem não é regular, queremos pro-var que também não é livre de contexto.

Suponhamos, por contradição, queLrr é livre de contexto. Aprovei-tando uma idéia já usada no capítulo 3, escolhemos w = 0m10m1 comonossa primeira tentativa. Entretanto, escolhendo ρ = 3 e decompondo0m10m1 na forma

u = 0m−1, v = 0, x = 1, y = 0 e z = 0m−11,

verificamos que todas as condições do lema do bombeamento são sa-tisfeitas. Portanto, não é possível chegar a uma contradição escolhendor = 0m1.

A saída é escolher uma palavra mais complexa. Observe que, noexemplo acima, a decomposição proposta não funcionaria se o númerode 1s também dependesse de m. Isto sugere que devemos escolher r =0m1m.

Supondo, por contradição, que Lrr é livre de contexto e escolhendow = 0m1m0m1m temos, pelo lema do bombeamento, que se m ≥ ρentão w pode ser decomposta na forma

0m1m0m1m = uvxyz

de modo que as condições (1), (2) e (3) do lema do bombeamento sejamsatisfeitas. Há dois casos a considerar.

O primeiro caso consiste em supor que vxy é uma subpalavra doprimeiro 0m1m. Escrevendo 0m1m = uvxyz′, onde z = z′0m1m, te-mos que

2m < |uv2xy2z′| ≤ 2m+ ρ.

Isto significa que yz′ foi deslocado |vxy| casas para à direita. Contudo,

|vxy| ≤ ρ ≤ me vxy2z′ acaba em m uns. Como o segundo 0m1m não foi bombeado,temos que o símbolo seguinte ao meio da palavra é 1. Em particular, seuv2xy2z = rr então o segundo r começa com 1 e o primeiro com 0, o

3. EXEMPLOS 101

que é uma contradição. O caso em que vxy é subspalavra do segundo0m1m pode ser tratado de maneira análoga.

Finalmente, resta-nos supor que vxy inclui o meio da palavra. Nestecaso, vxy tem que ser subpalavra de 1m0m, já que |vxy| ≤ ρ ≤ m.Assim, ou v contém algum 1 ou y algum 0. Removendo-os, concluímosque uxz = 0m1s0t1m, onde s ou t (ou ambos) são menores que m.Entretanto, se 0m1s0t1m = rr então r começa em 0 e acaba em 1,de forma que precisamos ter s = m = t, o que é uma contradição.Concluímos que Lrr não é livre de contexto.

Exemplo 4. Vimos na seção 4 do capítulo 7 que a união, concatenaçãoe estrela de linguagens livres de contexto também é livre de contexto.Resta-nos analisar o que acontece com a intersecção e o complementode linguagens livres de contexto.

Considere, por exemplo as linguagens

L1 = {aibjck : i, j, k ≥ 0 e i = j}, e

L2 = {aibjck : i, j, k ≥ 0 e j = k}.

Já vimos no capítulo 7 que estas duas linguagens são livres de contexto.Entretanto,

L1 ∩ L2 = {aibjck : i = j e j = k}.Em outras palavras, L1 ∩ L2 = Labc. Porém, mostramos no exemplo 1acima que esta linguagem não é livre de contexto. Assim, a intersecçãode duas linguagens livres de contexto pode não ser livre de contexto.

E quanto ao complemento? Já sabemos do capítulo 5, que existeuma maneira de relacionar o complemento e a intersecção de duas lin-guagens através da união. Como a intersecção de linguagens livres decontexto não é necessariamente livre de contexto, seria de esperar queo mesmo valesse para o complemento. Provaremos isto argumentandopor contradição.

Suponhamos, por contradição, que o complemento de linguagenslivres de contexto seja livre de contexto. Como L1 e L2 são livres decontexto, então L1 e L2 também serão. Mas a união de linguagens livresde contexto é livre de contexto. Portanto, L1 ∪ L2 é livre de contexto.Usando mais uma vez a hipótese sobre o complemento, concluímos que

(L1 ∪ L2) = L1 ∩ L2,

é livre de contexto. Entretanto já vimos que isto é falso neste caso.Portanto, o complemento de linguagens livres de contexto pode não serlivre de contexto.


Note que nossa conclusão diz apenas que a intersecção e o comple-mento de linguagens livres de contexto pode não ser livre de contexto.Isto porque, em muitos casos, estas operações produzem linguagens li-vres de contexto. Por exemplo, toda linguagem regular é livre de con-texto; e já vimos que a intersecção e o complemento de linguagens regu-lares é regular. Portanto, neste caso estamos intersectando ou tomandoo complementar de linguagens livres de contexto e obtendo como resul-tado uma linguagem do mesmo tipo. É possível aperfeiçoar este resul-tado, e mostrar que a intersecção de uma linguagem livre de contextocom uma linguagem regular é sempre livre de contexto. Mas, para fazeristo, precisamos usar os autômatos de pilha que serão introduzidos nopróximo capítulo.

4. Exercícios

1. Mostre que nenhuma das linguagens abaixo é livre de contexto usandoo lema do bombeamento.(a) {a2n : n é primo};(b) {an2

: n ≥ 0};(c) {anbncr : r ≥ n};(d) o conjunto das palavras em {a, b, c}∗ que têm o mesmo número

de as e bs, e cujo número de cs é maior ou igual que o de as;(e) {0n1n0n1n : n ≥ 0};(f) {rrr : s ∈ (0 ∪ 1)∗};(g) {wcwcw : w ∈ {0, 1}∗};(h) {0n! : n ≥ 1};(i) {0k1k0k : k ≥ 0};

CAPíTULO 12

Autômatos de Pilha

Neste capítulo começamos a estudar a classe de autômatos que aceitaas linguagens livres de contexto: os autômatos de pilha não determinís-ticos. Ao contrário dos autômatos finitos, os autômatos de pilha têmuma memória infinita. Contudo o acesso a esta memória é feito de ma-neira extremamente restrita, uma vez que o último item que foi posto namemória é obrigatoriamente o primeiro a ser consultado.

1. Heurística

Suponhamos que L é uma linguagem livre de contexto em um al-fabeto Σ. Nesta seção consideramos como construir um procedimentoque, tendo como entrada uma palavra w no alfabeto Σ, determina sew pertence ou não a L. Como sempre, assumiremos que w é lida, umsímbolo de cada vez, da esquerda para a direita.

Nossos procedimentos utilizarão uma memória infinita, em formade pilha. Para tornar o problema mais concreto, podemos imaginar queesta memória é constituída por discos perfurados ao meio, que são em-pilhados em uma haste. Os discos vêm em várias cores e temos um es-toque infinito deles. Além disso, a haste pode ser feita tão longa quantofor necessário.

Para ‘lembrar’ alguma coisa, enfiamos discos coloridos na haste.Como os discos estão trespassados pela haste, só é possível removê-losum a um, começando sempre pelo que está mais acima.

Nosso primeiro exemplo é a linguagem L1 formada pelas palavrasno alfabeto {a, b, c} que são da forma vcvR, onde v é uma palavra qual-quer nos as e bs. Por exemplo, as palavras abaacaaba e bbacabb per-tencem a L1, mas abcab e abba não pertencem. É fácil mostrar que esta

103

104 12. AUTÔMATOS DE PILHA

linguagem não é regular usando o lema do bombeamento; portanto, nãoexiste nenhum autômato finito que a aceite.

Para poder construir um procedimento que verifica se uma dada pa-lavra de {a, b, c} pertence ou não a L1 precisamos ter uma maneira de‘lembrar’ exatamente qual é a seqüência de as e bs que apareceu antesdo c. Comparamos, então, esta seqüência com a que vem depois do c.

Faremos isto usando uma pilha e duas cores diferentes de discos:preto e branco. Procedemos da seguinte forma:

Etapa 1: Se achar a empilhe um disco preto na haste, e se acharb, um disco branco.

Etapa 2: Se achar c, mude de atitude e prepare-se para desempi-lhar discos.

Etapa 3: Compare o símbolo que está sendo lido com o que estáno topo da pilha: se lê a e o topo da pilha é ocupado por umdisco preto, ou se lê b e o topo é ocupado por um disco branco,desempilhe o disco.

Este procedimento obedece ainda a uma instrução que não foi explici-tada acima, e que diz: se em alguma situação nenhuma das etapas acimapuder ser aplicada, então páre de executar o procedimento.

Por exemplo, se a palavra dada for w = abcba, o procedimento secomporta da seguinte maneira:

Acha Faz Pilha Resta na entradaa empilha disco preto • bcba

b empilha disco branco◦• cba

c muda de atitude◦• ba

b compara e desempilha • a

a compara e desempilha

Observe que a pilha registra os símbolos de w que antecedem o cde baixo para cima. Os discos da pilha, por sua vez, são comparados,de cima para baixo, com a parte da palavra que sucede o c. Assim, oreflexo da parte da palavra que antecede o c é comparado com a parte dapalavra que sucede o c. Portanto, se w ∈ L1, então todos os símbolosde w devem ter sido consumidos e a pilha deve estar vazia quando oprocedimento parar.

Por outro lado, se a palavra não está em L1 então podem aconte-cer duas coisas. A primeira é que a entrada não possa ser totalmente

2. DEFINIÇÃO E EXEMPLOS 105

consumida por falta de instruções adequadas. Isto ocorre, por exem-plo, quando a entrada é cab. A segunda possibilidade é que a entradaseja totalmente consumida, mas a pilha não se esvazie. Este é o caso,por exemplo, da entrada a2bcba. Concluímos que a entrada deverá seraceita se, e somente se, ao final da execução do procedimento ela foitotalmente consumida e a pilha está vazia.

A instrução de parar nos casos omissos faz com que o procedi-mento descrito acima seja completamente determinístico. Entretanto,nem sempre é possível criar um procedimento determinístico deste tipopara testar se uma palavra pertence a uma dada linguagem livre de con-texto. Por exemplo, a linguagem

L2 = {vvR : v ∈ {a, b}∗},

no alfabeto {a, b}, é livre de contexto.A única diferença desta linguagem paraL1 é que não há um símbolo

especial marcando o meio da palavra. Portanto, se descobrirmos comoidentificar o meio da palavra, o resto do procedimento pode ser igual aoanterior. A saída é deixar por conta de quem está executando o procedi-mento o ônus de advinhar onde está o meio da palavra. Como somenteum símbolo da palavra é visto de cada vez, a decisão acaba tendo queser aleatória. Portanto, tudo o que precisamos fazer é alterar a etapa 2,que passará a ser:

Nova etapa 2: decida (aleatoriamente) se quer mudar de atitudee passar a desempilhar os discos.

Observe que, se o procedimento determinar que a palavra dada per-tence a L2, então podemos estar seguros de que isto é verdade. Entre-tanto, como o procedimento não é determinístico, uma saída negativanão garante que a palavra não pertence a L2. Podemos apenas ter sidoinfelizes na nossa escolha de onde estaria o meio da palavra.

2. Definição e exemplos

Vamos analisar os elementos utilizados na construção destes proce-dimentos e, a partir deles, sistematizar nossa definição de autômato depilha.

Os elementos mais óbvios são: o alfabeto de entrada e a pilha. En-tretanto, em ambos os exemplos temos mudanças de atitude de empilhapara compara e desempilha. Como no caso de autômatos finitos, a ati-tude dos autômatos de pilha serão codificadas nos estados. Com istoprecisamos também de um estado inicial que indica qual é a primeira


etapa do procedimento. Finalmente, precisamos de uma função de tran-sição que nos diz o que fazer com a entrada (e a pilha!), e que sejaflexível o suficiente para codificar procedimentos não determinísticos.

Comparando a análise acima com a definição de autômato finito,verificamos que não foi necessário mencionar estados finais. Afinal, aaceitação de uma entrada pelos nossos procedimentos foi determinadapelo fato da entrada ter sido totalmente consumida e pelo esvaziamentoda pilha. Apesar disso, introduziremos a noção de estado final em nossadefinição formal, porque isto nos dá maior flexibilidade à construçãodos autômatos. Sistematizando estas considerações, obtemos a seguintedefinição.

Um autômato de pilha não determinístico M fica completamentedefinido pelos seguintes elementos:

ALFABETO DE ENTRADA: Σ;

ALFABETO DA PILHA: Γ;

CONJUNTO DE ESTADOS: Q = {q1, . . . , qn};ESTADO INICIAL: q1;

CONJUNTO DE ESTADOS FINAIS: F ⊆ Q;

FUNÇÃO DE TRANSIÇÃO: δ : Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) →Pf (Q× Γ∗).

Como no caso dos autômatos finitos, abreviaremos os elementos deum autômato finito listando-os em um vetor, sempre na ordem acima.Portanto, o autômato de pilha M que acabamos de definir tem comoelementos (Σ,Γ, Q, q1, F, δ).

Há algumas considerações que precisamos fazer sobre a função detransição definida acima. A primeira diz respeito ao seu conjunto dechegada. Se, por analogia com autômatos finitos não determinísticos,escolhêssemos este conjunto como sendo P(Q×Γ∗), abriríamos a pos-sibilidade de uma quantidade infinita de escolhas em uma transição. Istoporquê, ao contrário do que ocorria com autômatos finitos, o conjuntoQ×Γ∗ é infinito. Para evitar este problema, restringimos o conjunto dechegada a Pf (Q × Γ∗), que é o conjunto formado pelos subconjuntosfinitos de Q× Γ∗.

Voltando nossa atenção agora para o conjunto de partida da funçãode transição, note que δ toma valores em triplas formadas por um estado,um símbolo do alfabeto de entrada e um símbolo do alfabeto da pilha.Não há nada de muito surpreendente até aí, porque estamos tentandomodelar os procedimentos da seção 1, que consultam tanto a entradaquanto a pilha. Entretanto, diante destas considerações, esperaríamos


que o domínio de δ fosse Q× Σ× Γ, contudo, o que de fato obtemos é

Q× (Σ ∪ {ε})× (Γ ∪ {ε}).

Isto significa que o autômato pode efetuar uma transição sem consultara entrada ou sem consultar a pilha, ou ambos! Portanto podemos esperardestes autômatos um comportamento ainda ‘mais indeterminístico’ queo dos autômatos finitos.

Para poder enquadrar os procedimentos da seção 1 na estrutura dadefinição acima precisamos saber como interpretar o comportamentoda função de transição em termos mais concretos. Digamos que M éum autômato de pilha não determinístico cujos elementos obedecem ànotação adotada na definição de autômato de pilha não determinístico.Suponhamos que

q ∈ Q, σ ∈ Σ ∪ {ε} e γ ∈ Γ ∪ {ε}.

Dados p ∈ Q e u ∈ Γ∗, a condição

(p, u) ∈ δ(q, σ, γ),

significa que se o autômato M está no estado q, lendo o símbolo σ naentrada, e tendo γ no topo da pilha, então ao consumir σ:

• M muda para o estado p;• M troca γ por u no topo da pilha.

Além disso, se σ = ε temos que a entrada não é consultada. Já quandoγ = ε, a transição é efetuada sem que o topo da pilha seja consultado.

Note queM pode trocar o símbolo do topo da pilha por uma palavrainteira. Em termos da pilha de discos perfurados da seção anterior istosignifica que o disco do alto da pilha pode ser trocado por uma pilha devários discos em uma única transição.

O fato de u poder ser uma palavra qualquer de Γ∗ inclui a possibi-lidade de u ser ε. Mas o que significa trocar γ por ε no topo da pilha?Como ε não tem símbolos, retiramos γ e não pusemos nada no seu lugar.Portanto γ foi apenas removido da pilha.

Vale a pena enumerar os vários casos em que ε aparece para nãodeixar dúvidas quanto à interpretação correta de cada um:


Caso Interpretação

σ = ε a entrada não é consultadaγ = ε o topo da pilha não é consultadoσ = γ = ε nem a entrada, nem o topo da pilha são consultadosγ 6= ε e u = ε remove γ da pilhaγ = ε e u 6= ε empilha uγ = ε e u = ε não altera a pilha

O que vimos já é suficiente para que possamos adaptar os procedi-mentos da seção 1 ao modelo de autômato de pilha não determinístico.

Analisando o procedimento que aceita a linguagem L1, vemos quehá apenas uma mudança de atitude, que corresponde à passagem de em-pilha para desempilha. Isto significa que o autômato de pilhaM1 quedesejamos construir deve ter dois estados, digamos q1 e q2.

No primeiro estado, M1 põe um símbolo diferente na pilha paracada a ou b encontrado na entrada. Para facilitar, podemos imaginar queo alfabeto da pilha é {a, b}. Assim, para cada a achado na entrada, oautômato acrescenta um a no topo da pilha; e para cada b da entrada,um b é acrescentado ao topo da pilha. Temos assim as duas transições

δ(q1, a, ε) = {(q1, a)},δ(q2, b, ε) = {(q2, b)}.

Note o ε indicando que um símbolo é empilhado, não importando o queesteja no topo da pilha.

Por outro lado, ao achar um c na entrada M1 muda de atitude,preparando-se para passar a desempilhar. Como esta mudança de ati-tude ocorre sem que nada seja feito à pilha, temos a transição

δ(q1, c, ε) = {(q2, ε)}.Já no estado q2, o autômato passa a comparar o símbolo da entrada como que está no topo da pilha. Se os símbolos na entrada e na pilha coinci-dem, o autômato remove o símbolo que está no topo da pilha. Portanto,

δ(q2, a, a) = {(q2, ε)},δ(q2, b, b) = {(q2, ε)}.

Para completar a descrição deM1 precisamos ainda decidir sobreseu estado inicial e seus estados finais. Não há problema quanto aoestado inicial que, claramente, deve ser q1. E quanto aos estados finais?De acordo com a definição do procedimento em 1, uma palavra é aceita


quando for inteiramente consumida e a pilha estiver vazia. Mas isso sópode acontecer quando o estado final for q2. Como é razoável esperarque, se o autômato aceita a entrada, então parou em um estado final,vamos declarar q2 como sendo final.

A descrição do autômato acima seria, sem dúvida, mais fácil deinterpretar se tivéssemos uma maneira mais compacta de descrever astransições. Como no caso dos autômatos finitos, faremos isto usandouma tabela que, além da palavra de entrada e do estado, registrará o queo autômato faz à pilha.

Suponhamos que temos um autômato de pilha e que q, p1, . . . , pssão estados, σ é um símbolo do alfabeto de entrada, γ um símbolo doalfabeto da pilha e u1, . . . , us palavras no alfabeto da pilha. Uma tran-sição

δ(q, σ, γ) = {(p1, u1), . . . , (ps, us)},

corresponderá a uma entrada da seguinte forma na tabela:

estado entrada topo da pilha transições

q σ γ (p1, u1)...

(ps, us)

Observe que os diferentes pares (estado, símbolo da pilha) de umamesma transição são listados um sobre o outro sem uma linha divisória.As linhas horizontais da tabela separarão transições distintas uma daoutra. Em muitos casos é conveniente acrescentar a este modelo básicode tabela uma quinta coluna com comentários sobre o que o autômatoestá fazendo naquela transição. É claro que estes comentários não fazemparte da descrição formal do autômato de pilha, eles apenas nos ajudama entender como ele se comporta.

Utilizando esta notação, a tabela do autômatoM1 é seguinte:


estado entrada topo da pilha transições comentários

q1 a ε (q1, a) acha a e empilha a

q1 b ε (q1, b) acha b e empilha b

q1 c ε (q2, ε) acha c e muda de estado

q2 a a (q2, ε) acha a na entrada e pilhae o desempilha

q2 b b (q2, ε) acha b na entrada e pilha e odesempilha

No caso da linguagem L2 da seção 1, o procedimento que criamosera não determinístico. Por isso, para modelá-lo como um autômatode pilha precisamos dar ao autômato a capacidade de, a qualquer mo-mento, alterar o seu comportamento, deixando de empilhar e passandoa desempilhar. Assim, enquanto está no estado q1 o autômato pode terduas atitudes:

Primeira: verificar qual é o símbolo de entrada e acrescentar osímbolo correspondente ao topo da pilha; ou

Segunda: ignorar a entrada e a pilha, mudar de estado e passar adesempilhar.

Levando em conta estas considerações, obtemos um autômato de pilhaM2 que tem {a, b} como alfabeto de entrada e da pilha; estados q1 e q2;estado inicial q1, estado final q2 e função de transição dada por:


q1 a ε (q1, a) acha a e empilha a

q1 b ε (q1, b) acha b e empilha b

q1 ε ε (q2, ε) muda de estado

q2 a a (q2, ε) acha a na entrada e pilha e odesempilha

q2 b b (q2, ε) acha b na entrada e pilha e odesempilha

Observe que vale para a tabela a ressalva feita para os procedimen-tos na seção 1. Isto é, se surgir uma situação que leve a uma transiçãoque não esteja especificada na tabela, então o autômato pára de se mo-ver. Aliás, o mesmo valia para os autômatos finitos não determinísticos.

3. COMPUTANDO E ACEITANDO 111

3. Computando e aceitando

Apesar de já termos uma descrição formal dos autômatos de pilha,ainda precisamos definir de maneira precisa o que significa um autômatode pilha aceitar uma linguagem. Faremos isto adaptando as noções cor-respondentes da teoria de autômatos finitos.

Seja M um autômato de pilha cujos elementos são dados pelo vetor(Σ,Γ, Q, q1, F, δ). Uma configuração deM é um elemento deQ×Σ∗×Γ∗; ou seja, é uma tripla (q, w, u) onde

• q é um estado de M ;• w é uma palavra no alfabeto de entrada;• u é uma palavra no alfabeto da pilha.

Por uma questão de coerência com a maneira como a palavra w é lida,listamos os elementos da pilha em u de modo que o topo da pilha cor-responda ao símbolo mais à esquerda de u.

Como ocorreu com os autômatos finitos, a finalidade desta definiçãoé permitir que possamos acompanhar de maneira simples o comporta-mento de M com uma dada entrada. Portanto, esta definição só faz sen-tido quando vem conjugada à relação configuração seguinte. Suponha-mos que C = (q, σw, γu) é uma configuração deM , onde σ ∈ Σ∪{ε},γ ∈ Γ ∪ {ε}. Dizemos que C ′ = (q′, w, vu) é uma das configuraçõesseguintes a C se

(q′, v) ∈ δ(q, σ, γ).

Neste caso, escrevemos C `M C ′.Uma computação deM é uma seqüência de configuraçõesC0, · · · , Ck

tais que Ci+1 é uma das configurações seguintes a Ci. Freqüentementeabreviaremos a computação acima na forma C0 `kM Ck, já que, na mai-oria dos casos, estaremos interessados apenas nas configurações comas quais a computação começa e termina. Se o número de etapas dacomputação não for conhecido, ou não for relevante para as nossas con-siderações, escreveremos apenas C0 `∗M Ck. Usaremos ` em lugar de`M a não ser que haja risco de confusão sobre qual o autômato que estásendo considerado.

Como no caso de autômatos finitos, convencionaremos que se C éuma configuração, então C `0 C, e também C `∗ C. Note, contudo,que C `0 C não é equivalente a uma transição com entrada vazia. Porexemplo, o autômatoM2 satisfaz

(q1, ε, ε) ` (q2, ε, ε).

Mas, apesar da entrada e da pilha não terem sido alteradas, as configu-rações inicial e final não coincidem.


Vejamos estas definições em ação em alguns exemplos. Partindo daconfiguração (q1, abcba

2, a) temos a seguinte computação no autômatoM1 da seção 2:

(q1, abcba2, a) ` (q1, bcba

2, a2) ` (q1, cba2, ba2) ` (q2, ba

2, ba2) ` (q2, a2, a2) `

(q2, a, a) ` (q2, ε, ε).

Esta é, essencialmente, a única computação possível partindo de (q1, abcba2, a).

A única coisa que podemos fazer para obter uma computação diferente éinterromper a computação acima antes de chegar a (q2, ε, ε). Entretanto,isto está longe de ser sempre verdade, como mostra o exemplo seguinte.

Desta vez queremos considerar o autômato de pilhaM2 definido aofinal da seção 2. Digamos que a configuração inicial seja (q1, a

2b, ε).Uma computação possível é

(q1, a2b, ε) ` (q1, ab, a) ` (q1, b, a

2) ` (q2, b, a2).

Mas há muitas outras possibilidades, como:

(q1, a2b, ε) ` (q2, a

2b, ε)

ou ainda(q1, a

2b, ε) ` (q1, ab, a) ` (q2, ab, a).

A diferença é que o primeiro autômato era basicamente determinístico,ao passo que este último é claramente não determinístico.

Supondo, como antes, queM é um autômato de pilha cujos elemen-tos são dados pelo vetor (Σ,Γ, Q, q1, F, δ), diremos que uma palavraw ∈ Σ∗ é aceita por M se existe uma computação

(q1, w, ε) `∗ (p, ε, ε),

onde p é um estado final de M . Como já ocorria no caso de autôma-tos finitos não determinísticos, basta que exista uma computação comoacima para que a palavra seja aceita. A linguagem L(M) aceita por Mé o conjunto de todas as palavras que M aceita.

Em geral não é fácil determinar por simples inspecção qual a lingua-gem aceita por um autômato de pilha não determinístico dado. Contudo,veremos no próximo capítulo que é possível construir uma gramática li-vre de contexto que gere L(M) diretamente da descrição de M .

Observe que três condições precisam ser simultaneamente satis-feitas para que possamos afirmar, ao final de uma computação, que Maceita w:

(1) a palavra w tem que ter sido completamente consumida;(2) a pilha tem que estar vazia;(3) o autômato tem que ter atingido um estado final.

4. VARIAÇÕES EM UM TEMA 113

A condição referente ao estado final não aparece na descrição dos pro-cedimentos na seção 1. De fato, ela surgiu na definição formal de autô-mato de pilha sob a pífia justificativa de que seria razoável exigir que oautômato parasse aceitando num estado final!

Como sempre acontece, a exigência de que o autômato tenha queatingir um estado final para que a entrada seja aceita simplifica a cons-trução de alguns autômatos e complica a de outros. A verdade é que,como o exercício 7 mostra, teria sido possível suprimir toda menção aestados finais, embora isto não seja desejável do ponto de vista do de-senvolvimento da teoria.

4. Variações em um tema

Nesta seção discutimos a construção de autômatos de pilha para trêslinguagens definidas de maneira muito semelhante. Com isto teremos aoportunidade de chamar a atenção para algumas dificuldades comuns;além de desenvolver técnicas simples, mas úteis, na construção de autô-matos mais sofisticados.

Exemplo 1. Consideremos, em primeiro lugar, a linguagem livre decontexto

L = {aibi : i ≥ 0},É fácil descrever um procedimento extremamente simples que usa umapilha com apenas um tipo de disco para aceitar as palavras de L:

Etapa 1: Se achar um a na entrada, ponha um disco na pilha.Etapa 2: Se achar um b na entrada mude de atitude e passe a

comparar a entrada com a pilha, removendo um disco da pilhapara cada b que achar na entrada (incluindo o primeiro!).

Para precisar o comportamento do autômato de maneira a não deixardúvida sobre o que ele realmente faz basta construir sua tabela de tran-sição.


q1 a ε (q1, a) empilha a

q1 b a (q2, ε) desempilha a e muda de estado

q2 b a (q2, ε) desempilha a

É claro que queremos que q1 seja o estado inicial, mas precisamostomar cuidado com a escolha dos estados finais. A primeira impressãotalvez seja que q2 é o único estado final. Entretanto, o autômato só pode


alcançar q2 se houver algum símbolo na entrada, o que faria com que oautômato não aceitasse ε.

Há duas soluções possíveis. A primeira é declarar que q1 tambémé um estado final. Isto com certeza faz com que ε seja aceita. Porém,precisamos nos certificar de que a inclusão de q1 entre os estados finaisnão cria novas palavras aceitas que não pertencem a L. Fazemos istoanalisando em detalhes o comportamento do autômato. Suponhamos,então, que ε 6= w ∈ {a, b}∗ e que o autômato recebe w como entrada.Temos que:

• se w começa por b então nenhum de seus símbolos é consu-mido;• sew começa por a então os as são empilhados e para desempilhá-

los é preciso chegar ao estado q2.

No primeiro caso a palavra não será aceita; no segundo, só será aceitase os as são seguidos pelo mesmo número de bs e nada mais. Ou seja,se declaramos que os estados finais são {q1, q2} então o autômato resul-tante aceita L.

A segunda possibilidade é alterar as transições e dar ao autômato aalternativa de, sem consultar a entrada ou a pilha, mudar de estado deq1 para q2. Neste caso, o único estado final é {q2}. Além disso, a tran-sição que vamos acrescentar torna completamente redundante a terceiralinha da tabela acima. A tabela que descreve a função de transição doautômato passa, então, a ser:


q1 ε ε (q2, ε) muda de estado

q1 a ε (q1, a) empilha a

q2 b a (q2, ε) desempilha a

O problema com esta última estratégia é que a transição que acres-centamos pode ser executada enquanto o autômato está no estado q1,não importando o que está sendo lido, nem o que há na pilha. Para tercerteza que tudo ocorre como esperado, devemos analisar o que o autô-mato faria se usasse esta transição “no momento errado”. Em primeirolugar, se o autômato está no estado q1 então ele não pode se mover aoler b, a não ser que ignore a entrada e mude para o estado q2. Portanto,o autômato se comportará de maneira anómala apenas se ainda estiverlendo a e executar a transição que permite mudar de estado sem afetar aentrada nem a pilha. Neste caso ainda haveria as a serem lidos. Comoo autômato não se move se está no estado q2 e lê a, então a computação


simplesmente pára. A conclusão é que o autômato continua aceitando oque devia apesar da alteração na tabela de transição.

Exemplo 2. A linguagem deste segundo exemplo é uma generalizaçãoda que aparece no primeiro. Seja L a linguagem formada pelas pala-vras w ∈ {a, b} para as quais o número de as e bs é o mesmo. Assim,abaaabbabb ∈ L, mas aaabaa /∈ L. Observe que a linguagem do exem-plo anterior está contida em L.

À primeira vista, podemos construir um autômato de pilha que aceiteL usando a mesma estratégia do Exemplo 1. Isto é, quando achamos aempilhamos a e quando achamos um b desempilhamos um a. O pro-blema é o que fazer quando nos deparamos com uma palavra como abba.Neste caso começaríamos empilhando um a, mas em seguida teríamosde desempilhar dois as. Só que há apenas um a na pilha: como seriapossível desempilhar mais as do que há na pilha?

A estratégia que vamos adotar consiste em construir um contadorque:

• ao achar a soma 1 ao contador;• ao achar b soma −1 ao contador.

Poderíamos fazer isto usando {−1, 1} como alfabeto da pilha, entre-tanto, palavras como −1 − 1 estão demasiadamente sujeitas a causarconfusão. Por isso, vamos simplesmente empilhar a para cada a encon-trado na entrada, e b para cada b encontrado na entrada. Só precisamoslembrar que ‘empilhar um b sobre um a’ tem o efeito de desempilhar ob da pilha, e vice-versa.

O que ocorre quando aplicamos esta estratégia à palavra abba? Oprimeiro a contribui um a para a pilha, que por sua vez é removido pelob seguinte. Portanto, depois de ler o prefixo ab o autômato está com apilha vazia. Em seguida aparece um b e o autômato põe um b na pilha.Este b é seguido por um a. Portanto teríamos que acrescentar um a notopo da pilha. Mas isto tem o efeito de desempilhar o b anterior, e apilha acaba vazia, como desejado.

Parece fácil transcrever esta estratégia em uma tabela de transição,mas ainda há um obstáculo a vencer antes de podermos fazer isto. Afi-nal, para que esta estratégia funcione o autômato precisa ser capaz dedetectar que a pilha está vazia. Entretanto, escrever ε para o topo dapilha em uma tabela de transição não significa que a pilha está vazia;significa apenas que o autômato não precisa saber o que está no topo dapilha ao realizar esta transição.

A saída é inventar um novo símbolo β para o alfabeto da pilha. Estesímbolo é acrescentado à pilha ainda vazia, no início da computação.


Daí em diante, o autômato opera apenas com as e bs na pilha. Assim,ao avistar β no topo da pilha o autômato sabe que a pilha não contémmais nenhum a ou b. Para garantir que β só vai ser usado uma vez,convém reservar ao estado inicial apenas a ação de marcar o fundo dapilha. Portanto, se q1 for o estado inicial teremos

δ(q1, ε, ε) = {(q2, β)}.

Ao final desta transição, a entrada não foi alterada, o fundo da pilhafoi marcado e o autômato saiu do estado q1 para onde não vai podermais voltar. O que o autômato deve fazer no estado q2 está descritoresumidamente na seguinte tabela:

Acha na entrada Acha na pilha Faza β ou a empilha ab β ou b empilha bb a desempilha aa b desempilha b

Com isto se, ao final da computação, a pilha contém apenas o mar-cador β então a palavra está em L e é aceita; do contrário a palavra érejeitada. Entretanto, pela definição formal, dada na seção 3, o autô-mato só pode aceitar a palavra se a pilha estiver completamente vazia.Isto sugere que precisamos de mais uma transição para remover o β dofundo da pilha.

Com isto surge um novo problema. Se a palavra está em L, en-tão será totalmente consumida deixando na pilha apenas β. Portanto, atransição que remove o β ao final desta computação, e esvazia comple-tamente a pilha, não tem nenhuma entrada para consultar. O problema éque se permitimos ao autômato remover β sem consultar a entrada, elepode realizar este movimento no momento errado, antes que a entradatenha sido consumida. Como os nossos autômatos são não determinísti-cos, isto não apresenta nenhum problema conceitual.

Infelizmente o fato de ainda haver símbolos na entrada abre a pos-sibilidade do autômato continuar a computação depois de ter retirado omarcador do fundo. Para evitar isto, o autômato deve, ao remover β,passar a um novo estado q3 a partir do qual não há transições. Assim, seo autômato decidir remover o marcador antes da entrada ser totalmenteconsumida ele será obrigado a parar, e não poderá aceitar a entrada nestacomputação. Como a pilha só vai poder se esvaziar em q3, é claro queeste será o único estado final deste autômato.


Resumindo, temos um autômato que tem {a, b} como alfabeto deentrada e da pilha; estados q1, q2 e q3; estado inicial q1; estado final q3;e cuja função de transição é definida na tabela 1.


q1 ε ε (q2, β) marca o fundo da pilha

q2 a β (q2, aβ) acha a e empilha um a

q2 b β (q2, bβ) acha b e empilha um b

q2 a a (q2, aa) acha a e empilha um a

q2 b b (q2, bb) acha b e empilha um b

q2 b a (q2, ε) desempilha um a

q2 a b (q2, ε) desempilha um b

q2 ε β (q3, ε) esvazia a pilha

TABELA 1

Exemplo 3. A terceira linguagem que desejamos considerar é o con-junto das palavras w ∈ {a, b} que têm mais as que bs. Vamos chamá-lade L3. À primeira vista, pode parecer que autômato é essencialmenteigual ao anterior, bastando alterar a condição sob a qual a palavra éaceita. Afinal, se ao final da computação do autômato do Exemplo 2sobram as na pilha, então a palavra de entrada tem mais as que bs. Massurgem alguns problemas técnicos quando tentamos implementar estaestratégia.

A primeira dificuldade é que não temos como codificar nas transi-ções o fato de não haver mais símbolos na entrada. A saída é permitirque o autômato tente advinhar isto por conta própria. Assim, ao acharum a na pilha, o autômato deve poder decidir que a computação chegouao fim e, sem consultar a entrada, passar a um estado final. Natural-mente uma palavra não será aceita se a decisão de aplicar esta transiçãofor tomada antes que a entrada tenha sido completamente consumida.

A segunda dificuldade é que estamos identificando que uma palavraestá em L3 porque sobram as na pilha. Entretanto, um dos requisitospara que uma palavra seja aceita por um autômato de pilha é que nãosobrem símbolos na pilha ao final da computação! Resolvemos esteconflito fazendo com que, ao chegar ao estado final, o autômato possaesvaziar a pilha sem se preocupar com a entrada.

Tomando por base o autômato do Exemplo 2, teremos que substi-tuir a transição codificada na última linha da tabela, e acrescentar as três


transições que permitem ao autômato esvaziar a pilha. O autômato re-sultante terá alfabetos de entrada e da pilha iguais a {a, b}; estados q1,q2 e q3; estado inicial q1; estado final q3; e sua função de transição serádada na tabela 2.



q2 a β (q2, aβ) empilha um a

q2 b β (q2, bβ) empilha um b

q2 a a (q2, aa) empilha um a

q2 b b (q2, bb) empilha um b

q2 b a (q2, ε) desempilha um a

q2 a b (q2, ε) desempilha um b

q2 ε a (q3, a) decide que a computação acaboucom as sobrando na pilha

q3 ε a (q3, ε) retira a da pilha

q3 ε b (q3, ε) retira b da pilha

q3 ε β (q3, ε) retira β da pilha

TABELA 2

5. Exercícios

1. Considere o autômato de pilha não determinísticoM com alfabetosΣ = {a, b} e Γ = {a}, estados q1 e q2, estado inicial q1 e final q2 etransições dadas pela tabela:

estado entrada topo da pilha transições

q1 a ε (q1, a)

(q2, ε)

q1 b ε (q1, a)

q2 a a (q2, ε)

q2 b a (q2, ε)

(a) Descreva todas as possíveis seqüências de transições de M naentrada aba.

(b) Mostre que aba, aa e abb não pertencem a L(M) e que baa, babe baaaa pertencem a L(M).

5. EXERCíCIOS 119

(c) Descreva a linguagem aceita porM em português.

2. Ache um autômato de pilha não determinístico cuja linguagem aceitaé L onde:(a) L = {anbn+1 : n ≥ 0};(b) L = {anb2n : n ≥ 0};(c) L = {w ∈ {0, 1}∗ : w cujo número de as é diferente do de bs};(d) L = {anbm : m,n ≥ 0 e m 6= n};(e) L = {w1cw2 : w1, w2 ∈ {a, b}∗ e w1 6= wr2};

3. Um autômato finito não determinístico que aceita a linguagem deno-tada por 0 · 0∗ · 1 · 0 não pode ter menos de 4 estados. Construa umautômato de pilha não determinístico com apenas 2 estados que aceitaesta linguagem.

4. Considere a linguagem dos parênteses balanceados descrita no exer-cício 2 da lista 4.(a) Dê exemplo de uma gramática livre de contexto que gere esta

linguagem.(b) Dê exemplo de um autômato de pilha não determinístico que

aceita esta linguagem.

5. Esta questão trata da existência ou inexistência de computações infi-nitas.(a) Explique porque um autômato finito (determinístico ou não) não

admite uma computação com um número infinito de etapas.(b) Dê exemplo de um autômato de pilha não determinístico que ad-

mite uma computação com um número infinito de etapas.

6. Seja M um autômato de pilha. Mostre como definir a partir de M umnovo autômato de pilha Ms que aceita a mesma linguagem que M eque, além disso, satisfaz às seguintes condições:(a) a única transição deMs a partir do seu estado inicial i é δ(i, ε, ε) ={(q, β)}, onde q é um estado, β um símbolo do alfabeto da pilhae δ a função de transição deMs;

(b) o único estado deMs a partir do qual há transições sem consultara pilha é i;

(c) Ms tem um único estado final f ;(d) as transições que desempilham β levam o autômato ao estado f ;(e) não há transições a partir de f .

7. Construa uma autômato de pilha não determinístico que aceite o com-plementar da linguagem

L = {wwR : w ∈ (0 ∪ 1)∗}.


8. Seja M um autômato de pilha não determinístico com alfabeto deentrada Σ, estado inicial q1 e conjunto de estados Q. A linguagemque M aceita por pilha vazia é definida como:

N(M) = {w ∈ Σ∗ : existe (q1, w, ε) `∗ (q, ε, ε) onde q ∈ Q}.

Note que a diferença entre L(M) e N(M) é que, para a palavra seraceita em L(M) tem que ser possível chegar a uma configuração(q, ε, ε) em que q é um estado final, ao passo que não há restriçõessobre o estado no caso de N(M).(a) Dê exemplo de um autômato de pilha não determinístico M para

o qual N(M) 6= L(M).(b) Mostre que dado um autômato de pilha não determinístico M

existe um autômato de pilha não determinísticoM ′ tal queL(M) =N(M ′).

(c) Mostre que dado um autômato de pilha não determinístico Mexiste um autômato de pilha não determinísticoM ′ tal queN(M) =L(M ′).

SUGESTÃO: use o autômato Ms construído no exercício anterior.

Resolução do Exercício 7

O autômato tem alfabeto de entrada {0, 1}, alfabeto da pilha {β, 0, 1},conjunto de estados {q1, . . . , q4}, estado inicial q1, estado final q4 e a se-guinte tabela de transição:

5. EXERCíCIOS 121



q2 0 ε (q2, 0) empilha 0

q2 1 ε (q2, 1) empilha 1

q2 ε ε (q3, 0) tenta advinhar o meio da entrada

q3 0 0 (q3, ε) desempilha 0s casados

q3 1 1 (q3, ε) desempilha 1s casados

q3 0 1 (q4, ε) acha símbolo descasado

q3 1 0 (q4, ε) acha símbolo descasado

q4 0 0 (q4, ε) continua a desempilhar




q4 ε β (q4, ε) esvazia a pilha

Depois de marcar o fundo da pilha o autômato empilha 0s e 1s atédecidir, de maneira não determinística, que o meio da palavra de entradafoi encontrado. Então, muda de estado e passa a desempilhar em buscade um símbolo da pilha que não corresponda ao que está vendo na en-trada. Ao achar um tal símbolo o autômato muda para o estado final eesvazia a pilha, comparando-a símbolo a símbolo com a entrada. Pre-cisamos fazer isto para ter certeza de que o autômato advinhou o meioda palavra corretamente. Se não sobrarem nem 0s, nem 1s na pilha, oautômato remove o marcador do fundo e esvazia a pilha.

Note que, se o autômato advinhar incorretamente o meio da palavra,então sobrarão símbolos na entrada (se advinhar cedo demais) ou napilha (se advinhar tarde demais). Em nenhum destes casos a palavraserá aceita. Um destes casos ocorrerá obrigatoriamente se a palavrativer comprimento ímpar. Finalmente, se a palavra da entrada estiver emL e se o autômato advinhar corretamente onde está o meio da palavraentão a entrada será consumida e todos os 0s e 1s serão removidos dapilha. Entretanto, como o autômato continua no estado q3 o marcador dofundo da pilha não é removido, de modo que a pilha não será esvaziadae a palvra será não será aceita.

CAPíTULO 13

Gramáticas e autômatos de pilha

Nosso objetivo neste capítulo é dar uma demonstração do seguinteresultado fundamental.

TEOREMA 13.1. Uma linguagem é livre de contexto se, e somentese, é aceita por algum autômato de pilha não determinístico.

Como uma linguagem é livre de contexto se for gerada por umagramática livre de contexto, o que precisamos fazer é estabelecer umelo entre gramáticas livres de contexto e autômatos de pilha.

Já temos alguma experiência com este tipo de questão. De fato, pro-vamos que uma linguagem gerada por uma gramática linear à direita éregular construindo um autômato finito cujas computações simulam de-rivações na gramática dada. No caso de linguagens livres de contexto acorrespondência será entre computações no autômato de pilha e deriva-ções mais à esquerda na gramática.

Como no caso das linguagens regulares o problema pode ser divi-dido em dois. Assim, dada uma gramática livre de contexto G precisa-mos de uma receita para construir um autômato de pilha não determi-nístico que aceite L(G). Reciprocamente, dado um autômato de pilhaM queremos construir uma gramática livre de contexto que gere a lin-guagem aceita porM.

1. O autômato de pilha de uma gramática

Seja G uma gramática livre de contexto. Nosso objetivo nesta seçãoconsiste em construir um autômato de pilha cujas computações simulemas derivações à esquerda em G. É claro que a pilha tem que desempenharum papel fundamental nesta simulação. O que de fato acontece é que o

123

124 13. GRAMÁTICAS E AUTÔMATOS DE PILHA

papel dos estados é secundário, e a simulação se dá na pilha. Dizendode outra maneira, construiremos um autômato de pilha que simula napilha as derivações mais à esquerda em G.

Digamos que a gramática livre de contexto G é definida pela quá-drupla de elementos (T, V, S,R), e seja M o autômato de pilha a serconstruído a partir de G. ComoM deve aceitar L(G), é claro que seualfabeto de entrada tem que ser T . Chamaremos a função de transiçãodeM de δ e seu estado inicial de i.

A maneira mais concreta de pôr em prática a idéia delineada acimaconsiste em escolher o alfabeto da pilha como sendo T ∪V , e fazer cor-responder a cada derivação de G uma transição do autômato. Entretanto,como a derivação de palavras de L(G) é feita a partir do símbolo inicialS, o autômato deve começar pondo este símbolo no fundo da pilha. Ob-serve que o autômato não pode consumir entrada ao marcar o fundo dapilha, já que precisamos da entrada para guiá-lo na busca da derivaçãocorreta. Nem adianta consultar a pilha, já que ainda está totalmente va-zia. Entretanto, uma transição que não consulta a entrada nem a pilhapode ser executada em qualquer momento da computação. Por isso for-çamos o autômato a mudar de estado depois desta transição, impedindoassim que volte a ser executada. Temos, então, que

δ(i, ε, ε) = {(f, S)},onde f é um estado do autômato diferente de i.

Daí em diante toda a ação vai se processar na pilha, e podemos si-mular a derivação sem nenhuma mudança de estado adicional. Portanto,f será o estado final deM. Assim, à regra X → α de G fazemos cor-responder a transição

(1.1) (f, ε, α) ∈ δ(f,X)

deM. Contudo, a construção do autômato ainda não está completa. Oproblema é queM só pode aplicar uma transição como (1.1) se a variá-vel X estiver no topo da pilha. Infelizmente isto nem sempre acontece,como ilustra o exemplo a seguir.

Suponhamos que G1 é a gramática com terminais {a, b, c}, variável{S}, símbolo inicial S, e regras

S → Sc |aSb | ε.

De acordo com a discussão acima o autômatoM1 correspondente a G1deve ter {a, b, c} como alfabeto de entrada, {a, b, c, S} como alfabetoda pilha e conjunto de estados {i, f}, onde i é o estado inicial e f oestado final. Lembrando que a cada regra de G1 deve corresponder umatransição deM1, concluímos que a tabela resultante deve ser

1. O AUTÔMATO DE PILHA DE UMA GRAMÁTICA 125

Estado Entrada Topo da pilha Transição

i ε ε (f, S)

f ε S (f, Sc)

(f, aSb)

(f, ε)

A palavra abc2 tem derivação mais à esquerda

S ⇒ Sc⇒ Sc2 ⇒ aSbc2 ⇒ abc2

em G1. Resta-nos verificar se somos capazes, ao menos neste exemplo,de construir uma computação deM1 que copie na pilha esta derivaçãode abc2. A computação deve começar marcando o fundo da pilha comS e deve prosseguir, a partir daí, executando, uma a uma, as transiçõesdeM1 que correspondem às regras aplicadas na derivação acima. Istonos dá(1.2)(i, abc2, ε) ` (f, abc2, S) ` (f, abc2, Sc) ` (f, abc2, Sc2) ` (f, abc2, aSbc2).

Até aqui tudo bem, mas a transição seguinte deveria substituir S por ε.Só que para isto ser possível a variável S tem que estar no topo da pilha,o que não acontece neste caso. Observe, contudo, que o a que apareceuna pilha acima do S na última configuração de (1.2) corresponde ao pri-meiro símbolo da palavra de entrada. Além disso, como se trata de umaderivação mais à esquerda, este símbolo não será mais alterado. Con-cluímos que, como o primeiro símbolo da palavra já foi corretamentederivado, podemos ‘esquecê-lo’ e partir para o símbolo seguinte. Paraimplementar isto na prática basta apagar da pilha os terminais que pre-cedem a variável mais à esquerda da pilha e que já foram corretamenteconstruídos. Isto significa acrescentar à tabela acima transições que per-mitam apagar terminais que apareçam simultaneamente na entrada e napilha:


f a a (f, ε)

f b b (f, ε)

f c c (f, ε)

Levando isto em conta a computação acima continua, a partir daúltima configuração de (1.2) da seguinte maneira(1.3)(f, abc2, aSbc2) ` (f, bc2, Sbc2) ` (f, bc2, bc2) ` (f, c2, c2) ` (f, c, c) ` (f, ε, ε).


Observe que a passagem da segunda para a terceira configuração em(1.3) corresponde à regra S → ε. Todas as outras etapas são aplicaçõesdas transições da segunda tabela.

2. A receita e mais um exemplo

Podemos agora descrever de maneira sistematica a receita usadapara construir um autômato de pilha não determinísticoM cuja lingua-gem aceita éL(G). Se a gramática livre de contexto G tem por elementos(T, V, S,R), então o autômato ficará completamente determinado pelosseguintes os elementos:

• o alfabeto de entrada T ;• o alfabeto da pilha T ∪ V ;• o conjunto de estados {i, f};• o estado inicial i;• o conjunto de estados finais {f};• a função de transição

δ : {i, f} × (T ∪ {ε})× (T ∪ V ∪ {ε})→ {i, f} × (T ∪ V )∗

que é definida por

δ(q, σ, γ) =

(f, S) se q = i e σ = γ = ε

{(f, u) : onde X → u é regra de G} se q = f e γ = X ∈ V(f, ε) se q = f e σ = γ ∈ T

Este autômato executa dois tipos diferentes de transição a partir doestado f . As primeiras permitem substituir uma variável X no topo dapilha por u ∈ (T ∪ V )∗ quando X → u é uma regra se G, e serãochamadas substituições. As segundas permitem remover terminais queaparecem casados na pilha e na entrada, e vamos chamá-las remoções.Observe que, em geral, este autômato terá um comportamento muitopouco determinístico porque cada uma de suas transição correspondeao conjunto de todas as regras que têm uma mesma variável do ladodireito.

Vejamos mais um exemplo de autômato de pilha construído a partirde uma gramática livre de contexto pela receita acima. Considere a

2. A RECEITA E MAIS UM EXEMPLO 127

gramática G′exp, definida no capítulo 9, cujas regras são

E → E + T | T

T → T ∗ F | F

F → (E) | id.

O alfabeto de entrada do autômato de pilhaM′exp correspondente a estagramática é {id,+, ∗, (, )}, o alfabeto da pilha é {id,+, ∗, (, ), E, T, F},os estados são {i, f}, o estado inicial é i, o estado final é f e a funçãode transição é definida pela tabela 1.


i ε ε (f, S)

f ε E (f,E + T )

(f, T )

f ε T (f, T ∗ F )

(f, F )

f ε F (f, (E))

(f, id)

f ( ( (f, ε)

f ) ) (f, ε)

f + + (f, ε)

f ∗ ∗ (f, ε)

f id id (f, ε)

TABELA 1. Tabela de transição

Quando criamos a receita acima, nosso objetivo era inventar umautômato que aceitasse a linguagem gerada por uma gramática livre decontexto dada. Mas para ter certeza de que a receita funciona precisamosprovar o seguinte resultado.

Se G é uma gramática livre de contexto eM é o autô-mato de pilha não determinístico construído de acordocom a receita acima, então L(G) = L(M).

A demonstração deste resultado consiste em formalizar a relaçãoentre derivações mais à esquerda em G e computações emM, que foio nosso ponto de partida para a criação da receita. Antes de fazer isto,porém, vale a pena tentar equiparar cada etapa de uma derivação mais à


esquerda em G′exp com uma computação no autômato que acabamos dedescrever. Por exemplo, vamos construir a computação correspondenteà derivação mais à esquerda

E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + F ⇒ id + id

e compará-las passo-a-passo. A derivação começa marcando o fundo dapilha com o símbolo inicial de G′exp

(i, id + id, ε) ` (f, id + id, E),

mas isto não corresponde a nenhuma etapa da derivação. Em seguida,utilizando transições por substituição, reproduzimos na pilha as quatroprimeiras etapas da derivação

(f, id+id, E) ` (f, id+id, E+T ) ` (f, id+id, T+T ) ` (f, id+id, F+T ) `(f, id + id, id + T ).

Neste ponto nos deparamos com a necessidade de usar remoções paraeliminar os terminais que obstruem o topo da pilha:

(f, id + id, id + T ) ` (f,+id,+T ) ` (f, id, T ).

A computação prossegue com a aplicação de mais duas substituições ea remoção do último terminal na pilha e na entrada:

(f, id, T ) ` (f, id, F ) ` (f, id, id) ` (f, ε, ε).

Como era esperado, o número de passos na computação excede emmuito o número de etapas da derivação por causa das transições de re-moção, que não correspondem a nenhuma regra de G′exp. Observe que émuito fácil determinar se um passo da computação corresponde ou nãoa uma etapa da derivação; isto é, a uma transição por substituição. Defato, estas transições só podem ser aplicadas a configurações nas quaishá uma variável no topo da pilha. Esta observação vai desempenhar umpapel importante na demonstração de que nossa receita funciona.

3. Provando a receita

Como sempre a demonstração pode ser dividida em duas partes, quecorrespondem às inclusões L(G) ⊆ L(M) e L(G) ⊇ L(M).

Seja G é uma gramática livre de contexto formada pelos elementos(T, V, S,R) e seja w uma palavra gerada por G. Queremos mostrar quew é aceita porM. Suponhamos que conhecemos uma derivação mais àesquerda S ⇒∗ w em G. Devemos ser capazes de usar esta derivaçãopara obter uma computação

(i, w, ε) `∗ (f, ε, ε).

3. PROVANDO A RECEITA 129

Além disso, sabemos que cada etapa desta computação deve correspon-der a uma etapa da derivação, ou à aplicação de uma das transições porremoção, que apagam os prefixos de terminais que já tenham sido cor-retamente gerados na pilha deM.

Digamos que, depois de k etapas, a derivação seja

S ⇒k αXv,

onde estamos assumindo que α ∈ T ∗ e que X ∈ V . Em particular, Xé a variável mais à esquerda de αXv. Isto significa, por um lado, que wdeve ser da forma αβ, para alguma palavra β ∈ T ∗, e por outro que apróxima regra deve ser aplicada à variável X .

Se imaginarmos que já construímos a computação passo-a-passo atéeste ponto, devemos ter obtido

(i, w, ε) ` (f, w, S) `∗ (f, β,Xv),

porque os terminais de α foram sendo eliminados na mesma medida emque foram produzidos, para que a computação pudesse avançar.

Suponhamos que a regra aplicada na próxima etapa da derivaçãoseja X → u, onde u ∈ (T ∪ V )∗. Avançando mais esta etapa na deriva-ção, obtemos

S ⇒k αXv ⇒ αuv.

Queremos reproduzir esta etapa na computação deM. Como já chega-mos a um ponto em queX está no topo da pilha, basta aplicar a transição(f, u) ∈ δ(f, ε,X), que nos dá

(i, w, ε) ` (f, w, S) `∗ (f, β,Xv) ` (f, β, uv).

Contudo isto não basta, porque queremos deixar a variável mais à es-querda de uv à descoberto, para poder aplicar a próxima regra sem obs-táculos. Para isto precisamos localizar onde está esta variável, que va-mos batizar de Y . Digamos que uv = γY v′, onde γ ∈ T ∗. Como

αuv = αγY v′ ⇒ w = αβ.

e γ só tem terminais, podemos concluir que γ é prefixo de β. Portanto,β = γβ′ e usando as regras de eliminação obtemos a computação

(i, w, ε) `∗ (f, β, uv) = (f, γβ′, γY v′) `∗ (f, β′, Y v′),

o que nos deixa prontos para prosseguir com a construção da computa-ção exatamente como fizemos na etapa anterior.

Note que, continuando desta maneira, quando chegarmos ao final daderivação teremos obtido uma computação

(i, w, ε) `∗ (f, ε, ε),

demonstrando, portanto, que w ∈ L(M).


Provamos, assim, que L(G) ⊆ L(M), falta mostrar que a inclusãooposta também vale. Para isto, basta verificar que se w é aceita porMentão existe uma derivação S ⇒∗ w.

A primeira impressão talvez seja de que, como a pilha de M re-produz uma derivação de w em G, deve ser suficiente olhar para o quehá na pilha em cada etapa da computação. Contudo, por causa das re-gras de remoção, cada vez que uma parte de w for gerada na pilha, elaserá apagada antes da computação poder continuar. Portanto, para obtera etapa da derivação que corresponde a um dado passo da computaçãobasta concatenar o prefixo de w que foi removido da entrada com o con-teúdo da pilha. Em outras palavras, se a configuração de M em umadada etapa da computação for (f, u, Y v) e w = αu, então a etapa cor-respondente da computação será αY v.

O problema desta correspondência é que mais de uma etapa da com-putação pode corresponder a uma única etapa da derivação. Para evitaristo só vamos construir as etapas da derivação que correspondem a umpasso da computação em que há uma variável no topo da pilha. Noteque escolhemos estes passos porque é exatamente neles que se aplicamas transições por substituição.

Para concluir a demonstração precisamos nos convencer de que estaseqüência de palavras de (T ∪V )∗ é de fato uma derivação de w a partirde S. Há três coisas a verificar:

(1) a seqüência começa com S;(2) para passar de uma palavra da seqüência para a próxima tro-

camos sua variável mais à esquerda pelo lado direito de umaregra de G;

(3) a última palavra da seqüência é w.

Mas (1) e (2) são conseqüências imediatas da maneira comoM foi de-finido, e (3) segue do fato de que a computação acaba na configuração(f, ε, ε). Provamos, portanto, que w ∈ L(G).

4. Autômatos de pilha cordatos

Na próxima seção consideramos a recíproca do problema descritona seção anterior. Isto é, descrevemos um algoritmo que, a partir de umautômato de pilhaM constrói uma gramática livre de contexto G tal queL(G) = L(M).

Para tornar a construção da gramática a partir do autômato maisfácil, começaremos transformando o autômato de pilha não determinís-ticoM dado. Construiremos a partir deM um autômato de pilhaM′que aceita a mesma linguagem queM, mas cujo comportamento é mais

4. AUTÔMATOS DE PILHA CORDATOS 131

predizível. Em particular, M′ terá apenas um estado final e a pilha sópoderá se esvaziar neste estado.

Para melhor sistematizar os algoritmos é conveniente introduzir anoção de um autômato de pilha cordato. Seja N um autômato de pilhacom estado inicial i e função de transição δ. Dizemos que N é cordatose as seguintes condições são satisfeitas:

(1) a única transição a partir de i é δ(i, ε, ε) = {(q, β)}, onde q éum estado de N e β é um símbolo do alfabeto da pilha;

(2) N tem um único estado final f ;(3) a pilha só se esvazia no estado final f ;(4) não há transições a partir de f .

Note que por causa de (1), (3) e (4), há um elemento β ∈ Γ quenunca sai do fundo da pilha até que o estado final seja atingido. Alémdisto, (3) nos diz que se δ(q, σ, β) = (p, ε) então p = f .

Vejamos como é possível construir a partir de um autômato de pilhaM qualquer um autômato de pilha cordato N que aceita L(M). Supo-nhamos queM é definido pelos ingredientes (Σ,Γ, Q, q1, F, δ). EntãoN será o autômato de pilha com os seguintes ingredientes:

• alfabeto de entrada Σ;• alfabeto da pilha Γ ∪ {β}, onde β /∈ Γ;• conjunto de estados Q ∪ {i, f}, onde i, f /∈ Q;• estado inicial i;• conjunto de estados finais {f};• função de transição δ′ definida de acordo com a tabela abaixo:

estado entrada topo da pilha transição

i ε ε (q1, β)

q 6= i, f e q /∈ F σ γ δ(q, σ, γ)

q 6= i, f e q ∈ F σ γ 6= ε δ(q, σ, γ)

q 6= i, f e q ∈ F ε β δ(q, ε, ε) ∪ {(f, ε)}

onde estamos supondo que σ ∈ Σ∪{ε} e que γ ∈ Γ∪{ε}.É claro que N é cordato; falta apenas mostrar que L(N ) = L(M).

Observe que o comportamento de N pode ser descrito suncintamentedizendo que, depois de marcar o fundo da pilha com β, o autômato si-mula o comportamento deM. De fato, na primeira transição N apenaspõe β no fundo da pilha e passa ao estado q1 deM. A partir daí N secomporta como M até que um estado final p de M é atingido. Nestecaso, se a pilha contém apenas β, N tem a opção de entrar no estado f


e esvaziar a pilha. Observe que a pilha só é esvaziada no estado f , e istoobriga o autômato a parar porque não existem transições a partir de f .

Suponha agora queN computa a partir de uma entrada w ∈ Σ∗. Sew for aceita porM, então existirá uma computação

(q1, w, ε) `∗ (p, ε, ε) em M.

Esta computação dará lugar a uma computação em N da forma

(i, w, ε) ` (q1, w, β) `∗ (p, ε, β) ` (f, ε, ε).

Portanto se w for aceita porM será aceita por N .Por outro lado, uma computação

(4.1) (i, w, ε) `∗ (f, ε, ε),

implica que a configuração do autômato N anterior à última tinha queser (p, ε, β), com p um estado final deM. Assim, a computação (4.1)de N procede ao longo das seguintes etapas

(i, w, ε) ` (q1, w, ε) `∗ (p, ε, β) ` (f, ε, ε).

Temos assim que (q1, w, ε) `∗ (p, ε, ε) é uma computação válida deM.Como p é estado final deM concluímos quew é aceita porM. PortantoM e N aceitam exatamente as mesmas palavras.

5. A gramática de um autômato de pilha

Suponha agora que N é um autômato de pilha cordato. Veremoscomo é possível construir uma gramática livre de contextoG que gera aspalavras aceitas porN . Digamos queN está definido pelos ingredientes(Σ,Γ, Q, i, {f}, δ). Além disso, suporemos que β é o símbolo que ficano fundo da pilha de N enquanto ele simulaM.

Naturalmente os terminais da gramática G serão os elementos deΣ. A construção das variáveis é mais complicada. Cada variável seráindexada por três símbolos: dois estados e um símbolo da pilha. Comoisto complica muito a notação é preferível identificar cada variável coma própria tripla que lhe serve de índice. Assim o conjunto de variáveisde G será

Q× Γ×Q.Portanto uma variável de G será uma tripla (q, γ, p), onde q e p sãoestados de N e γ é um símbolo do alfabeto da pilha. Note que γ nãopode ser ε.

Seδ(i, ε, ε) = {(i′, β)},

5. A GRAMÁTICA DE UM AUTÔMATO DE PILHA 133

então o símbolo inicial de G será (i′, β, f). Precisamos agora construiras regras de G. Suponhamos que

(p, u) ∈ δ(q, σ, γ)

onde u ∈ Γ∗. Há dois casos a considerar:Primeiro caso: u = γ1 · · · γk.

Neste caso, para cada k-upla (r1, . . . , rk) ∈ Qk contruímosuma regra

(q, γ, rk)→ σ(p, γ1, r1)(r1, γ2, r2) · · · (rk−1, γk, rk).

Observe que isto nos dá, não apenas uma, mas nk regras dis-tintas, onde n é o número de estados de N .

Segundo caso: u = εNeste caso construímos apenas a regra

(q, γ, p)→ σ.

De nossa experiência anterior sabemos que, de alguma maneira,uma derivação mais à esquerda por G deve simular uma computaçãopor N . Mais precisamente,(5.1)

(i, w, ε) ` (i′, w, β) `∗ (f, ε, ε) se, e somente se (i′, β, f)⇒∗ w.

Entretanto, neste caso a simulação procede de maneira bem mais sutil.Para melhor identificar o problema, consideremos uma etapa da compu-tação acima

(q, σv, γu) ` (p, w, γ1 · · · γku),

onde v ∈ Σ∗ e u ∈ Γ∗. Evidentemente para que esta etapa seja legítimaé preciso que

(5.2) (p, γ1 · · · γk) ∈ δ(q, σ, γ).

Mas (5.2) dá lugar a nk regras: qual delas devemos escolher? Paradecidir isto precisamos verificar como a computação continua.

Em outras palavras, para construir o i-ésimo passo da derivação nãoé suficiente considerar apenas o i-ésimo passo da computação, mas vá-rios outros passos; até mesmo todo o restante da computação ! É claroque isto torna a demonstração da correspondência bem mais difícil queno caso de autômatos finitos. Felizmente podemos generalizar a equi-valência (5.1) de modo a tornar a demonstração mais transparente. Paraisso substituimos em (5.1) os estados i′ e f por estados quaisquer p e q,e β por um símbolo qualquerX do alfabeto da pilha. Esta generalizaçãoé o conteúdo do seguinte lema.


LEMA 13.2. Sejam p e q estados do autômato de pilha não deter-minístico N . Então

(q, w,X) `∗ (p, ε, ε) se, e somente se (q,X, p)⇒∗ wna gramática G(N ).

De acordo com esta correspondência se o autômato está no estadop quando X é desempilhado, então a variável que inicia a derivaçãoé (q,X, p). Assim, para achar a variável da partida é preciso olhar acomputação até o último passo!

A demonstração é por indução finita, e para torná-la mais clara va-mos dividi-la em duas partes.

Primeira parte: Queremos mostrar a afirmação

(A(m)) se (q, w,X) `m (p, ε, ε), então (q,X, p)⇒∗ w.por indução em m.

Se m = 1, então

w = σ ∈ Σ ∪ {ε} e (p, ε) ∈ δ(q, σ,X).

Mas, por construção, isto significa que na gramáticaG(N ) há uma regrado tipo

(q,X, p)→ σ.

Como, neste caso, toda a derivação se reduz a uma aplicação desta regra,a base da indução está provada.

Suponhamos, agora, que s > 1 é um número inteiro, e que A(m)vale para todo m < s. Seja

(5.3) (q, w,X) `s (p, ε, ε)

uma computação em N com s etapas.Isolando o primeiro símbolo de w, podemos escrever w = σv, onde

σ ∈ Σ e v ∈ Σ∗. Neste caso o primeiro passo da computação (5.3) seráda forma

(q, σv,X) ` (q1, v, Y1 · · ·Yk),que corresponde à transição

(5.4) (q1, v, Y1 · · ·Yk) ∈ δ(q, σ,X).

Note que, ao final da computação (5.3) cada Y foi desempilhado.Lembre-se que dizer, por exemplo, que Y1 é removido da pilha significaque a pilha passou a ser Y2 · · ·Yk. Isto não tem que acontecer em apenasuma transição. Assim, Y1 pode ser trocado por uma palavra no alfabetoda pilha sem que seja necessariamente desempilhado. Por isso, duranteos passos seguintes da computação a pilha pode crescer bastante antes

5. A GRAMÁTICA DE UM AUTÔMATO DE PILHA 135

de diminuir ao ponto de ser apenas Y2 · · ·Yk. Digamos então que v1é o prefixo de v que é consumido para que Y1 seja desempilhado. Sev = v1v, temos uma computação

(q1, v1v′, Y1 · · ·Yk) `∗ (q2, v′, Y2 · · ·Yk),

onde q2 é algum estado de N .Analogamente, sejam v2, v3, . . . , vk as subpalavras de v que têm

que ser consumidas para que Y2, . . . , Yk sejam desempilhados. Assim,v = v1v2 . . . vk, e existem estados q1, . . . , qk deN modo que (5.3) podeser subdividida em k − 1 etapas da forma

(qi, vi · · · vk, Yi · · ·Yk) `∗ (qi+1, vi+1 · · · vk, Yi+1 · · ·Yk),seguidas de uma etapa final da forma

(qk, vk, Yk) `∗ (p, ε, ε).

Como cada uma destas computações tem menos de s passos, segue dahipótese de indução, que

(qi, vi, Yi) `∗ (qi+1, ε, ε),

dá lugar à derivação

(5.5) (qi, Yi, qi+1)⇒∗ vi,

ao passo que a etapa final da computação corresponde a

(5.6) (qk, Yk, p)⇒∗ vk.Falta-nos apenas reunir de modo ordenado tudo o que fizemos até

agora. Em primeiro lugar, a transição (5.4) dá lugar a uma regra deG(N ) da forma

(q,X, p)→ σ(q1, Y1, q2) · · · (qk, Yk, p).

Substituindo, finalmente, as derivações de (5.5) e (5.6) nos lugares apro-priados, obtemos

(q,X, p)⇒ σ(q1, Y1, q2) · · · (qk, Yk, p)⇒∗ σv1 · · · vk = w,

como queríamos.

Segunda parte: Queremos mostrar a afirmação

(B(m)) se (q,X, p)⇒m w então (q, w,X) `∗ (p, ε, ε)

por indução em m

Se m = 1 então a derivação se resume a à regra

(q,X, p)→ w,


da gramática G(N ). Mas, pela construção da gramática, w tem que serum símbolo σ ∈ Σ ∪ {ε}. Além disto, esta regra só pode ocorrer sehouver uma transição da forma

(p, ε) ∈ δ(q, σ,X)

em N . Mas esta transição dá lugar à computação

(q, σ,X) ` (p, ε, ε)

que esperávamos obter.Suponha, agora, que s > 1 é um número inteiro e que o resultado

vale para toda derivação com menos de s passos. Seja

(5.7) (q,X, p)⇒s w

uma derivação de G(N ) com s etapas. Como s > 1, a primeira regra aser aplicada nesta derivação deve ser da forma

(5.8) (q,X, p)→ σ(s1, Y1, s2)(s2, Y2, s3) · · · (sk, Yk, p),onde (s1, . . . , sk) ∈ Qk e σ é o símbolo mais à esquerda de w. Di-gamos que w = σv, para alguma palavra v ∈ Σ∗. Para que a deriva-ção possa acabar produzindo w deve ser possível decompor v na formav = v1 · · · vk de modo que, para i = 1, . . . , k, temos

(si, Yi, si+1)⇒∗ vionde sk+1 = p. Como a derivação de vis tem que ter um número deetapas menor que s, podemos aplicar a hipótese de indução, obtendoassim computações

(si, vi, Yi) `∗ (si+1, ε).

para i = 1, . . . , k. Além disso, se pusermos Yi+1, . . . , Yk abaixo de Yi,no fundo da pilha, obteremos

(si, vi, YiYi+1 · · ·Yk) `∗ (si+1, ε).

Agora, (5.8) provém da transição

(p, Y1 · · ·Yk) ∈ δ(q, σ,X),

que pode ser reescrita na forma

(q, σ,X) ` (p, Y1 · · ·Yk).Lembrando que w = σv1 · · · vk, vemos queN admite uma computaçãoda forma

(q, w,X) ` (s1, v1 · · · vk, Y1 · · ·Yk) `∗ (s2, v2 · · · vk, Y2 · · ·Yk) `∗

· · · `∗ (sk, vk, Yk) ` (p, ε, ε),

como queríamos mostrar.

6. EXERCíCIOS 137

6. Exercícios

1. Construa a computação no autômato descrito na seção 2 que corres-ponde à derivação mais à esquerda de id ∗ (id + id) na gramáticaG′exp.

2. Ache um autômato de pilha não determinístico que aceita a linguagemgerada pela gramática cujas regras são:

S → 0AA

A→ 1S|0S|0

3. Considere a linguagem dos parênteses balanceados descrita no exer-cício 2 do capítulo ??.(1) Dê exemplo de uma gramática livre de contexto que gere esta

linguagem.(2) Dê exemplo de um autômato de pilha não determinístico que

aceita esta linguagem.

4. Para cada uma das linguagens L, abaixo, invente uma gramática livrede contexto que gere L e use a receita da seção 2 para construir umautômato de pilha não determinístico que aceite L.(a) L = {wc4wr : w ∈ {0, 1}};(b) L = {anbmc : n ≥ m ≥ 1};(c) L = {0m1n : n ≤ m ≤ 2n};(d) L = {ai+3b2i+1 : i ≥ 0};(e) L = {aibjcjdie3 : i, j ≥ 0}.

5. Seja G uma gramática livre de contexto cujo símbolo inicial é S, esejaM o autômato de pilha construído a partir de G pela receita daseção 2. Suponhamos que w é uma palavra de comprimento k emL(G) . Determine o número de passos da computação de M quecorresponde à derivação mais à esquerda S ⇒n w.

CAPíTULO 14

Máquinas de Turing

1. Exercícios

1. Considere a máquina de Turing cujo alfabeto é {a, b,t, .}, conjuntode estados {q0, q1, h}, estado inicial q0 e transições dadas pela tabela:

estado entrada transições

q0 0 (q1, 1)

1 (q1, 0)

t (h,t)

. (q0,→)

q1 0 (q0,→)

1 (q0,→)

t (q0,→)

. (q1,→)

(a) Descreva a computação deM a partir da configuração (q0, .001110).(b) Descreva informalmente o que M faz quando iniciada no estado

q0 e em alguma casa de sua fita.

2. Descreva a tabela de transição de uma máquina de Turing, no alfabeto{a, b,t, .}, que se move para a esquerda até encontrar três as na fitae então pára.

3. Explique porque as máquinas DE e ED nem sempre têm a mesmasaída.

4. Esboce o esquema de máquinas de Turing que aceitem as seguinteslinguagens:

139

140 14. MÁQUINAS DE TURING

(a) 010∗1;(b) {w ∈ {0, 1}∗ : |w| é par};(c) {anbncm : m ≥ n};(d) {w ∈ {0, 1} : w = wr};(e) {0n2

: n ≥ 1}.

5. Construa, a partir do diagrama dado em aula, a tabela de transições damáquina de TuringMe que move uma palavraw ∈ (0∪1)∗, precedidade uma casa vazia, uma casa para a esquerda; isto é, que transformatw em w.

6. Construa máquinas de Turing que calculem as seguintes funções f :N→ N definidas por:(a) f(n) = n+ 1;(b) f(n) é o resto da divisão de n por 2;(c)

f(n,m) =

{n−m se n−m ≥ 0

0 se n < m.

7. Descreva uma máquina de Turing que, tendo como entrada uma pala-vra w ∈ {0, 1}∗ encontra o símbolo do meio da palavra (se existir!).

8. Descreva uma máquina de Turing que, tendo como entrada uma pa-lavra w ∈ {0, 1}∗ com comprimento par, substitui os 0s por a ou c eos 1s por bs ou ds, de modo que a palavra fica escrita na forma w1w2

onde w1 ∈ {a, b}∗ e w2 ∈ {c, d}∗.

9. Utilizando a máquina de Turing da questão anterior construa uma má-quina de Turing que aceita a linguagem {ww : w ∈ {0, 1}∗}.

10. Mostre que a linguagem {ww : w ∈ {0, 1}∗} é recursiva.

11. Construa a fita de entrada para que a máquina de Turing universalsimule a computação da máquina de Turing do exercício 1 a partir daconfiguração (q0, .001110).

12. Sejam L1 e L2 linguagens recursivas aceitas por máquinas de TuringM1 e M2, respectivamente. Mostre como construir uma máquina deTuringM que aceite a linguagem L1 ∪ L2.

13. A intersecção de linguagens recursivas é recursiva? Explique sua res-posta.

14. Dê a definição formal de uma máquina de Turing cuja fita é dupla-mente infinita (isto é, vai de −∞ a +∞). Mostre como é possívelsimular uma máquina destas usando uma máquina de TuringM cuja

1. EXERCÍCIOS 141

fita é infinita somente à direita. As máquinas definidas originalmentepor Alan Turing tinham fitas duplamente infinitas.Sugestão: Escolha um ponto de referência na fita duplamente infinitae escreva os símbolos das casas à direita do referencial nas casas pa-res da fita deM, e aqueles que estão à esquerda nas casas ímpares.Explique como deve ser o comportamento deM. Note queM chegaa . quando a máquina original cruza o ponto de referência. Qual vaiser o comportamento deM neste caso?

15. Seja Σ0 um alfabeto e L uma linguagem no alfabeto Σ0. Mostre que,se L e Σ0 \ L são recursivamente enumeráveis, então L é recursiva.

16. Seja Σ0 um alfabeto e L uma linguagem no alfabeto Σ0 que é recur-sivamente enumerável mas não é recursiva. Suponha que M é umamáquina de Turing que aceita L. Mostre que existe uma quantidadeinfinita de palavras em Σ0 que não é aceita por M .

CAPíTULO 15

Máquinas de Turing e Linguagens

Neste capítulo discutimos várias propriedades das linguagens recur-sivas e recursivamente enumeráveis. Entretanto, o principal resultado docapítulo é o fato de que existe uma máquina de Turing que é capaz desimular qualquer outra máquina de Turing. Esta máquina é conhecidacomo máquina de Turing Universal, e foi originalmente construída porAlan Turing em 1937.

O capítulo começa com a descrição de uma construção que permiteconectar duas máquinas de Turing em paralelo, e se encerra com o Pro-blema da Parada.

1. Conectando Máquinas em Paralelo

Suponhamos que M = (Σ, Q, q1, F, δ) e M ′ = (Σ, Q′, q′1, F′, δ′)

são duas máquinas de Turing no alfabeto Σ. Defina um novo alfabetopor

Σ = Σ ∪ {σ : σ ∈ Σ}.

Quer dizer, para cada símbolo σ ∈ Σ, existem dois símbolos em Σ: opróprio σ e σ. A nova máquina M é constituída pelos seguintes ele-mentos:

ALFABETO: Σ2 ∪ {.,t}.

CONJUNTO DE ESTADOS: Q ⊇ Q×Q′.

ESTADO INICIAL: (q1, q′1),

ESTADOS FINAIS: H ⊆ Q × Q′ que depende do que eu quero que amáquina faça.

143

144 15. MÁQUINAS DE TURING E LINGUAGENS

Antes de discutir as transições, precisamos explicar como é a fita damáquina. Como sempre, a extremidade esquerda da fita está marcadapelo símbolo .. Já a casa imediatamente à direita desta sempre conterá

(., .) ou (., .) ou (., .) ou (., .).

Além disso, a máquina que estamos construindo só poderá imprimir umdestes símbolos nesta casa.

TRANSIÇÃO: Vamos descrever o comportamento da máquina na formade um ciclo completo que ela fica repetindo até parar. No começo dociclo,M está no estado (q, q′) ∈ Q×Q′.

A máquina M precisa lembrar que está simulando M a partir doestado q e M ′ a partir do estado q′, até chegar na etapa 5. Nesta etapahaverá uma mudança nos estados a partir dos quais a simulação estásendo feita. Estes novos estados serão lembrados até chegar à etapa 8.Como isto é feito será discutido ao final da descrição da transição.

ETAPA 1: Se (q, q′) ∈ H a máquina pára.

ETAPA 2: Lembrando que está simulando M a partir de q e M ′ a partirde q′, a máquinaM recua seu cabeçote para a esquerda até encontrar ..

ETAPA 3: Lembrando que está simulando M a partir de q e M ′ a partirde q′, a máquina M move o cabeçote para a direita até encontrar umsímbolo da forma (σ, σ′).

ETAPA 4: Lembrando que está simulando M a partir de q e M ′ a partirde q′, a máquinaM atualiza a fita e os estados que está simulando deM e M ′ conforme a tabela abaixo

Novo esta- Novo esta- Fitaδ(q, σ) do de M do de M ′

(p, τ) p q′ imprime (τ , σ′) sem mover cabeçote(p,→) p q′ imprime (σ, σ′) e move para a direita:

• se está lendo (α, α′), imprime (α, α′)• se está lendo t, imprime (t,t)

(p,←) p q′ imprime (σ, σ′) e move para a esquerda:• se está lendo (α, α′), imprime (α, α′)• se está lendo t, imprime (t,t)

Se, na última linha da tabela, (σ, σ′) = (., .) então a máquina seráforçada a mover o cabeçote para a direita, efetuando a mudança de esta-dos correspondente em M .

2. FECHAMENTO DE LINGUAGENS 145

Ao final desta etapa os estados M e M ′ que estão sendo lembradosporM passam a ser p e q′.

ETAPA 5: Se (p, q′) ∈ H a máquina pára.

ETAPA 6: Lembrando que está simulando M a partir de p e M ′ a partirde q′, a máquinaM recua seu cabeçote para a esquerda até encontrar ..

ETAPA 7: Lembrando que está simulando M a partir de p e M ′ a partirde q′, a máquina M move o cabeçote para a direita até encontrar umsímbolo da forma (σ, σ′).

ETAPA 8: Lembrando que está simulando M a partir de p e M ′ a partirde q′, a máquinaM atualiza a fita e os estados que está simulando deM e M ′ conforme a tabela abaixo

Novo esta- Novo esta- Fitaδ(q′, σ′) do de M do de M ′

(p′, τ ′) p p′ imprime (σ, τ ′) sem mover cabeçote(p′,→) p p′ imprime (σ, σ′) e move para a direita:

• se está lendo (α, α′), imprime (α, α′)• se está lendo t, imprime (t,t)

(p′,←) p p′ imprime (σ, σ′) e move para a esquerda• se está lendo (α, α′), imprime (α, α′)• se está lendo t, imprime (t,t)

Naturalmente, se, na última linha da tabela, (σ, σ′) = (., .) entãoa máquina será forçada a mover o cabeçote para a direita, efetuando amudança de estados correspondente em M .

Ao final desta transição a máquina entra o estado (p, p′) e o ciclo éreinicializado.

Falta somente explicar como é que a máquina lembra que está simu-lando M a partir de q e M ′ a partir de q′. Para isto, para cada par (q, q′),construímos um conjunto de estados associado a este par que a máquinadeverá entrar ao executar as etapas 1, 2, 3 e 4 do ciclo, e outro conjuntode estados que corresponderá às etapas 5, 6, 7 e 8 do ciclo. Em outraspalavras, a máquina lembra quais são os estados q e q′ a partir dos quaisestá simulando M e M ′ por causa dos estados que está vendo.

2. Fechamento de linguagens

Estamos prontos para usar a máquina construída na seção anteriorpara discutir como é o comportamento das linguagens recursivas e re-cursivamente enumeráveis com respeito às operações de união e inter-secção.


Para começar, digamos que L é uma linguagem aceita por uma má-quina de Turing M = (Σ, Q, q1, F, δ) e L′ por M ′ = (Σ, Q′, q′1, F

′, δ′).Assim, estamos supondo que L e L′ são recursivamente enumeráveis.

A partir destas máquinas construiremos uma máquinaM, como naseção 1, tomando H = (F × Q′) ∪ (Q × F ′). O efeito desta escolhade estados finais é fazer com que esta mquina páre quando M ou M ′

atinge um estado final.Seja w = σ1 · · ·σn uma palavra de Σ∗. Daremos aM a entrada

(2.1) (., .)(t,t)(σ1, σ1) · · · (σn, σn).

Por causa de nossa escolha de estados finais, a computação de M apartir desta palavra vai parar se, e somente se, w ∈ L ou w ∈ L′.Portanto, a linguagem aceita porM, sob esta escolha de estados finais éL∪L′. Concluímos, assim, que se L e L′ são linguagens recursivamenteenumeráveis, então L ∪ L′ é recursivamente enumerável.

Também é verdade que se L e L′ linguagens recursivamente enume-ráveis, então L ∩ L′ é recursivamente enumerável. Fica como exercíciopara você, determinar qual a escolha de conjunto de estados finais paraa qualM aceita L ∩ L′.

Suponhamos, agora, que L e L′ são linguagens recursivas. SejamM e M ′, definidas como acima, de modo que L seja decidida por M eL′ porM ′. Lembre-se que, neste caso, F = F ′ = {s, n}. Escolheremos

H = F × F ′.

Dando aM uma entrada como (2.1), verificamos que esta máquina sópára no estado (n, n) se w /∈ L e w /∈ L′. Por outro lado, se w ∈ Lou w ∈ L′, então M pode parar em um dos estados (s, n), (n, s) ou(s, s). Isto não é satisfatório, porque se w ∈ L ∪ L′ esperaríamos queM parasse sempre no mesmo estado. Para curar este problema, bastaconstruir uma máquinaN que executaM como explicado acima e que,terminada a computação deM, altera o estado para (s, s) seM alcan-çou um dos estados de aceitação (s, n), (n, s) ou (s, s). Verificamos,portanto, que se L e L′ são linguagens recursivas, então L∪L′ tambémé recursiva.

Deixamos aos seus cuidados escolher os estados finais deM e efe-tuar as mudanças necessárias para provar que se L e L′ são linguagensrecursivas, então L ∩ L′ também é recursiva.

De todas as operações básicas com conjuntos só não analisamosainda o que ocorre com o complementar. Neste ponto as duas classes delinguagens divergem radicalmente. Suponhamos, para começar, que Lseja uma linguagem recursiva no alfabeto Σ0 e que M é uma máquina

3. A MÁQUINA DE TURING UNIVERSAL 147

de Turing, em um alfabeto que contém Σ0, e que decide L. Então, oconjunto de estados finais de M é {s, n} e, dado w ∈ Σ∗0, temos que

• w ∈ L se e só se M pára no estado s;• w ∈ L = Σ∗0 \ L se e só se M pára no estado n.

Para construir uma mquina M que decida L, basta alterar as transiçõesde M de modo que quando M entra o estado s, então M entra o estadon; e vice-versa. Logo se L é recursiva, então L também é.

Infelizmente, uma estratégia deste tipo não vai funcionar quando Lfor apenas recursivamente enumerável porque, neste caso, a máquinaque aceita L simplesmente não pára se a palavra estiver fora de L. Vere-mos, na seção 5, que o complementar de uma linguagem recursivamenteenumerável não tem que ser recursivamente enumerável. Por hora, re-sumiremos tudo o que vimos nesta seção em um teorema.

TEOREMA 15.1. Sejam L e L′ linguagens em um alfabeto Σ0.(1) Se L e L′ são recursivamente enumeráveis, então L ∪ L′ e

L ∩ L′ também são.(2) Se L e L′ são recursivas, então L ∪ L′ e L ∩ L′ também são.(3) Se L for recursiva, então L = Σ∗0 \ L também é.

3. A máquina de Turing universal

Nesta seção descrevemos uma construção para a máquina de Tu-ring universal U . Trata-se de uma máquina de Turing capaz de simularqualquer outra máquina de Turing. Naturalmente, para que isto seja pos-sível, a máquina universal precisa receber como entrada o “programa”da máquina que está sendo simulada. Em outras palavras, precisamosser capazes de descrever o alfabeto, o conjunto de estados e as transiçõesde uma máquina de Turing qualquer a partir do alfabeto de U .

Há muitas maneiras diferentes de construir a máquina U . Na cons-trução que faremos o alfabeto será

Σ = {., 0, 1, σ, q,X, Y, Z, ?,t, a, b}.

Descreveremos as transições de uma máquina de Turing M na fita deU enumerando (separadamente) os símbolos e os estados de M no sis-tema unário. Para distinguir símbolos de estados vamos adicionar aossímbolos o prefixo σ e aos estados o prefixo q. Para os propósitos destadescrição, é conveniente representar as setas → e ← como se fossemsímbolos de M .

Digamos que a máquina de TuringM que desejamos simular usandoU tem n estados e um alfabeto com m símbolos. Para que o número decasas da fita de U ocupadas pela descrição de um símbolo de M seja


sempre o mesmo, reservaremos m+ 3 casas para representar cada sím-bolo, preenchendo as casas redundantes com 1s. Mas se o alfabeto deMsó tem m símbolos, por que precisamos de m + 3 casas? Em primeirolugar, estamos considerando as setas como símbolos ‘honorários’, o quedá conta de duas, das três casas extra. A outra casa é usada para pôr oprefixo σ, que indica que a seqüência de 0s e 1s que vem a seguir é umsímbolo, e não um estado de M .

Procederemos de maneira análoga para os estados, reservando nestecaso n + 1 casas para cada estado. Assim, o r-ésimo símbolo do alfa-beto de M será denotado por σ0r1m+2−r, e o r-ésimo estado de M porq0r1n−r. Lembre-se que nesta descrição estão incluídas → e ←. Porrazões mnemônicas, convencionaremos que→,← e ., serão sempre ostrês primeiros símbolos a serem enumerados. Assim,

símbolo código

→ σ01m+1

← σ021m

. σ031m−1

SejamM uma máquina de Turing ew uma palavra que deverá servirde entrada para M . Para dar início à simulação de M por U precisamospreparar a fita de U com os dados de M . Consideremos, em primeirolugar, a maneira de codificar uma transição de M da forma δ(qi, σj) =(qr, σs). Se σs ∈ Σ∪{→,←}, então esta transição corresponderá a umsegmento da fita da forma

X q 0i 1n−i σ 0j 1m+2−j q 0r 1n−r σ 0s 1m+2−s X

Note que o 0i representa na verdade um segmento de i casas da fita, e omesmo vale para 1i.

A descrição completa deM e w na fita de entrada de U será feita se-gundo o modelo abaixo, onde Si denota um segmento, da forma descritaacima, entre os dois Xs.

. X S1 X S2 · · · X St Y Q Z σ u1 σ u2 ? u3 · · ·

Nesta fita temos que:

3. A MÁQUINA DE TURING UNIVERSAL 149

De Até Conteúdo do segmento. Y descrição do comportamento de M

Y Z Q = q0i1n−i é o estado em que M se encontra no estágio atualda computação

Z final w onde cada símbolo está escrito em unário e precedido de σ

Note que o número unário que descreve um dos símbolos da en-trada da máquina M na fita acima está precedido de ? e não de σ. A ?serve para marcar o símbolo atualmente lido por M na simulação porU . Assim, quando a fita é preparada para a entrada de U , o segmento Qé preenchido com o estado inicial de M e o símbolo ? ocupa a segundacasa à direita do Z (porque a segunda e não a primeira?). A sucessão desímbolos do trecho da fita de U que contém a descrição da máquina Mé uma palavra no alfabeto Σ. Vamos denotar esta palavra por c(M).Exemplo. Considere a máquina de Turing com alfabeto {0,t, .}, con-junto de estados {q0, q1, h}, estado inicial q0, conjunto de estados finais{h} e tabela de transição

estado entrada transições

q0 0 (q1,t)

t (h,t)

. (q0,→)

q1 0 (q0, 0)

t (q0,→)

. (q1,→)

Neste caso os símbolos e estados deM são codificados como abaixo.Lembre-se que, neste exemplo, deve haver 4 casas da fita para cada es-tado e para cada símbolo (já que há 3 estados e 3 símbolos), sendo queas casas redundantes devem ser preenchidas com 1s.

estado código símbolo código

q0 →q1 ←h .

* * t* * 0


Exercício. Descreva a fita de U correspondente a esta máquina com en-trada 000t.

4. Comportamento de U

O procedimento da máquina de Turing universal é constituído deduas partes: na primeira a máquina verifica se a fita contém uma des-crição legítima de alguma máquina de Turing; na segunda U simula amáquina cuja descrição lhe foi dada.

Na primeira parte do processamento da entrada, U verifica que a fitaque recebeu contém uma descrição legítima de máquina de Turing. Parafazer isto, U varre a fita a partir de / e verifica que os Xs, qs, σs e Zsestão posicionados na ordem correta. À medida que faz isto, U utilizaa máquina contagem para comparar o bloco de 0s e 1s entre q e σ como bloco correspondente que vem depois do próximo X; e faz o mesmocom o bloco entre σ e X . Finalmente, U compara o bloco entre os doisZs com o bloco entre o primeiro q e o primeiro σ para ver se têm omesmo número de casas. Se alguma destas condições não é verificadaU caminha para a direita pela fita sem parar.

A segunda parte do processamento de U pode ser descrito como umciclo com 3 etapas:Primeira Etapa: No início o cabeçote está parado sobre o Z. Entãoentra em ação uma máquina do tipo localiza que, a partir de . localizauma quádrupla que comece com o par (Q, τ), onde τ é o símbolo à di-reita do Z marcado com ? eQ é o estado entre Y e Z. À medida que vaitentando achar este par, a máquina vai trocando os 0s e 1s (da esquerdapara a direita) por as e bs, respectivamente. Isto permite identificar atéonde já foi feita a busca. Ao achar o par desejado, a máquina tambémtroca os 0s e 1s deste par por as e bs. Com isto o q0i1n−i mais à es-querda da fita corresponde ao estado seguinte a Q na transição de Mpor τ . Note que se U não conseguir localizar a transição desejada entãoo estado atual de M é final. Portanto, neste caso, U deve entrar em umestado final, o que a faz parar também.

Segunda Etapa: Agora copie o estado seguinte ao atual na transição deM a partir de Q e τ no campo que corresponde ao estado atual de M .Troque os números por letras também neste estado. Considere agora o σseguido de algum número que fica mais à esquerda da fita: ele nos diz oque M faria com sua fita de entrada nesta transição. O comportamentode U está resumido na tabela abaixo:

5. LINGUAGENS NÃO RECURSIVAS 151

Acha Faz

σ011m+1 move o ? para o lugar do σ seguinte

σ021m move o ? para o lugar do σ anterior

σ0j1m+2−j e j ≥ 3 substitui o segmento entre ? e σ por 0j1m+2−j

Terceira Etapa: Agora U volta o cabeçote até . e move-se para à direitatrocando todos os as e bs por 0s e 1s, respectivamente até chegar aosegundo σ depois da ? (por quê?). Finalmente o cabeçote volta a Z.Assim U está pronta para começar um novo ciclo.

5. Linguagens não recursivas

Seja M uma máquina de Turing no alfabeto Σ. Já vimos que pode-mos simular M usando a máquina universal U . Para fazer isto, precisa-mos preparar a fita da máquina U de modo a codificar o comportamentode M . A descrição de M vem no começo da vida e está inteiramentecontida na palavra c(M) ∈ Σ∗.

Considere agora a linguagem L formada pelas palavras de Σ∗ querepresentam corretamente a descrição de uma máquina de Turing noalfabeto Σ. Em outras palavras

L = {c(M) : M é uma máquina de Turing no alfabeto Σ}.

A linguagem que desejamos considerar é um subconjunto de L:

L0 = {c(M) : a máquina M aceita c(M)}.

Por mais exótica que possa parecer, L0 é uma linguagem recursivamenteenumerável. Para ver isto basta exibir uma máquina de Turing que aceitaL0. Seja C a máquina de Turing que, tendo como entrada /wt, produza saída /wZwt. Então a linguagem aceita por C · U é L0. Observeque se w ∈ Σ∗ não é uma descrição legítima de alguma máquina deTuring, então wZw é automaticamente rejeitada por U no momento dachecagem inicial da entrada.

Diante do que acabamos de ver a seguinte pergunta imediatamentese impõe.

PERGUNTA. L0 é uma linguagem recursiva?

Se L0 fosse recursiva, seu complemento L0 também seria. Surpre-endentemente isto está longe de ser verdade.

TEOREMA 15.2. L0 não é uma linguagem recursivamente enume-rável.


Suponhamos, por contradição, que L0 seja recursivamente enume-rável. Então é aceita por alguma máquina de Turing M no alfabeto Σ.O código desta máquina é um elemento de L. Podemos perguntar:

c(M) pertence a L0?Digamos que a resposta desta pergunta seja sim. Neste caso

c(M) ∈ L0 = L(M).

Mas se c(M) ∈ L(M) então c(M) é aceita por M . Assim, por defini-ção, c(M) ∈ L0; e obtemos uma contradição.

Por outro lado, se a resposta da pergunta for não, então

c(M) /∈ L0 = L(M).

Em outras palavras, c(M) não é aceita por M . Mas isto significa quec(M) /∈ L0; isto é c(M) ∈ L0; e mais uma vez obtemos uma contradi-ção.

Mostramos assim que existem linguagens recursivamente enumerá-veis que não são recursivas. De quebra, obtemos o seguinte resultado.

COROLÁRIO 15.3. O complemento de uma linguagem recursiva-mente enumerável não é necessariamente recursivamente enumerável.

6. O problema da parada

Podemos enunciar este problema da seguinte maneira:

PROBLEMA 15.1. Dada uma máquina de Turing M no alfabetoΣ e uma palavra w ∈ Σ∗ existe uma máquina de Turing P que, tendoc(M) · Z · w como entrada decide se M pára com entrada w?

Se o problema da parada tivesse uma resposta afirmativa, entãotoda linguagem recursivamente enumerável seria recursiva. Para mos-trar isto, suponha que L é uma linguagem recursivamente enumerávelqualquer e seja M uma máquina de Turing que aceita L. Se conhece-mos M , então conhecemos c(M). Seja C a máquina que transforma aentrada /wt em /c(M)Zwt. Se w ∈ L então a máquina M pára naentrada w; portanto C · P pára no estado sim. Do contrário, M não páracom entrada M ; mas neste caso C · P também pára, só que no estadonão.

Diante disto podemos concluir que o problema da parada não podeter uma resposta afirmativa porque, como vimos na seção anterior, exis-tem linguagens recursivamente enumeráveis que não são recursivas.

A resposta negativa para o problema da parada tem importantes con-seqüências, tanto de natureza teórica quanto prática. Por exemplo, seria

6. O PROBLEMA DA PARADA 153

certamente desejável ter algoritmo que, recebendo um programa P euma entrada E de P , decidisse se P pára com entrada E. Um algoritmodeste tipo ajudaria muito na elaboração e teste de programas. Infeliz-mente a resposta negativa para o problema da parada mostra que um talalgoritmo não pode existir.

Uma conseqüência de natureza teórica muito importante do mesmoproblema é que nem toda questão matemática pode ser decidida de ma-neira algorítmica. Em outras palavras, há limites teóricos claros para oque uma máquina pode fazer.

Além disto o problema da parada está longe de ser o único pro-blema matemático que não admite solução algorítmica. Outros proble-mas, ainda na área de linguagens formais, que padecem do mesmo malsão os seguintes:

• dadas duas linguagens livres de contexto, determinar se suaintersecção é livre de contexto.• dada uma linguagem livre de contexto, determinar se é regular.• dada uma linguagem livre de contexto, determinar se é ineren-

temente ambígüa.

Referências Bibliográficas

[1] M. A. Harrison, Introduction to formal language theory, Addison-Wesley (1978).[2] J. E. Hopcroft e J. D. Ullman, Introduction to automata theory, languages and computation,

Addison-Wesley (1979).

155

Documents

Autômatos e Linguagens Formais S. C. Coutinho