capitulo 3 - Autômatos de pilha

Prévia do material em texto

Caṕıtulo 3
Autômatos de Pilha
Apesar das inúmeras aplicações dos formalismos associados às linguagens regulares,
existem aplicações que requerem linguagens mais sofisticadas e que, portanto, envolvem
o uso de formalismos mais sofisticados. Por exemplo, são comuns as aplicações em
que se deve escrever expressões aritméticas. As linguagens das expressões aritméticas
normalmente contêm todas as palavras da forma:
(
nx0+x1)+x2) · · · +xn)
em que n ≥ 0, cada xi é uma subexpressão, e o número de (s é igual ao de )s. Aplicando-
se o lema do bombeamento, vê-se que tais linguagens não são regulares: tomando-se
z = (kx0+x1)+x2) · · · +xk), em que k é a constante referida no lema, vê-se que para
quaisquer u, v e w tais que z = uvw, |uv| ≤ k e v 6= λ,
uv2w = (k+|v|x0+x1)+x2) · · · +xk),
que tem mais (s do que )s.
Intuitivamente, um AF não pode reconhecer a linguagem descrita porque não tem
uma memória poderosa o suficiente para “lembrar” que leu n ocorrências de certo
śımbolo, para n arbitrário. A única maneira de ler uma quantidade arbitrária de
determinado śımbolo, em um AF, é por meio de um ciclo. E, nesse caso, não há como
contar o número de śımbolos lidos.
Neste caṕıtulo, será apresentada uma extensão dos AFs, os denominados autômatos
de pilha,1 de grande importância, visto que constituem uma base para a obtenção de
reconhecedores para muitas linguagens que ocorrem na prática. Em particular, alguns
compiladores de linguagens de programação utilizam alguma variante de autômato de
pilha na fase de análise sintática.
Ao contrário dos AFs, a versão não determińıstica desse tipo de autômato tem uma
abrangência de reconhecimento maior que a determińıstica. No entanto, as linguagens
que podem ser reconhecidas por autômatos de pilha determińısticos são especialmente
1 Em inglês, pushdown automata.
133
134 Editora Thomson Introdução aos fundamentos da computação
a1 a2 · · · ai · · · an 〉 fita de leitura apenas, unidirecional
❄
controle
+
δ
e registrador com estado atual
b1
b2
...
bn
topo da pilha
pilha
Figura 3.1 Arquitetura de um APD.
importantes, já que admitem reconhecedores eficientes. Algumas construções que ocor-
rem em linguagens que podem ser reconhecidas por autômatos de pilha não deter-
mińısticos, mas que não podem ocorrer em linguagens que possam ser reconhecidas por
autômatos de pilha determińısticos, alertam para o fato de que se está transitando do
campo da eficiência de reconhecimento para o da ineficiência.
Antes de apresentar as versões determińıstica e não determińıstica de autômatos de
pilha nas Seções 3.2 e 3.3, será vista uma introdução informal de autômato de pilha
determińıstico na Seção 3.1. Depois, na Seção 3.4, serão estudadas as gramáticas livres
do contexto, que são um formalismo de grande utilidade prática para a especificação de
linguagens reconhećıveis por autômatos de pilha. Para finalizar, algumas propriedades
importantes dessa classe de linguagens serão abordadas na Seção 3.5.
3.1 Uma Introdução Informal
Um autômato de pilha determnińıstico (APD) pode ser visto como uma máquina similar
àquela ilustrada na Figura 2.47, página 120, que contenha adicionalmente uma pilha,
como mostrado na Figura 3.1. Como a fita, a pilha é dividida em células que comportam
apenas um śımbolo cada uma, mas o cabeçote de leitura da pilha só se posiciona na
célula do topo da pilha. No ińıcio, o registrador contém o estado inicial do APD, a
fita recebe a palavra de entrada a partir da sua primeira célula, o cabeçote da fita é
posicionado na primeira célula da fita e a pilha está vazia.
Agora, além do alfabeto da fita haverá o alfabeto da pilha (não necessariamente
disjunto do da fita). E embora a ocorrência de uma transição a partir de um estado
possa depender do śımbolo de entrada e do śımbolo no topo da pilha, será permitido
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 135
ap fp
(, λ/X
a, λ/λ
), X/λ
+, λ/λ; ∗, λ/λ
Figura 3.2 Reconhecendo expressões aritméticas simples.
também que ela dependa apenas do śımbolo de entrada (ignorando o que está no topo
da pilha) ou apenas do śımbolo no topo da pilha (ignorando o śımbolo de entrada). A
palavra vazia, λ, será usada nestes últimos dois casos para indicar a intenção de ignorar
a entrada ou a pilha.
Suponha um APD com conjunto de estados E, alfabeto de entrada (alfabeto da
fita) Σ e alfabeto da pilha Γ. Em uma computação, ao transitar de um estado e para
um estado e′, caso o śımbolo de entrada seja a ∈ Σλ (se a = λ, nada é lido) e o śımbolo
do topo da pilha seja b ∈ Γλ (se b = λ, o śımbolo do topo da pilha é ignorado), o APD
poderá empilhar zero ou mais śımbolos (representados por uma palavra z ∈ Γ∗) no lugar
de b. Tendo isso em mente, cada transição do APD será da forma δ(e, a, b) = [e′, z],
em que e, e′ ∈ E, a ∈ Σλ, b ∈ Γλ e z ∈ Γ
∗. Essa transição será dita uma transição de
e para e′ sob a desempilhando b e empilhando z, sendo representada em um diagrama
de estados da seguinte forma:
e e′
a, b/z
significando, no caso em que a 6= λ, b 6= λ e z 6= λ, que “estando no estado e, se o
próximo śımbolo de entrada for a e o śımbolo no topo da pilha for b, há uma transição
para o estado e′, b é desempilhado e z, empilhado (o śımbolo mais à esquerda em z,
no topo)”. Se a = λ, não é consumido o śımbolo de entrada. Se b = λ, a transição
acontece sem consulta à pilha e nada é desempilhado. E se z = λ, nada é empilhado.
Se z = a0a1 . . . an, então os śımbolos são empilhados na ordem an, an−1, . . . , a0.
Um APD simples que reconhece certo tipo de expressão aritmética é apresentado a
seguir.
Exemplo 70 Seja o conjunto EA das expressões aritméticas com parênteses e as
operações de soma (+) e multiplicação (*), definido recursivamente por:
a) a ∈ EA;
b) se x, y ∈ EA, então (x) ∈ EA, x+y ∈ EA e x∗y ∈ EA.
O śımbolo a pode ser imaginado como representando expressões mais básicas, como
números inteiros e/ou reais, identificadores de variáveis etc. O reconhecimento de tais
expressões básicas não oferece nenhum problema, podendo ser feito mediante um AF. A
Figura 3.2 apresenta um diagrama de estados para um APD que reconhece EA. Observe
que o conjunto de estados é E = {ap, fp}, o alfabeto de entrada é Σ = {a, (, ),+, ∗}, e
136 Editora Thomson Introdução aos fundamentos da computação
o da pilha, Γ = {X}. O estado inicial é ap e o conjunto de estados finais, {fp}. Existem
cinco transições:
1. δ(ap, (, λ) = [ap, X];
2. δ(ap, a, λ) = [fp, λ];
3. δ(fp, ), X) = [fp, λ];
4. δ(fp,+, λ) = [ap, λ];
5. δ(fp, ∗, λ) = [ap, λ].
As transições estão numeradas para referência futura. Os detalhes de funcionamento
desse APD serão elucidados do decorrer desta seção, à medida que os conceitos ne-
cessários forem sendo introduzidos.
Uma pilha de śımbolos de um alfabeto Γ será representada por meio de uma palavra
de Γ∗. A convenção adotada é que o śımbolo mais a esquerda está no topo. Assim, o
resultado de empilhar o śımbolo a na pilha y é a pilha ay. O resultado de desempilhar
o elemento do topo da pilha ay é a pilha y. A pilha vazia será representada pela
palavra λ.
No Caṕıtulo 2, mostrou-se que a configuração instantânea de um AF é um par
[e, y], em que e é o estado atual do autômato e y, o restante da palavra de entrada. A
configuração instantânea consta das informações necessárias para o autômato prosseguir
no reconhecimento da palavra de entrada em certo instante. Em um autômato de pilha,
ela será uma tripla [e, y, z], na qual e é o estado atual, y é o restante da palavra de
entrada, e z é o conteúdo da pilha. Como explicado na Seção 2.1.1, usa-se a notação
c ⊢ c′ para dizer que a configuração instantânea c′ é o resultado de uma transição
a partir da configuração instantânea c. Com isso, por exemplo, pode-se expressar a
seguinte computação para o APD do Exemplo70, mostrado na Figura 3.2, quando a
palavra de entrada for (a*(a+a)):
[ap, (a ∗ (a+ a)), λ] ⊢ [ap, a ∗ (a+ a)),X] por 1
⊢ [fp, ∗(a + a)),X] por 2
⊢ [ap, (a+ a)),X] por 5
⊢ [ap, a+ a)),XX] por 1
⊢ [fp,+a)),XX] por 2
⊢ [ap, a)),XX] por 4
⊢ [fp, )),XX] por 1
⊢ [fp, ),X] por 3
⊢ [fp, λ, λ] por 3.
Não há transição que se aplique a ⊢ [fp, λ, λ].
Outro exemplo:
[ap, a), λ] ⊢ [fp, ), λ] por 2.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 137
λ, λ/X
Figura 3.3 Um APD com computações ilimitadas.
Não há transição que se aplique a [fp, ), λ]. Esse segundo exemplo mostra que o APD
pode não consumir toda a palavra de entrada. Usando a metáfora propiciada pelo
esquema da Figura 3.1, em que a cada transição corresponde uma “instrução” da
máquina, diz-se que um AP pode parar sem consumir toda a palavra de entrada.
Para uma palavra ser reconhecida é necessário que três condições sejam satisfeitas
simultaneamente : (1) um estado final seja atingido (2) a palavra seja totalmente con-
sumida e (3) a pilha esteja vazia. Em outras palavras, uma palavra w é reconhecida se
a computação com ińıcio na configuração inicial [i, w, λ] atingir a configuração [f, λ, λ]
em que f é estado final. Assim, para o APD do Exemplo 70, a palavra (a*(a+a)) é
reconhecida, como mostra a primeira computação descrita. A palavra a) não é reco-
nhecida, pois o AP não consome toda a palavra, como mostra a segunda computação
apresentada. E a palavra (a não é reconhecida, pois o APD para com a pilha não vazia:
[ap, (a, λ] ⊢ [ap, a, X] por 1
⊢ [fp, λ, X] por 2.
Não há transição que se aplique a [fp, λ, X].
É interessante notar que existem APs que não param para algumas entradas, ou
mesmo para todas as entradas, como mostra o próximo exemplo.
Exemplo 71 Um exemplo conciso de um AP com computações de tamanho ilimitado
seria aquele com alfabeto de entrada {1} e com o diagrama de estados exposto na
Figura 3.3. Para toda palavra em {1}+, pode-se dizer que o APD não para, visto
que o primeiro śımbolo nunca é lido e a única transição existente é sempre aplicável.
Em particular:
[0, 1, λ] ⊢ [0, 1,X] ⊢ [0, 1,XX] . . .
Para a palavra λ, a transição também é aplicável e têm-se computações de todo tama-
nho. Pergunta: para a palavra de entrada λ, deve-se considerar que o APD para ou
não? A palavra λ é reconhecida ou não?
Na próxima seção, será definido formalmente o conceito de autômato de pilha de-
termińıstico e apresentados alguns exemplos. O problema levantado no Exemplo 71
pode ser resolvido formalizando-se convenientemente a noção de reconhecimento.
3.2 Autômatos de Pilha Determińısticos
Os autômatos de pilha determińısticos (APDs) são especialmente importantes, já que
lidam com uma classe de linguagens para as quais há reconhecedores eficientes.
138 Editora Thomson Introdução aos fundamentos da computação
A definição de autômato de pilha determińıstico, basicamente, acrescenta uma pilha
a um AFD. Para que haja determinismo, não deverá ser posśıvel mais de uma transição
ser definida para uma mesma configuração instantânea; em outras palavras, em um es-
tado qualquer do APD, qualquer que seja o próximo śımbolo de entrada e qualquer que
seja a situação atual da pilha, no máximo uma transição deverá ser posśıvel. A de-
finição a seguir captura exatamente as situações em que duas transições podem ocorrer
simultaneamente para alguma configuração instantânea.
Definição 33 Seja uma função de transição δ : E×Σλ×Γλ → E×Γ
∗. Duas transições
δ(e1, a1, b1) = [e
′
1, z1] e δ(e2, a2, b2) = [e
′
2, z2] são ditas compat́ıveis se e somente se:
e1 = e2 e (a1 = a2 ou a1 = λ ou a2 = λ) e (b1 = b2 ou b1 = λ ou b2 = λ).
Note-se, na Definição 33, que a compatibilidade não depende dos estados destino
nem das palavras a empilhar. Para algumas pessoas pode parecer mais intuitivo o
complemento da expressão apresentada na definição: duas transições δ(e1, a1, b1) =
[e′1, z1] e δ(e2, a2, b2) = [e
′
2, z2] são não compat́ıveis se e somente se:
e1 6= e2 ou (a1 6= a2 e a1 6= λ e a2 6= λ) ou (b1 6= b2 e b1 6= λ e b2 6= λ).
Apesar de um APD admitir transições sob λ, ele não admite transições compat́ıveis.
Logo, qualquer configuração instantânea que seja atingida terá no máximo uma suces-
sora.
Definição 34 Um autômato de pilha determińıstico (APD) é uma sêxtupla (E,Σ,Γ, δ, i, F ),
em que
• E é um conjunto finito de um ou mais elementos denominados estados;
• Σ é o alfabeto de entrada;
• Γ é o alfabeto de pilha;
• δ, a função de transição, é uma função parcial de E ×Σλ×Γλ para E ×Γ
∗, sem
transições compat́ıveis;
• i, um estado de E, é o estado inicial;
• F , subconjunto de E, é o conjunto de estados finais.
As seguintes razões fazem que não haja uma função δ̂ similar àquela do Caṕıtulo 2:
• Pode haver computações que não terminam, como ficou claro na Seção 3.1.
• Além do(s) estado(s) atingido(s), é importante saber o conteúdo da pilha.
Assim, em vez de uma função δ̂, será usada a relação ⊢ definida a seguir.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 139
1 2
a, λ/X
b, X/λ
b, X/λ
Figura 3.4 APD para {anbn |n ∈ N}.
Definição 35 Seja um APD M = (E,Σ,Γ, δ, i, F ). A relação ⊢⊆ (E×Σ∗×Γ∗)2, para
M , é tal que para todo e, e′ ∈ E, a ∈ Σλ, b ∈ Γλ e x ∈ Γ
∗:
[e, ay, bz] ⊢ [e′, y, xz] para todo y ∈ Σ∗ e z ∈ Γ∗ se, e somente se, δ(e, a, b) = [e′, x].
Utilizando a relação
∗
⊢, que corresponde ao fecho reflexivo e transitivo de ⊢, define-se
a seguir o que é a linguagem reconhecida (aceita) por um APD.
Definição 36 Seja um APD M = (E,Σ,Γ, δ, i, F ). A linguagem reconhecida por M é
L(M) = {w ∈ Σ∗ | [i, w, λ]
∗
⊢ [e, λ, λ] para algum e ∈ F}.
Uma palavra w tal que [i, w, λ]
∗
⊢ [e, λ, λ], em que e ∈ F , é dita ser reconhecida (aceita)
por M .
Exemplo 72 No Exemplo 50, página 87, mostrou-se que o conjunto {anbn |n ∈ N}
não é uma linguagem regular. Ela é reconhecida pelo autômato de pilha determińıstico
({1, 2}, {a, b}, {X}, δ, 1, {1, 2}), em que δ é dada por:
δ(1, a, λ) = [1, X];
δ(1, b, X) = [2, λ];
δ(2, b, X) = [2, λ].
O diagrama de estados está ilustrado na Figura 3.4.
No exemplo anterior, a pilha foi utilizada para conter o número de as em excesso
(com relação ao número de bs) lido até o momento atual; e os dois estados garantem que
o processamento dos as anteceda o dos bs. Veja-se, então, que parte das informações
coletadas (até certo instante do processamento) é armazenada na pilha e parte nos
estados. Evidentemente, o número de as só pode ser anotado na pilha, visto que ele
pode ser um número natural qualquer. Os dois exemplos a seguir, mostram que às
vezes pode-se escolher entre guardar uma informação em estados ou na pilha. (Na
Seção 3.4.4 será visto que, para a versão não determińıstica, toda informação pode ser
guardada na pilha, o estado inicial servindo apenas para “dar partida”.)
140 Editora Thomson Introdução aos fundamentos da computação
igm0 m1
0, λ/F
1, λ/F
0, λ/X
1, X/λ
1, F/λ
1, λ/X
0, X/λ
0, F/λ
Figura 3.5 APD para número igual de 0s e 1s/versão 1.
Exemplo 73 A Figura 3.5 apresenta o diagrama de estados de um APD M que reco-
nhece a linguagem {w ∈ {0, 1}∗ |n0(w) = n1(w)}. Tem-se que
M = ({ig,m0,m1}, {0, 1}, {Z, U, F}, δ, ig, {ig})
sendo δ dada por:
1. δ(ig, 0, λ) = [m0, F];
2. δ(ig, 1, λ) = [m1, F];
3. δ(m0, 0, λ) = [m0, X];
4. δ(m0, 1, X) = [m0, λ];
5. δ(m0, 1, F) = [ig, λ];
6. δ(m1, 1, λ) = [m1, X];
7. δ(m1, 0, X) = [m1, λ];
8. δ(m1, 1, F) = [ig, λ].
No estado ig a pilha estará vazia e, além disso, o número de 0s será igual ao de 1s.
O estado m0 é atingido se e somente se o número de 0s lido até o momento é maior
do que o de 1s; neste caso, a pilha contém o excesso de 0s com relação ao número de
1s. Analogamente, o estado m1 é atingido se e somente se o número de 1s lido até o
momento é maior do que o de 0s; nocaso, a pilha contém o excesso de 1s com relação
a 0s. Portanto, a informação de que o número de 0s é igual ao de uns (estado ig) ou
o de 0s é maior que o de 1s (estado m0) ou o de 1s é maior que o de 0s (estado m1)
é dada pelos estados. Já a informação do excesso de um dos śımbolos com relação ao
outro é dado pela pilha.
A seguinte computação mostra que 001110 pertence à linguagem reconhecida por
M :
[ig, 001110, λ] ⊢ [m0, 01110, F] por 1
⊢ [m0, 1110, XF] por 3
⊢ [m0, 110, F] por 4
⊢ [ig, 10, λ] por 5
⊢ [m1, 0, F] por 2
⊢ [ig, λ, λ] por 7.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 141
= 6=
1, λ/UF
0, λ/ZF
λ, F/λ
0, U/λ
0, Z/ZZ
1, U/UU
1, Z/λ
Figura 3.6 APD para número igual de 0s e 1s/versão 2.
No exemplo a seguir, a informação de qual śımbolo está em excesso, que no exemplo
anterior é dada pelos estados, é colocada na pilha.
Exemplo 742 A Figura 3.6 apresenta o diagrama de estados de um outro APD que
reconhece a linguagem {w ∈ {0, 1}∗ |n0(w) = n1(w)}. Observe que, como requerido,
não há transições compat́ıveis. Após lido um prefixo x da palavra de entrada:
• se n0(x) > n1(x), o estado atual é 6= e a pilha contém Z
nF, sendo n = n0(x) −
n1(x);
• se n1(x) > n0(x), o estado atual é 6= e a pilha contém U
nF, sendo n = n1(x) −
n0(x);
• se n0(x) = n1(x), o estado atual é = e a pilha está vazia ou o estado atual é 6= e
a pilha contém F.
No caso em que n0(x) = n1(x) e o estado atual é 6= e a pilha contém F, a única transição
aplicável é a de 6= para = sob λ substituindo F por λ, mesmo que exista um próximo
śımbolo a ser lido.
Os Exemplos 73 e 74 utilizam uma técnica que possibilita marcar o fundo da pi-
lha: foi introduzido um śımbolo de pilha (F) especificamente para isso. Algumas for-
malizações de APDs incluem um śımbolo especial para tal propósito. No entanto, a
introdução de um śımbolo especial de fundo de pilha não aumenta o poder de reco-
nhecimento dos APDs, já que um śımbolo de pilha comum pode fazer seu papel, como
mostram os exemplos citados. A seguir mais um exemplo de uso de marcação do fundo
de pilha.
Exemplo 75 A Figura 3.7 mostra o diagrama de estados de um APD que reconhece
{0m1n |m ≤ n}.
Novamente, de forma similar ao que se fez no exemplo da Figura 3.5, o marcador
F é usado para detectar quando o fundo de pilha é atingido, que é quando, ao ler o
próximo 1, o número de 1s se torna igual ao de 0s.
2 O APD apresentado nesse exemplo foi desenvolvido por Jonatan Schröeder, na época (segundo
semestre de 2000), aluno da UFPR.
142 Editora Thomson Introdução aos fundamentos da computação
0, λ/F
1, λ/λ
0, F/XF
0, X/XX
1, X/λ
1, F/λ
1, X/λ
1, F/λ
1, λ/λ
Figura 3.7 Mais um APD com marcação de fundo de pilha.
0s 1s
f
0, λ/X
1, X/λ
#, λ/λ
1, X/λ
#, λ/λ
λ, X/λ
Figura 3.8 APD com śımbolo de final de palavra.
Existem linguagens que podem ser reconhecidas por autômatos de pilha não deter-
mińısticos, mas que não podem ser reconhecidas por APDs, como será visto na próxima
seção. Dentre essas, existem algumas que passam a ser reconhecidas por APDs, caso
haja um śımbolo espećıfico para finalizar a palavra de entrada. Segue um exemplo.
Exemplo 76 A Figura 3.8 apresenta o diagrama de estados de um APD que reconhece
a linguagem
{0m1n# |m ≥ n}.
Note que o śımbolo # só é utilizado para finalizar as palavras da linguagem. A lingua-
gem similar, sem tal śımbolo,
{0m1n |m ≥ n},
não pode ser reconhecida por APD, como pode ser verificado.3
Observe que, para cada 0, alguma coisa deve ser empilhada para, no futuro, garantir-
se que o número de 1s não ultrapasse o de 0s. Mas, após lido o prefixo de 0s, caso
possa ser lido mais algum 1 (conforme indicado pela pilha), pode-se também terminar
a palavra. Nesse último caso, a pilha deve ser esvaziada sem leitura de mais śımbolos.
O śımbolo para indicar final de palavra propicia, justamente, reconhecer deterministi-
camente o momento de parar a leitura e esvaziar a pilha.
3 Na verdade, essa linguagem pode ser reconhecida por APD, mas com outro critério de reconheci-
mento, como será visto na Seção 3.3.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 143
A definição de reconhecimento dada na Definição 36, página 139, não faz referência
à parada da máquina. Assim, por exemplo, a linguagem reconhecida pelo APD cujo dia-
grama de estados está ilustrado na Figura 3.3, página 137, é {λ}, não sendo importante
se o APD para ou não para essa entrada.
Ao contrário dos autômatos finitos, os autômatos de pilha têm o seu poder aumen-
tado quando se introduz não determinismo, como será visto na próxima seção. Depois,
na Seção 3.4, serão estudadas as gramáticas livres do contexto, que geram exatamente
as linguagens reconhećıveis por autômatos de pilha. Isso é importante, já que, na maio-
ria das situações que ocorrem na prática, é mais fácil e conveniente obter uma gramática
para a linguagem e, a partir da gramática, obter o autômato de pilha (determińıstico
ou não).
Exerćıcios
1. Mostre que duas transições são compat́ıveis (veja a Definição 33, página 138)
se, e somente se, elas podem ocorrer simultaneamente para alguma configuração
instantânea.
2. Construa APDs para as seguintes linguagens:
a) {0n12n |n ≥ 0};
b) {03n12n |n ≥ 0};
c) {w0wR |w ∈ {1, 2}∗};
d) {anbkcn |n, k ≥ 0};
e) {anbicj |n = i+ j};
f) {0m1n |m < n};
g) {0n1n012 |n ∈ N};
h) {0m1n# |m 6= n};
i) {w# |w ∈ {0, 1}∗ e n0(w) > n1(w)}.
3. Explique por que não há APD para as seguintes linguagens:
a) {wwR |w ∈ {1, 2}∗};
b) {0m1n |m > n};
c) {0m1n |m 6= n};
d) {w ∈ {0, 1}∗ |n0(w) > n1(w)}.
4. Construa um APD que reconheça toda palavra com parênteses balanceados.
Exemplos de palavras da linguagem: λ, (), (())(). Exemplos de palavras que
não pertencem à linguagem: (, )(, ()).
Generalize para o caso em que existem n tipos de parênteses. Nesse caso, considere
que cada ocorrência de abre parênteses, ai, deve ser seguida à direita por uma
ocorrência do fecha parênteses respectivo, bi, e entre ai e bi só pode ocorrer
144 Editora Thomson Introdução aos fundamentos da computação
uma palavra com parênteses balanceados. Se i = 2, a1 = (, b1 = ), a2 = [,
b2 = ], seriam exemplos de palavras da linguagem: λ, (), [()](), [[()]()]([]).
Exemplos de palavras que não pertencem à linguagem: (, ][, ()], (], ([)].
5. Construa um APD que reconheça as expressões aritméticas na forma prefixada,
EAPre, definidas recursivamente como segue:
a) a é uma EAPre;
b) se x e y são EAPre, então +xy e −xy são EAPre.
Dica: Sempre que ler + ou −, empilhe dois Xs, para “lembrar” de ler duas
subexpressões à frente.
6. Construa um APD que reconheça as expressões aritméticas na forma posfixada,
EAPos, definidas recursivamente como segue:
(a) a é uma EAPos;
(b) se x e y são EAPos, então xy+ e xy− são EAPos.
Dica: Use os seguintes fatos, fáceis de mostrar por indução: o número de as é um
a mais que o de operadores, e qualquer palavra que tenha mais as que operadores
é prefixo de EAPos.
3.3 Autômatos de Pilha Não Determińısticos
A diferença entre um autômato de pilha determińıstico e um não determińıstico é
que esse último pode conter transições compat́ıveis, como pode ser visto na definição
a seguir.
Definição 37 Um autômato de pilha não determińıstico (APN ) é uma sêxtupla
(E,Σ,Γ, δ, I, F ), em que
• E, Σ, Γ e F são como em APDs;
• δ, a função de transição, é uma função parcial de E ×Σλ × Γλ para D, sendo D
constitúıdo dos subconjuntos finitos de E × Γ∗;
• I, um subconjunto de E, é o conjunto de estados iniciais.
A relação
∗
⊢ da Definição 35, página 139, será utilizada para definir o reconheci-
mento para APNs, de forma similar ao reconhecimento para APDs apresentado na
Definição 36.
Definição 38 Seja um APN M = (E,Σ,Γ, δ, I, F ). A linguagem reconhecida por M é
L(M) = {w ∈ Σ∗ | [i, w, λ]
∗
⊢ [e, λ, λ] paraalgum i ∈ I e e ∈ F}.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 145
= 6=
1, λ/U
0, λ/Z
λ, λ/λ
0, U/λ
0, Z/ZZ
1, U/UU
1, Z/λ
Figura 3.9 APN para número igual de 0s e 1s.
Uma palavra w tal que [i, w, λ]
∗
⊢ [e, λ, λ], sendo i ∈ I e e ∈ F , é dita ser reconhecida
(aceita) por M .
Segue um exemplo que mostra a evolução de um APD para um APN equivalente
“mais conciso”.
Exemplo 77 No Exemplo 74, página 141, foi visto umAPD para {w ∈ {0, 1}∗ |n0(w) =
n1(w). Nele é usado o śımbolo F para marcar o fundo da pilha, de forma que, quando
os números de 0s e de 1s se tornam idênticos (mesmo que a palavra não tenha sido toda
processada ainda), seja ativada a transição para o estado final =. Ora, um autômato
não determińıstico pode “adivinhar” quando a pilha se torna vazia e fazer a transição
citada. Assim, um APN equivalente ao APD do Exemplo 74 seria:
N = ({=, 6=}, {0, 1}, {Z, U}, δ, {=}, {=}),
em que δ é dada por:
1. δ(=, 0, λ) = {[6=, Z]};
2. δ(=, 1, λ) = {[6=, U]};
3. δ(6=, 0, Z) = {[6=, ZZ]};
4. δ(6=, 0, U) = {[6=, λ]};
5. δ(6=, 1, U) = {[6=, UU]};
6. δ(6=, 1, Z) = {[6=, λ]};
7. δ(6=, λ, λ) = {[=, λ]}.
O diagrama de estados de N pode ser visto na Figura 3.9. Note que, a única diferença,
com relação ao APD do Exemplo 74, é que, na figura, o śımbolo F foi substitúıdo por λ.
Observe que a transição 7 é compat́ıvel com as transições 3 a 6, mas de uma forma
restrita: partindo-se do estado 6=, quando a pilha está vazia, apenas a transição 7 é
aplicável; somente quando a pilha não está vazia, uma das transições 3 a 6 é aplicável,
além da transição 7. Assim, se for dada prioridade sempre para as transições 3 a 6,
o comportamento do APN é análogo ao do APD do Exemplo 74. Isso evidencia que
esse APN reconhece toda palavra que o referido APD reconhece. Contudo, tal APN
146 Editora Thomson Introdução aos fundamentos da computação
= 6=
1, λ/U
0, λ/Z
λ, λ/λ
0, U/λ
1, Z/λ
(a) O segundo
0, λ/Z
1, λ/U
0, U/λ
1, Z/λ
(b) O terceiro
Figura 3.10 Mais dois APNs para número igual de 0s e 1s.
1 2
λ, λ/λ
0, λ/λ
1, λ/λ
0, λ/0
1, λ/1
0, 0/λ
1, 1/λ
Figura 3.11 APN para paĺındromos sobre {0, 1}∗.
continua não podendo reconhecer palavras com números diferentes de 0s e 1s, como
pode ser notado verificando-se o padrão de empilhamentos e desempilhamentos.
Na realidade, o APN N é menos conciso do que poderia ser. As transições 3 e 5
são desnecessárias. O mesmo efeito da transição 3 pode ser conseguido aplicando-se,
em sequência, as transições 7 (compat́ıvel com a 3) e 1, e o mesmo efeito da transição
5 pode ser obtido aplicando-se, em sequência, as transições 7 (compat́ıvel com a 5) e 2.
Obtém-se, com isso, o APN cujo diagrama de estados está mostrado na Figura 3.10a.
Analisando-se esse último diagrama de estados, levando-se em conta que o reconheci-
mento se dá quando a pilha fica vazia, chega-se ao APN equivalente cujo diagrama de
estados está ilustrado na Figura 3.10b.
A seguir, é apresentado um APN para uma linguagem que não pode ser reconhecida
por APDs.
Exemplo 78 Na Figura 3.11 está representado o diagrama de estados para um APN
que reconhece a linguagem {w ∈ {0, 1}∗ |w = wR}.
Caso uma palavra w seja paĺındromo, existirá uma computação para w em que w é
consumida e a pilha fica vazia; para tal computação, uma das três transições de 1 para
2 é percorrida:
• se |w| for par, será percorrida a transição de 1 para 2 sob λ;
• se |w| for ı́mpar e o śımbolo do meio for 0, será percorrida a transição de 1 para
2 sob 0;
• se |w| for ı́mpar e o śımbolo do meio for 1, será percorrida a transição de 1 para
2 sob 1.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 147
Ao processar uma palavra da esquerda para a direita, quando atinge o meio da
palavra, não há como o autômato reconhecer tal fato, para, a partir dáı, comparar a
segunda metade com a primeira. Assim sendo, não há como construir um APD para a
linguagem dos paĺındromos.
Pela Definição 38, a linguagem reconhecida por um APN M = (E,Σ,Γ, δ, I, F ) é
L(M) = {w ∈ Σ∗ | [i, w, λ]
∗
⊢ [e, λ, λ] para algum i ∈ I e e ∈ F}.
Uma definição alternativa, que levaria a uma concepção diferente de APNs, é aquela
em que o reconhecimento de uma palavra se dá ao ser atingido um estado final, após
ser consumida a palavra de entrada, esteja a pilha vazia ou não. Usando o ı́ndice F em
LF (M) para significar reconhecimento por estado final, segue tal definição alternativa,
mais formalmente.
Definição 39 Seja um APN M = (E,Σ,Γ, δ, I, F ). A linguagem reconhecida por M
por estado final é
LF (M) = {w ∈ Σ
∗ | [i, w, λ]
∗
⊢ [e, λ, y] para algum i ∈ I, e ∈ F e y ∈ Γ∗}.
Uma palavra w tal que [i, w, λ]
∗
⊢ [e, λ, y], sendo i ∈ I, e ∈ F e y ∈ Γ∗, é dita ser
reconhecida (aceita) por M por estado final.
O reconhecimento, segundo a Definição 38, será denominado, a seguir, reconheci-
mento por pilha vazia e estado final.
Pode-se mostrar que uma linguagem pode ser reconhecida por pilha vazia e es-
tado final se, e somente se, pode ser reconhecida por estado final, como será visto no
Teorema 18 no final desta seção.
O exemplo a seguir apresenta dois autômatos de pilha que reconhecem a mesma
linguagem, um deles utilizando reconhecimento por pilha vazia e estado final, e o outro
usando reconhecimento por estado final.
Exemplo 79 Seja o problema de determinar um APN que reconheça a linguagem
L = {0m1n |m ≥ n}.
A Figura 3.12a mostra o diagrama de estados de um APN M tal que L(M) = L,
sendo que M reconhece por pilha vazia e estado final, enquanto a Figura 3.12b ilustra
o diagrama de estados de um APN M ′ tal que LF (M
′) = L, sendo que M ′ reconhece
por estado final. Veja que, por coincidência, o diagrama de estados da Figura 3.12b
é idêntico ao da Figura 3.4, página 139, que reconhece a linguagem {anbn |n ≥ 0}
por pilha vazia e estado final (substituindo-se 0 por a e 1 por b); assim, L(M ′) =
{0n1n |n ≥ 0}. Observe também que LF (M) = L: coincidentemente, o APN cujo
diagrama de estados pode ser observado na Figura 3.12a reconhece a mesma linguagem
para os dois métodos de reconhecimento.
148 Editora Thomson Introdução aos fundamentos da computação
0 1
1, X/λ
0, λ/λ
0, λ/X 1, X/λ
(a) Aceitação por pilha vazia e estado final
0 1
1, X/λ
0, λ/X 1, X/λ
(b) Aceitação por estado final
Figura 3.12 APNs para {0m1n |m ≥ n}.
Outra definição alternativa é aquela em que o reconhecimento de uma palavra se dá
quando a pilha fica vazia, após ser consumida a palavra de entrada. Nesse caso, não há
o conceito de estado final. Usando o ı́ndice V em LV (M) para significar reconhecimento
por pilha vazia, segue tal definição alternativa, observando a ausência do conjunto de
estados finais.
Definição 40 Seja um APN M = (E,Σ,Γ, δ, I). A linguagem reconhecida por M por
pilha vazia é
LV (M) = {w ∈ Σ
∗ | [i, w, λ]
∗
⊢ [e, λ, λ] para algum i ∈ I e e ∈ E}.
Uma palavra w tal que [i, w, λ]
∗
⊢ [e, λ, λ], sendo que i ∈ I, é dita ser reconhecida
(aceita) por M por pilha vazia.
Note que, por essa definição, λ é sempre reconhecida, já que a pilha começa vazia.
Será mostrado também, no Teorema 18, que uma linguagem com a palavra λ pode ser
reconhecida por pilha vazia e estado final se, e somente se, pode ser reconhecida por
pilha vazia.
O APN cujo diagrama de estados está ilustrado na Figura 3.12a reconhece a lin-
guagem {0m1n |m ≥ n} também por pilha vazia, visto que todos os seus estados são
estados finais. Aliás, se um APN M = (E,Σ,Γ, δ, I) reconhece LV (M), então o APN
M ′ = (E,Σ,Γ, δ, I, E) (observe que todos os estados são finais em M ′) reconhece
LV (M) por pilha vazia e estado final.
Exemplo 80 Seja o APN cujo diagrama de estados está representado na Figura 3.13.
Tal APN reconhece a linguagem {0m1n |m ≤ n} por pilha vazia. Considerando todos
os seus estados como estados finais, ele reconhece a mesma linguagem por pilha vazia
e estado final.
O teorema a seguirmostra a equivalência dos três métodos de reconhecimento. A
equivalência segue do uso de três métodos: (a) um que mostra como obter um AP que
reconhece por estado final equivalente a um que reconheça por pilha vazia e estado final,
(b) outro que revela como chegar a um AP que reconhece por pilha vazia equivalente
a um que reconheça por estado final, e (c) finalmente, um método que mostra como
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 149
0 1
1, X/λ
0, λ/X
λ, λ/X 1, X/λ
Figura 3.13 APN para {0m1n |m ≤ n}.
M
· · ·i′
i1
...
im
f1
fn
...
g
λ, λ/F
λ, λ/F
λ, F/λ
λ, F/λ
I F
Figura 3.14 Obtenção de AP pelo Método 12.
obter um AP que reconhece por estado final e pilha vazia equivalente a um outro que
reconheça por pilha vazia. Antes do teorema, seguem os três métodos.
Método 12 De reconhecimento padrão ao por estado final
Seja um APN M = (E,Σ,Γ, δ, I, F ). É posśıvel obter, a partir de M , um APN M ′ de
modo que LF (M
′) = L(M). A idéia central é utilizar um śımbolo de pilha novo para
marcar o fundo da pilha, de forma que M ′ possa reconhecer quando M estaria com a
pilha vazia.
Serão usados, além dos estados em E, mais dois estados i′, g 6∈ E, e, além dos
śımbolos de Γ, mais um śımbolo de pilha F 6∈ Γ. Basta fazer M ′ = (E ∪ {i′, g},Σ,Γ ∪
{F}, δ′, {i′}, {g}) (veja a Figura 3.14 para uma representação esquemática de M ′), tal
que δ′ inclui δ mais as seguintes transições:
• para cada ik ∈ I, δ
′(i′, λ, λ) = {[ik, F]};
• para cada fj ∈ F , δ
′(fj , λ, F) = {[g, λ]}.
Método 13 De reconhecimento por estado final ao por pilha vazia
Seja um APN M = (E,Σ,Γ, δ, I, F ). Um APN M ′ tal que LV (M
′) = LF (M) ∪ {λ}
seria M ′ = (E∪{i′, g, h},Σ,Γ∪{F}, δ′ , {i′}) (veja a Figura 3.15 para uma representação
esquemática de M ′), tal que i′, g, h 6∈ E, F 6∈ Γ e δ′ inclui δ mais as seguintes transições:
• para cada ik ∈ I, δ
′(i′, λ, λ) = {[ik, F]};
• para cada fj ∈ F , δ
′(fj , λ, λ) = {[g, λ]};
150 Editora Thomson Introdução aos fundamentos da computação
M
· · ·i′
i1
...
im
f1
fn
...
g h
λ, λ/F
λ, λ/F
λ, λ/λ
λ, λ/λ
λ, X/λ ∀X ∈ Γ
λ, F/λ
I F
Figura 3.15 Obtenção de APN pelo Método 13.
• para cada X ∈ Γ, δ(g, λ,X) = {[g, λ]};
• δ(g, λ, F) = {[h, λ]}.
O śımbolo de pilha F é utilizado aqui para evitar que a pilha fique vazia, exceto quando
a palavra deva ser reconhecida. A pilha fica vazia se, e somente se, for atingido o
estado h.
Teorema 18 Seja L uma linguagem. As seguintes afirmativas são equivalentes:
a) L pode ser reconhecida por pilha vazia e estado final.
b) L pode ser reconhecida por estado final.
c) L ∪ {λ} pode ser reconhecida por pilha vazia.
Prova
(a)→ (b)
Seja um APN qualquer M . O AP M ′, obtido de acordo com o Método 12, é tal
que LF (M
′) = L(M), de onde se segue que se L pode ser reconhecida por pilha vazia
e estado final, então L pode ser reconhecida por estado final.
(b)→ (c)
De um APN M que reconheça por estado final, pode-se construir via o Método 13
um APN M ′ tal que LV (M
′) = LF (M) ∪ {λ}. Logo, se L pode ser reconhecida por
estado final, então L ∪ {λ} pode ser reconhecida por pilha vazia.
(c)→ (a)
Como já foi ressaltado, um APN que reconhece por pilha vazia é um APN que
reconhece por pilha vazia e estado final, bastando considerar todos os seus estados
como estados finais. Ou seja, se M = (E,Σ,Γ, δ, I), um APN M ′ tal L(M ′) = LV (M)
seria, então, M ′ = (E,Σ,Γ, δ, I, E). Observe que, como LV (M) contém λ, L(M
′)
também contém. Embora não seja mostrado aqui como, é posśıvel também obter M ′
tal que L(M ′) = LV (M)− {λ}.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 151
Daqui para a frente, será usada também a expressão AP para designar autômato
de pilha (não determińıstico).
Exerćıcios
1. Seja o AP M = ({i, f}, {a, b}, {B, C}, δ, {i}, {f}), em que δ é dada por:
δ(i, a, λ) = [i, B]
δ(i, λ, λ) = [f, λ]
δ(f, b, B) = [f, C]
δ(f, c, C) = [f, λ]
a) Exiba as computações para as palavras aa, bb, aabcc e aabcbc. Quais destas
palavras são reconhecidas por M?
b) Que linguagem é reconhecida por M?
2. Construa um AP com um alfabeto de pilha contendo apenas dois śımbolos, que
reconheça {w ∈ {a, b, c, d}∗ |w = wR}.
3. Para as seguintes linguagens, construa APD, se posśıvel. Se não for posśıvel,
construa APN.
a) {(01)n1(10)n |n ∈ N};
b) {(01)n0(10)n |n ∈ N};
c) {anb2nc2k |n, k ∈ N};
d) {anb2na2k |n, k ∈ N};
e) {anb2na2k |n ≥ 1, k ∈ N};
f) {an(abc)n |n ∈ N}.
4. Construa APNs que reconheçam as linguagens seguintes por pilha vazia e estado
final:
a) {0n1n |n ≥ 0} ∪ {0n12n |n ≥ 0};
b) {0n1k |n ≤ k ≤ 2n};
c) {0n1n0k |n, k ≥ 0};
d) {0m1n |m > n}.
5. Construa APDs que reconheçam {anbn |n ≥ 0}:
a) por estado final;
b) por pilha vazia.
6. Construa APDs que reconheçam por estado final as linguagens:
a) {ambn |m 6= n};
152 Editora Thomson Introdução aos fundamentos da computação
b) O complemento de {ambn |m ≥ n};
c) O complemento de {anbn |n ≥ 0}.
7. Construa APNs que reconheçam as linguagens do Exerćıcio 4:
a) por estado final;
b) por pilha vazia.
8. Mostre que um APN em que é empilhado no máximo um śımbolo por transição
tem o mesmo poder que um APN normal.
9. Mostre como obter um APN, cuja pilha receba no máximo um śımbolo, que seja
equivalente a um AFNλ dado.
10. Obtenha umAPD que reconheça por estado final a linguagem L = {w ∈ {0, 1}∗ |n0(w) 6=
n1(w)}. A partir dele, obtenha um APD que reconheça L{#} por pilha vazia e
estado final.
11. Mostre que toda linguagem regular pode ser reconhecida por algum APD sob
qualquer um dos três critérios de reconhecimento. Para isso, mostre como obter,
a partir de qualquer AFD, os APDs equivalentes para cada um dos critérios de
reconhecimento.
12. Mostre como obter um APM ′ a partir de um APM , tal que L(M ′) = L(M)−{λ}.
3.4 Gramáticas Livres do Contexto
O seguinte trecho é uma parte de uma gramática livre do contexto, na notação BNF,4
que define uma parte da sintaxe de uma linguagem de programação similar àquela que
é utilizada para a apresentação dos algoritmos deste texto:
4 Em inglês, Backus-Naur Form.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 153
〈programa〉 ::= 〈declarações〉 ; 〈lista-de-cmds〉 .
...
〈lista-de-cmds〉 ::= 〈comando〉 ; 〈lista-de-cmds〉 |
λ
〈comando〉 ::= 〈cmd-enquanto〉 |
〈cmd-se〉 |
〈cmd-atribuição〉 |
· · ·
〈cmd-enquanto〉 ::= enquanto 〈exp-lógica〉 faça
〈lista-de-cmds〉 fimenquanto
〈cmd-se〉 ::= se 〈exp-lógica〉 então
〈lista-de-cmds〉 〈senaoses〉 〈senao〉 fimse
〈senaoses〉 ::= senãose 〈exp-lógica〉 então
〈lista-de-cmds〉 〈senaoses〉 |
λ
〈senao〉 ::= senão 〈lista-de-cmds〉 |
λ
〈cmd-atribuição〉 ::= 〈variável〉 ← 〈expressão〉
Nessa notação, o lado esquerdo de uma regra é separado do lado direito pela
sequência ”::=“. As variáveis figuram entre “〈” e “〉”. Os outros śımbolos são termi-
nais; por ordem de ocorrência: “;”, enquanto, faça, fimenquanto, se, então,fimse,
senãose, “←”.
Cada regra de uma gramática livre do contexto tem no lado esquerdo apenas uma
variável. No lado direito pode ser colocada uma palavra qualquer constitúıda por
variáveis e/ou terminais.
Existem programas que aceitam uma gramática livre do contexto no formato BNF
e produzem um analisador sintático para a mesma. Apesar da notação BNF ser co-
mumente mais adequada para a descrição de linguagens que ocorrem na prática, como
as linguagens de programação, a notação formal a ser introduzida na próxima seção é
mais adequada para o estudo de gramáticas livres do contexto em geral. Após isso, na
Seção 3.4.2, serão apresentados os conceitos de árvore de derivação e de ambiguidade
de gramáticas, muito importantes por terem grande repercussão em aplicações que en-
volvem o uso de gramáticas como base no processamento de linguagens. Depois, na
Seção 3.4.3 será abordado o problema de manipular as regras de uma gramática com
o objetivo de que a gramática resultante tenha certas caracteŕısticas.Para finalizar,
na Seção 3.4.4 será mostrada a equivalência dos formalismos de gramáticas livres do
contexto e autômatos de pilha.
3.4.1 Definição e exemplos
Segue a definição de gramática livre do contexto.
Definição 41 Uma gramática livre do contexto (GLC ) é uma gramática (V,Σ, R, P ),
em que cada regra tem a forma X → w, em que X ∈ V e w ∈ (V ∪ Σ)∗.
154 Editora Thomson Introdução aos fundamentos da computação
Para uma GLC, em cada passo de uma derivação deve-se escolher, na forma sen-
tencial, a variável A a ser substitúıda pelo lado direito de uma regra com A do lado
esquerdo. Ao se fazer tal substituição, diz-se que A é expandida.
Observe que uma gramática regular é uma gramática livre do contexto especial, em
que toda derivação produz uma forma sentencial contendo uma única variável, que é
sempre o śımbolo mais à direita. Todavia, existem linguagens que não são regulares e
que, portanto, não podem ser geradas por GRs, mas que podem ser geradas por GLCs.
A seguir são mostrados alguns exemplos.
Exemplo 81 A linguagem não regular {0n1n |n ∈ N} é gerada pela gramática livre
do contexto G = ({P}, {0, 1}, R, P ), em que R consta das duas regras:
P → 0P1 |λ
As únicas palavras geradas por tal gramática são aquelas que podem ser geradas por
n aplicações da regra P → 0P1, n ≥ 0, seguidas de uma aplicação da regra P → λ.
Esquematicamente: P
n
⇒ 0nP1n ⇒ 0n1n. Logo, L(G) = {0n1n |n ∈ N}.
Exemplo 82 A gramática G, a seguir, gera os paĺındromos sobre {0, 1}, ou seja,
L(G) = {w ∈ {0, 1}∗ |w = wR}. G = ({P}, {0, 1}, R, P ), em que R consta das cinco
regras:
P → 0P0 | 1P1 | 0 | 1 |λ
Aplicando-se as duas primeiras regras, gera-se qualquer forma sentencial do tipo wPwR,
para w ∈ {0, 1}∗. Por fim, para gerar uma palavra, aplica-se uma das três últimas regras
de G; a última, quando a palavra apresenta tamanho par, e uma das outras, quando
ela tem tamanho ı́mpar.
Exemplo 83 A linguagem L = {w ∈ {0, 1}∗ |n0(w) = n1(w)} é gerada pela gramática
G = ({P}, {0, 1}, R, P ), em que R consta das três regras:
P → 0P1P | 1P0P |λ
Como o lado direito de cada uma das três regras possui número igual de 0s e 1s, G só
gera palavras de L. O fato de que G produz todas as palavras de L vem do fato de que
para toda palavra w de L, tem-se um dos três casos:
a) w = λ; nesse caso, basta aplicar a regra P → λ;
b) w = 0y para algum y ∈ {0, 1}∗ e y tem um 1 a mais que 0s; logo, y é da forma
x1z, onde x tem número igual de 0s e 1s e z também tem número igual de 0s e
1s; assim, basta iniciar a derivação de w com a primeira regra;
c) w = 1y para algum y ∈ {0, 1}∗ e y tem um 0 a mais que 1s; por motivo análogo
ao segundo caso, basta aplicar a segunda regra.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 155
Nos casos (b) e (c), têm-se novamente (recursivamente) os três casos aplicados para
as subpalavras x e z. Com isso, obtém-se um método para construir uma derivação
de qualquer palavra de L. A seguinte derivação de 01010110 ilustra a aplicação do
método subjacente, em que a variável expandida é sempre a mais à esquerda:
P ⇒ 0P1P P → 0P1P (x = 10; z = 0110)
⇒ 01P0P1P P → 1P0P (x = λ; z = λ)
⇒ 010P1P P → λ
⇒ 0101P P → λ
⇒ 01010P1P P → 0P1P (x = λ; z = 10)
⇒ 010101P P → λ
⇒ 0101011P0P P → 1P0P (x = λ; z = λ)
⇒ 01010110P P → λ
⇒ 01010110 P → λ.
O exemplo a seguir ilustra uma gramática que contém a essência da especificação
da sintaxe das expressões aritméticas das linguagens de programação usuais.
Exemplo 84 Seja a GLC ({E,T, F}, {a,+, ∗, (, )}, R,E), para expressões aritméticas,
em que R consta das regras:
E → E+T |T
T → T∗F |F
F → (E) | a
As duas primeiras regras dizem que uma expressão aritmética, E, é constitúıda por um
ou mais termos, T s, somados. As duas seguintes dizem que um termo é composto de
um ou mais fatores, F s, multiplicados. E as duas últimas dizem que um fator é terminal
a ou, recursivamente, uma expressão aritmética entre parênteses. Essa gramática será
utilizada em vários exemplos daqui para a frente.
Adiante, na Seção 3.4.4, será mostrado que as linguagens geradas por gramáticas
livres do contexto são exatamente as reconhecidas por autômatos de pilha. A definição
a seguir dá um nome à classe formada por tais linguagens.
Definição 42 Uma linguagem é dita ser uma linguagem livre do contexto se existe
uma gramática livre do contexto que a gera.
Em geral, existem várias derivações de uma mesma palavra da linguagem gerada
por uma gramática. Note que no Exemplo 83, página 154, inicia-se uma derivação de
01010110 por
P ⇒ 0P1P (regra P → 0P1P ).
156 Editora Thomson Introdução aos fundamentos da computação
E, após isso, a variável expandida é sempre a mais à esquerda. Pode-se ver que a mesma
palavra pode ser derivada expandindo-se sempre a variável mais à direita em vez da
variável mais à esquerda. E mais, a mesma palavra pode ser derivada expandindo-se
variáveis em ordem aleatória. Isto mostra que existem várias derivações distintas para
a palavra 01010110. O que tais derivações têm em comum, além de gerar a mesma
palavra? Esse assunto será abordado na próxima seção.
3.4.2 Derivações e ambiguidade
Um conceito bastante útil, base para muitas implementações de compiladores de lin-
guagens de programação, é o de árvore de derivação (AD). Uma AD captura a essência
de uma derivação, a história da obtenção de uma forma sentencial que não depende da
ordem de aplicação das regras da GLC. A cada derivação vai corresponder uma única
AD, mas a uma AD vai corresponder, quase sempre, uma quantidade muito grande
de derivações. Assim, pode-se dizer que as ADs particionam o conjunto de todas as
derivações de uma GLC em “derivações equivalentes”: duas derivações seriam equiva-
lentes se, e somente se, correspondessem à mesma AD.
Definição 43 Seja uma GLC G = (V,Σ, R, P ). Uma árvore de derivação (AD) de uma
forma sentencial de G é uma árvore ordenada constrúıda recursivamente como segue:
a) uma árvore sem arestas cujo único vértice tem rótulo P é uma AD;
b) se X ∈ V é rótulo de uma folha f de uma AD A, então:
i. se X → λ ∈ R, então a árvore obtida acrescentando-se a A mais um vértice
v com rótulo λ e uma aresta {f, v} é uma AD;
ii. se X → x1x2 . . . xn ∈ R, onde x1, x2, . . . , xn ∈ V ∪Σ, então a árvore obtida
acrescentando-se a A mais n vértices v1, v2, . . . , vn com rótulos x1, x2, . . . ,
xn, nessa ordem, e n arestas {f, v1}, {f, v2}, . . . , {f, vn}, é uma AD.
Se a sequência dos rótulos da fronteira da AD é a forma sentencial w, diz-se que a AD
é uma árvore de derivação de w.
Exemplo 85 Seja a gramática do Exemplo 84 cujas regras são reproduzidas a seguir:
E → E+T |T
T → T∗F |F
F → (E) | a
Na Figura 3.16, mostra-se uma AD de a*(a+a). Para a construção de tal árvore,
tomou-se como ponto de partida a derivação:
E⇒ T (regra E → T )
produzindo-se uma AD de T :
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 157
E
T
Em seguida, a derivação evoluiu para:
E⇒ T (regra E → T )
⇒ T∗F (regra T → T∗F )
e a árvore correspondente (que é uma AD de T∗F ) para:
E
T
T ∗ F
Neste instante, tem-se duas opções para continuar a derivação:
E⇒ T (regra E → T )
⇒ T∗F (regra T → T∗F )
⇒ F∗F (regra T → F )
ou então
E⇒ T (regra E → T )
⇒ T∗F (regra T → T∗F )
⇒ T∗(E) (regra F → (E)).
À esquerda, mostra-se a AD correspondente à primeira derivação, e à direita, a AD
correspondente à segunda derivação:
E
T
T ∗ F
F
E
T
T ∗ F
( E )
Prosseguindo-se por qualquer uma dessas alternativas, chega-se, após uma derivação
de 11 passos, à AD mostrada na Figura 3.16.
158 Editora Thomson Introdução aos fundamentos da computação
E
T
T ∗ F
F ( E )
a +E T
T F
F a
a
Figura 3.16 Uma árvore de derivação de a*(a+a).
Observe que o número de passos de qualquer derivação que leva a uma AD X é o
número de vértices internosde X, já que a cada vértice interno corresponde a aplicação
de uma regra (e vice-versa).
A estrutura da árvore de derivação, muitas vezes, é utilizada para associar signifi-
cado para as sentenças de uma linguagem, de forma similar ao que se faz em análise
sintática de sentenças na ĺıngua portuguesa (em que se identifica sujeito, verbo, predi-
cado etc.). Em português, se a mesma sentença pode ser desmembrada de mais de uma
forma durante a análise, então ela possui vários significados, e diz-se que ela é amb́ıgua.
De forma análoga, se existir mais de uma AD de uma mesma palavra, provavelmente
ela terá mais de um significado. Isso inspira a definição a seguir.
Definição 44 Uma GLC é denominada amb́ıgua quando existe mais de uma AD para
alguma sentença que ela gera.
Observe, no entanto, que a gramática é dita amb́ıgua, não a linguagem que ela gera
nem as sentenças para as quais haja mais de uma AD. Afinal, podem haver outras
GLCs equivalentes a uma GLC amb́ıgua que não sejam amb́ıguas.
Exemplos de gramáticas não amb́ıguas são aquelas dos Exemplos 81, 82 e 84 da
Seção 3.4.1. Já a gramática do Exemplo 83 é amb́ıgua, como mostra o exemplo a
seguir.
Exemplo 86 Seja a gramática do Exemplo 83, cujas regras são:
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 159
P
0 P 1 P
1 P 0 P λ
λ λ
P
0 P 1 P
λ 0 P 1 P
λ λ
Figura 3.17 Duas árvores de derivação de 0101.
P → 0P1P | 1P0P |λ
As duas ADs de 0101 apresentadas na Figura 3.17 demonstram que tal GLC é amb́ıgua.
À árvore da esquerda corresponde, entre outras, a derivação:
P ⇒ 0P1P (regra P → 0P1P )
⇒ 01P0P1P (regra P → 1P0P )
⇒ 010P1P (regra P → λ)
⇒ 0101P (regra P → λ)
⇒ 0101 (regra P → λ)
À árvore da direita corresponde a seguinte derivação, entre outras:
P ⇒ 0P1P (regra P → 0P1P )
⇒ 01P (regra P → λ)
⇒ 010P1P (regra P → 0P1P )
⇒ 0101P (regra P → λ)
⇒ 0101 (regra P → λ)
O próximo exemplo apresenta uma gramática amb́ıgua que gera a linguagem de
expressões aritméticas, gerada também pela gramática não amb́ıgua do Exemplo 84.
Exemplo 87 Seja a gramática G = ({E}, {a,+, ∗, (, )}, R,E), para as expressões arit-
méticas, em que R consta das regras:
E → E+E |E ∗E | (E) | a
Essa gramática é amb́ıgua, já que existem duas ADs da palavra a+a*a, as quais estão
mostradas na Figura 3.18. À árvore da esquerda corresponde, entre outras, a derivação:
160 Editora Thomson Introdução aos fundamentos da computação
E
E + E
a E * E
a a
E
E * E
E + E a
a a
Figura 3.18 Duas árvores de derivação de a+a*a.
E⇒ E+E (regra E → E+E)
⇒ a+E (regra E → a)
⇒ a+E ∗E (regra E → E ∗E)
⇒ a+ a ∗E (regra E → a)
⇒ a+ a ∗ a (regra E → a).
À árvore da direita corresponde a seguinte derivação, entre outras:
E⇒ E ∗E (regra E → E ∗E)
⇒ E+E ∗E (regra E → E+E)
⇒ a+E ∗E (regra E → a)
⇒ a+ a ∗E (regra E → a)
⇒ a+ a ∗ a (regra E → a).
Como já foi dito anteriormente, em geral, o significado é associado a uma palavra
de acordo com a AD obtida. Por exemplo, a AD do lado esquerdo da Figura 3.18 leva à
interpretação de a+a*a como a soma de um elemento com o produto de dois elementos,
isto é, a+(a∗a), enquanto a AD do lado direito da mesma figura leva à interpretação de
a+a*a como o produto da soma de dois elementos com um elemento, ou seja, (a+a)∗a.
Entre as derivações correspondentes a uma AD, existem duas de particular interesse:
as derivações mais à esquerda e as derivações mais à direita.
Definição 45 Uma derivação é dita mais à esquerda (DME ) se em cada passo é ex-
pandida a variável mais à esquerda. E é dita mais à direita (DMD) se em cada passo
é expandida a variável mais à direita. Para enfatizar que uma derivação é mais à
esquerda, pode-se usar “⇒e” em vez de “⇒” e, para uma derivação mais à direita,
pode-se utilizar “⇒d”.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 161
Existe uma única DME e uma única DMD correspondentes a uma AD: para obter
a DME a partir de uma AD, basta ir gerando os passos de derivação à medida em
que se percorre a AD visitando primeiro as subárvores à esquerda, antes de visitar
as subárvores à direita; para obter a DMD, visita-se primeiro as subárvores à direita.
Assim sendo, pode-se dizer que:
• uma GLC é amb́ıgua se, e somente se, existe mais de uma DME para alguma
sentença que ela gere;
• uma GLC é amb́ıgua se, e somente se, existe mais de uma DMD para alguma
sentença que ela gere.
Exemplo 88 No Exemplo 87 foram mostradas as duas DMEs que correspondem às
ADs da Figura 3.18. As duas DMDs que correspondem às mesmas ADs são, para a
primeira AD:
E⇒d E+E (regra E → E+E)
⇒d E+E ∗E (regra E → E ∗E)
⇒d E+E∗ a (regra E → a)
⇒d E+ a ∗ a (regra E → a)
⇒d a+ a ∗ a (regra E → a)
e para a segunda AD:
E⇒d E ∗E (regra E → E ∗E)
⇒d E ∗ a (regra E → a)
⇒d E+E ∗ a (regra E → E+E)
⇒d E+ a ∗ a (regra E → a)
⇒d a+ a ∗ a (regra E → a).
Há linguagens livres do contexto (LLCs) para as quais existem apenas gramáticas
amb́ıguas. Essas linguagens são denominadas linguagens inerentemente amb́ıguas. Um
exemplo de linguagem inerentemente amb́ıgua é {ambnck |m = n ou n = k}. Pode-se
mostrar que qualquer GLC que gere tal linguagem terá mais de uma AD para palavras
da forma anbncn.
A detecção e remoção de ambiguidade em GLCs é muito importante, por exemplo,
como um passo prévio ao uso de uma gramática para a geração de um compilador para
uma linguagem de programação. Na próxima seção serão vistas algumas técnicas de
modificação de GLCs, que não alteram a linguagem gerada. No entanto, infelizmente,
o problema de determinar se uma GLC arbitrária é amb́ıgua é indecid́ıvel, como será
mostrado no Caṕıtulo 5.
Existem dois tipos básicos de analisadores sintáticos gerados5 a partir de GLCs:
o bottom-up e o top-down. Um analisador bottom-up parte do programa, lendo-o da
5 Um analisador sintático é um programa cujo objetivo principal é determinar se um programa está
sintaticamente correto.
162 Editora Thomson Introdução aos fundamentos da computação
esquerda para a direita, e aplica as regras de forma invertida, construindo a AD da
fronteira para a raiz, ou seja, bottom-up; a derivação considerada durante o processo
é uma DMD (obtida de trás para a frente). Por outro lado, um analisador top-down
parte do śımbolo de partida da GLC e constrói a AD da raiz em direção à fronteira,
ou seja, top-down; a derivação considerada é uma DME. Os detalhes estariam fora do
escopo deste texto, e podem ser encontrados em qualquer livro-texto sobre construção
de compiladores. De qualquer forma, fica evidenciada a importância dos três conceitos
do ponto de vista prático: AD, DME e DMD.
A mesma linguagem pode ser gerada por inúmeras gramáticas. Algumas gramáticas
podem ser mais adequadas que outras, dependendo do contexto para o qual elas foram
projetadas. Assim, é importante saber algumas técnicas de manipulação de GLCs de
forma a obter GLCs equivalentes, mas com a presença ou ausência de certa(s) carac-
teŕıstica(s) relevante(s) para determinada aplicação. Em particular, existem algumas
formas normais que são apropriadas em diversas situações, como quando se pretende
mostrar que certa propriedade vale para todas as linguagens livres do contexto. Na
próxima seção, serão apresentadas algumas técnicas de manipulação de GLCs, assim
como duas formas normais importantes.
3.4.3 Manipulação de gramáticas e formas normais
A detecção de variáveis que nunca participam de derivações de palavras da linguagem
gerada por uma GLC, as chamadas variáveis inúteis, é importante por vários motivos.
Por exemplo, em gramáticas grandes, como as de linguagens de programação, pode
acontecer de se esquecer de definir as regras relativas a uma variável; ou, então, uma
variável, apesar de ter suas regras já definidas, pode não ter sido utilizada ainda na
formação de novas regras. Ambos os tipos de variáveis inúteis podem ser detectados.Após a detecção das variáveis inúteis, pode-se acrescentar novas regras para prever a
definição ou uso das variáveis. Ou então, caso uma variável seja efetivamente inútil,
deve-se eliminar todas as regras que possuem alguma ocorrência da mesma.
Segue uma definição precisa de variável útil, assim como algoritmos para a detecção
de variáveis inúteis e um método para eliminar todas as variáveis inúteis de uma GLC.
Definição 46 Seja uma GLC G = (V,Σ, R, P ). Uma variável X ∈ V é dita ser uma
variável útil se, e somente se, existem u, v ∈ (V ∪ Σ)∗ e w ∈ Σ∗ tais que:
P
∗
⇒ uXv
∗
⇒ w.
Observe que, pela Definição 46, para a variável X ser útil é necessário, não apenas
que existam u e v tais que P
∗
⇒ uXv, mas também que, para algum u e algum v, tais
que P
∗
⇒ uXv, se tenha que uXv
∗
⇒ w para algum w ∈ Σ∗.
Exemplo 89 Seja a gramática ({P,A,B,C}, {a, b, c}, R, P ), em queR contém as regras:
P → AB | a
B → b
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 163
C → c
• C é inútil: não existem u e v tais que P
∗
⇒ uCv;
• A é inútil: não existe w ∈ Σ∗ tal que A
∗
⇒ w;
• B é inútil: P
∗
⇒ uBv apenas para u = A e v = λ, e não existe w ∈ Σ∗ tal que
AB
∗
⇒ w (pois não existe w ∈ Σ∗ tal que A
∗
⇒ w).
Eliminando-se essas variáveis e todas as regras que as referenciam, além dos termi-
nais b e c que não ocorrem em nenhuma regra retida,6 tem-se a gramática equivalente
({P}, {a}, {P → a}, P ).
O método de eliminação de variáveis inúteis consta de duas etapas. Na primeira,
elimina-se as variáveis a partir das quais não é posśıvel gerar sentenças (como a variável
A do exemplo anterior). Após tal eliminação, na segunda etapa elimina-se as variáveis
que não ocorram em formas sentenciais deriváveis a partir do śımbolo de partida (como
a variável C do exemplo). A definição a seguir, dá o conjunto de variáveis a partir das
quais é posśıvel gerar sentenças. Usa-se a notação vars(w) para designar o conjunto
das variáveis que ocorrem na palavra w.
Definição 47 O conjunto SG = {X ∈ V |X
∗
⇒ w para algum w ∈ Σ∗}, para uma GLC
G = (V,Σ, R, P ), pode ser assim definido recursivamente:
• X ∈ SG, se existe X → w ∈ R tal que w ∈ Σ
∗;
• se X → w ∈ R e vars(w) ⊆ SG, então X ∈ SG.
A próxima definição mostra como obter o conjunto das variáveis que ocorrem em
formas sentenciais deriváveis em uma GLC.
Definição 48 O conjunto AG = {X ∈ V |P
∗
⇒ uXv para algum u, v ∈ (V ∪Σ)∗}, para
uma GLC G = (V,Σ, R, P ), pode ser assim definido recursivamente:
• P ∈ AG;
• se X → w ∈ R e X ∈ AG, então vars(w) ⊆ AG.
Versões procedurais de ambas as definições, 47 e 48, estão mostradas na Figura 3.19.
Método 14 Eliminação de variáveis inúteis
Considere uma GLC G = (V,Σ, R, P ). A partir de G, obtém-se uma GLC equivalente
sem variáveis inúteis assim:
6 Pode-se dizer que tais terminais são inúteis, visto que não são usados para formar palavras da
linguagem gerada.
164 Editora Thomson Introdução aos fundamentos da computação
Entrada: uma GLC G = (V,Σ, R, P ).
Sáıda: SG = {X ∈ V |X
∗
⇒ w para w ∈ Σ∗}.
SG ← ∅;
repita
N ← {X ∈ V − SG |X → w ∈ R
e vars(w) ⊆ SG};
SG ← SG ∪N
até N = ∅;
retorne SG.
(a) Produzem sentenças
Entrada: uma GLC G = (V,Σ, R, P ).
Sáıda: AG = {X ∈ V |P
∗
⇒ w e X ∈ vars(w)}.
AG ← {P};
repita
N ← {X ∈ V −AG |Y → w para Y ∈ AG
e X ∈ vars(w)};
AG ← AG ∪N
até N = ∅;
retorne AG.
(b) Alcançáveis a partir de P
Figura 3.19 Algoritmos para achar variáveis úteis.
1. Obtenha G′ = (SG ∪ {P},Σ, R
′, P ), em que R′ = {X → w ∈ R | vars(w) ⊆ SG}.
2. Obtenha G′′ = (AG′ ,Σ, R
′′, P ), em que R′′ = {X →∈ R′ |X ∈ AG′}.
Note-se, em particular, que L(G) = ∅ se e somente se P 6∈ SG, e que, mesmo que seja
inútil, P é preservado nas GLCs G′ e G′′ constrúıdas pelo Método 14. Alternativamente
a Σ, pode-se considerar como alfabeto de G′′ o conjunto daqueles terminais que ocorrem
em regras de R′′, desde que se cuide para que Σ tenha no mı́nimo um śımbolo se R′′ = ∅.
A notação ⇒G, sendo G uma gramática, será usada a seguir para informar que a
derivação está sendo tomada com relação à gramática G.
Teorema 19 Seja uma GLC G tal que L(G) 6= ∅. Existe uma GLC, equivalente a G,
sem variáveis inúteis.
Prova
Sejam G, G′ e G′′ como delineados no método descrito.
Inicialmente, veja que L(G′) = L(G), pois apenas as regras de G cujas variáveis X
são tais que X
∗
⇒ w, para algum w ∈ Σ∗, podem contribuir para a geração de alguma
palavra de L(G); e G′ contém exatamente essas regras. Analogamente, L(G′′) = L(G′).
Resta então mostrar que G′′ não possui variáveis inúteis, ou seja, que todas as suas
variáveis são úteis. Para isso, seja uma variável arbitrária X ∈ V ′′. Em primeiro
lugar, tem-se que P
∗
⇒G′′ uXv, por construção de R
′′. E para qualquer uXv tal que
P
∗
⇒G′′ uXv, tem-se que uXv
∗
⇒G′′ w e w ∈ Σ
∗, pois todas as variáveis Y da forma
sentencial uXv são tais que Y
∗
⇒ y e y ∈ Σ∗; isso porque as variáveis de R′ têm essa
propriedade por construção, e ela é preservada na construção de R′′. Esse último fato
é mostrado a seguir. Ao ser eliminada uma variável Z de V ′, se Y
∗
⇒ uZv, então não
podem existir r e s tais que P
∗
⇒ rY s; caso contrário, ter-se-ia que P
∗
⇒ rY s
∗
⇒ ruZvs,
e Z não seria eliminada de V ′. Portanto, se Y
∗
⇒ uZv, Y é também eliminada. Caso
contrário, a eliminação de Z não altera o fato de que Y
∗
⇒ w para algum w ∈ Σ∗ .
Segue um exemplo de aplicação do método de eliminação de variáveis inúteis. Deve-
se notar que o Algoritmo 3.19a deve ser aplicado antes do Algoritmo 3.19b.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 165
Exemplo 90 Seja a gramática G = ({A,B,C,D,E, F}, {0, 1}, R,A}), em queR contém
as regras:
A→ ABC |AEF |BD
B → B0 | 0
C → 0C |EB
D → 1D | 1
E → BE
F → 1F1 | 1
Primeiro, determina-se SG = {B,D,F,A}. De acordo com o método descrito, R
′
consta das regras:
A→ BD
B → B0 | 0
D → 1D | 1
F → 1F1 | 1
Agora determina-se AG′ = {A,B,D}. Pelo método descrito, R
′′ contém apenas as
regras:
A→ BD
B → B0 | 0
D → 1D | 1
Durante a concepção de uma gramática, o projetista pode deparar com a necessidade
de modificar uma ou mais regras, sem alterar a linguagem gerada. Inicialmente, será
mostrado como eliminar uma regra X → w, em que X não é a variável de partida,
usando-se o expediente de “simular” a aplicação da mesma em todos os contextos
posśıveis: para cada ocorrência de X do lado direito de cada regra, prevê-se o caso em
que X é substitúıda por w e o caso em que não o é. Com esse expediente, consegue-se
produzir algumas derivações mais curtas, à custa do aumento do número de regras da
gramática.
Método 15 Eliminando uma regra
Sejam uma GLC G = (V,Σ, R, P ) e X → w ∈ R em que X 6= P . Uma GLC equivalente
sem a regra X → w seria G′ = (V,Σ, R′, P ) em que R′ é constitúıdo de:
1. cada regra Y → z ∈ R− {X → w} tal que X 6∈ vars(z); e
2. cada regra Y → x0γ1x1γ2x2 . . . γnxn, em que cada γj pode ser X ou w, para cada
Y → x0Xx1Xx2 . . . Xxn ∈ R com n > 0 ocorrências de X e X 6∈ vars(xi) para
0 ≤ i ≤ n. Exceção: no caso em que Y = X, apenas X → x0Xx1Xx2 . . . Xxn
não pertence a R′.
166 Editora Thomson Introdução aos fundamentos da computação
Y
B1 Bp X C1 Cq
A1 An
· · · · · ·
△
· · ·
△ △
· · ·
△
△
· · ·
△
(a) Antes
Y
B1 Bp A1 An C1 Cq
· · · · · ·
△
· · ·
△ △
· · ·
△ △
· · ·
△
(b) Depois
Figura 3.20 Transformação entre ADs induzida por remoção de regra.
Teorema 20 As GLCs G e G′, em que G′ é obtida como mostrado no Método 15, são
equivalentes.
Prova
Não será feita uma demonstração rigorosa desse teorema, mas uma argumentação relati-
vamente precisa e clara, utilizando o conceito de árvore de derivação (AD) desenvolvido
na Seção 3.4.2. Uma GLC G gera uma palavra w se, e somente se, existe uma AD de w.
Será mostrado, então, como transformar uma AD de w em G em uma AD de w em G′,
e vice-versa.Seja, então a regra X → w eliminada de G, com w = A1A2 . . . An, em que
Ai ∈ V ∪ Σ, e seja uma regra da forma Y → B1 . . . BpXC1 . . . Cq, com Bi, Cj ∈ V ∪ Σ
(note que cada Bi e Cj pode ser ou não X). Tendo em vista como G
′ é obtida, uma
AD de w em G pode ser transformada em uma AD de w em G′ substituindo-se toda
subárvore da forma exposta na Figura 3.20a pela subárvore exibida na Figura 3.20b.
Em palavras, para todo vértice vX de rótulo X, filho de vY , de rótulo Y , e cujos filhos
sejam (nesta ordem) vA1 , vA2 , . . . , vAn , com rótulos A1, A2, . . . , An,
1. eliminar o vértice vX ; e
2. colocar os vértices vA1 , vA2 , . . . , vAn (nesta ordem) como filhos de vY , entre os
vértices vBp e vC1 .
Essa transformação, assim como a inversa, é posśıvel, visto que X 6= P . Nela, a
subárvore à esquerda é substitúıda pela subárvore à direita (ou vice-versa).
O método delineado acima será exemplificado a seguir. Observe que, para se elimi-
nar uma regraX → w, cada regra com n ocorrências de X no seu lado direito dá origem
a até 2n regras: para cada ocorrência, considera-se o caso em que ela é substitúıda por
w (aplicação da regra X → w) e o caso em que não o é (prevendo os casos de aplicações
de outras regras X).
Exemplo 91 Seja a gramática G = ({P,A,B}, {a, b, c}, R, P ), em que R contém as
regras:
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 167
P → ABA
A→ aA | a
B → bBc |λ
que gera a linguagem {a}∗{bncn |n ≥ 0}{a}∗. Seja o problema de eliminar a regra
A→ a. A regra P → ABA dá origem a quatro regras:
P → ABA |ABa | aBA | aBa
e a regra A→ aA resulta em duas regras:
A→ aA | aa
Assim, a gramática resultante é G′ = ({P,A,B}, {a, b, c}, R′, P ), em que R′ contém as
regras:
P → ABA |ABa | aBA | aBa
A→ aA | aa
B → bBc |λ
Note que o número de regras aumentou, mas as derivações propiciadas são mais curtas.
Por exemplo, aa tem a seguinte derivação em G:
P ⇒ ABA (regra P → ABA)
⇒ aBA (regra A→ a)
⇒ aA (regra B → λ)
⇒ aa (regra A→ a).
E a mesma palavra tem a seguinte derivação em G′:
P ⇒ aBa (regra P → aBa)
⇒ aa (regra B → λ).
Uma GLC em uma certa forma normal admite poucos formatos de regras, porém
sem alterar o poder descritivo: para qualquer LLC existirá uma GLC equivalente na
formal normal considerada. Com isto, elas facilitam demonstrações relativas a proprie-
dades de LLCs, e, por propiciarem árvores de derivação com estrutura uniforme, podem
servir de base para construção de analisadores sintáticos.
Existem duas formas normais especialmente importantes para GLCs: as formas
normais de Chomsky e de Greibach. Como visto, as restrições feitas às regras de uma
gramática para torná-la uma gramática regular restringem a classe de linguagens que
podem ser descritas à das linguagens regulares. Uma maneira de se tentar chegar
a uma forma normal para GLCs é considerar: que modificações mı́nimas se poderia
fazer aos formatos de regras de gramáticas regulares de forma a conseguir o poder de
gerar qualquer LLC? Ora, uma ideia é simplesmente “generalizar” o formato de regra
X → aY de gramáticas regulares para permitir uma variável no lugar do terminal a.
168 Editora Thomson Introdução aos fundamentos da computação
Isto é suficiente para se ter o poder de gerar qualquer LLC, e é o que se faz na forma
normal de Chomsky. Por outro lado, uma caracteŕıstica interessante de gramáticas
regulares é que cada passo de derivação gera um novo terminal (a não ser no último
passo, que termina a derivação) e, em consequência, o número de passos para se derivar
uma palavra é limitado pelo tamanho da mesma. Isto segue novamente do formato de
regra X → aY . A forma normal de Greibach requer justamente que o lado direito das
regras comece com um terminal.
Uma caracteŕıstica importante das formas normais mencionadas é que suas de-
rivações são constitúıdas de formas sentenciais não decrescentes, isto é se x⇒ y, então
|x| ≤ |y|. Tal propriedade segue do fato de que elas não admitem regras λ. Por este
fato, também não há como gerar a palavra λ. Assim, daqui para frente, ao se gerar
uma GLC G′, em uma das duas formas normais, a partir de uma GLC G, ela será
tal que L(G′) = L(G) − {λ}. Evidentemente, se λ ∈ L(G), pode-se acrescentar uma
regra P → λ apenas para gerar a palavra λ. Neste caso, para evitar que tal regra
possa ser usada para outro propósito, basta introduzir um novo śımbolo de partida P ′
e acrescentar as regras P ′ → λ e P ′ → w para cada w tal que exista a regra P → w
em G′. Com isto, apenas a regra P ′ → λ não obedecerá ao formato, mas ela servirá
exclusivamente para gerar a palavra λ.
A seguir, será mostrado como obter, a partir de uma GLC G, uma GLC G′ sem
regras λ tal que L(G′) = L(G)− {λ}.
O Método 15 mostra como qualquer regra X → λ, em que X não seja o śımbolo de
partida, pode ser eliminada. Mas, ao se eliminar uma regra λ usando-se tal método,
pode-se criar outras regras λ. O método apresentado a seguir revela como eliminar
todas as regras λ de forma que L(G′) = L(G) − {λ}, usando uma técnica similar.
Primeiramente, introduz-se o conceito de variável anulável.
Definição 49 Uma variável X é dita ser anulável em uma GLC G se, e somente se,
X
∗
⇒G λ.
O conjunto das variáveis anuláveis pode ser obtido mediante a seguinte definição
recursiva.
Definição 50 O conjunto das variáveis anuláveis de uma GLC G = (V,Σ, R, P ), VAG,
é definido recursivamente assim:
• X ∈ VAG, se X → λ ∈ R;
• se X → w ∈ R e w ∈ VA∗G, então X ∈ VAG.
O algoritmo da Figura 3.21 determina proceduralmente o conjunto das variáveis
anuláveis de uma GLC.
Método 16 Eliminação de regras λ
Seja uma GLC G = (V,Σ, R, P ). Uma GLC G′ = (V,Σ, R′, P ) tal que L(G′) =
L(G)− {λ} é aquela em que R′ é constitúıdo de:
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 169
Entrada: uma GLC G = (V,Σ, R, P );
Sáıda: VAG = {X ∈ V |X
∗
⇒ λ}.
VAG ← ∅;
repita
N ← {X ∈ V − VAG |X → w ∈ R e w ∈ VA
∗
G};
VAG ← VAG ∪N
até N = ∅;
retorne VAG.
Figura 3.21 Algoritmo para determinar variáveis anuláveis.
1. cada regra Y → z ∈ R tal que z 6= λ e vars(z) ∩ VAG = ∅;
2. cada regra Y → x0γ1x1γ2x2 . . . γnxn, em que cada γj pode ser Xj ou λ, para
Y → x0X1x1X2x2 . . . Xnxn ∈ R, sendo n > 0, Xi ∈ VAG para 1 ≤ i ≤ n, e cada
xi sem variáveis anuláveis. Exceção: regra λ não pertence a R
′.
Note-se que se P ∈ VAG, então λ ∈ L(G); e, neste caso, seguirá do teorema a seguir
que L(G′) 6= L(G), e também que L(G) = L(G′) ∪ {λ}.
Teorema 21 Sejam G e G′ como no Método 16. Então L(G′) = L(G)− {λ}.
Prova
Analisando-se as duas etapas da definição de R′, vê-se que G′ não contém regra λ.
Assim, para provar o teorema, basta provar que P
∗
⇒G w se, e somente se, P
∗
⇒G′ w
para todo w ∈ Σ+. Mas isso segue do fato de que para todo X ∈ V , X
∗
⇒G w se, e
somente se, X
∗
⇒G′ w para todo w ∈ Σ
+, resultado este que será provado a seguir.
(→) Será mostrado inicialmente por indução sobre n, que para todo n ≥ 1, todo X ∈ V
e todo w ∈ Σ+, se X
n
⇒G w, então X
∗
⇒G′ w.
Sejam X ∈ V e w ∈ Σ+ arbitrários, e suponha que X
1
⇒G w. Tem-se, então, que
X → w ∈ R. Como w 6= λ, pela definição de R′ X → w ∈ R′ e, portanto, X
1
⇒G′ w.
Seja n ≥ 1 arbitrário, e suponha, como hipótese de indução, que se X
n
⇒G w, então
X
∗
⇒G′ w para todo X ∈ V e todo w ∈ Σ
+. Suponha agora que X
n+1
⇒ G w para X ∈ V
e w ∈ Σ+ arbitrários. Nesse caso,
X
1
⇒G Y1Y2 . . . Yk
n
⇒G w = x1x2 . . . xk,
sendo que Yi
pi⇒G xi, para cada 1 ≤ i ≤ k, sendo
∑k
i=1 pi = n. Para cada xi: se xi = λ
e Yi é uma variável, então Yi é uma variável anulável; e se xi 6= λ, então, pela hipótese
de indução, tem-se que Yi
∗
⇒G′ xi. E como G tem a regra X → Y1Y2 . . . Yk, G
′ tem a
regra X → Z1Z2 . . . Zk, sendo Zi = Yi se xi 6= λ, e Zi = λ se xi = λ. Assim sendo,
tem-se, finalmente, que:
X
1
⇒G′ Z1Z2 . . . Zk
∗
⇒G′ x1Z2 . . . Zk
∗
⇒G′ x1x2 . . . Zk
∗
⇒G′ . . .
∗
⇒G′ x1x2 . . . xk.
170Editora Thomson Introdução aos fundamentos da computação
(←) Será mostrado, também por indução sobre n, que para todo n ≥ 1, para todo
X ∈ V e todo w ∈ Σ+, se X
n
⇒G′ w, então X
∗
⇒G w.
Sejam X ∈ V e w ∈ Σ+ arbitrários, e suponha que X
1
⇒G′ w. Tem-se, então, que
X → w ∈ R′. Como w 6= λ, pela definição de R′ existe y tal que |y| > 0 e X → y ∈ R′
e w é o resultado de substituir zero ou mais ocorrências de variáveis anuláveis de y por
λ. Assim sendo, tem-se que X
1
⇒G y
∗
⇒G w. Seja n ≥ 1 arbitrário, e suponha, como
hipótese de indução, que se X
n
⇒G′ w, então X
∗
⇒G w para todo X ∈ V e todo w ∈ Σ
+.
Suponha agora que X
n+1
⇒ G′ w para X ∈ V e w ∈ Σ
+ arbitrários. Nesse caso,
X
1
⇒G′ Z1Z2 . . . Zk
n
⇒G′ w = x1x2 . . . xk,
sendo que Zi
pi⇒G xi, para cada 1 ≤ i ≤ k, sendo
∑k
i=1 pi = n. Como X →
Z1Z2 . . . Zk ∈ R
′, segue que há em R uma regra X → y sendo que Z1Z2 . . . Zk é
obtida de y pela eliminação de zero ou mais variáveis anuláveis. Portanto, X
∗
⇒G
Z1Z2 . . . Zk. Se Zi é uma variável, pela hipótese de indução tem-se que Zi
∗
⇒G xi.
Logo, Z1Z2 . . . Zk
∗
⇒G x1x2 . . . xk. Concluindo:
X
∗
⇒G Z1Z2 . . . Zk
∗
⇒G w = x1x2 . . . xk.
Segue um exemplo de aplicação do método de eliminação de regras λ.
Exemplo 92 Seja a gramática G = ({P,A,B,C}, {a, b, c}, R, P ), em que R contém
as regras:
P → APB |C
A→ AaaA |λ
B → BBb |C
C → cC |λ
O conjunto de variáveis anuláveis de G, no presente caso, é o conjunto de todas as suas
variáveis. Obtém-se, então, as seguintes regras aplicando-se o Método 16:
P → APB |AP |AB |PB |A |B |C
A→ AaaA | aaA |Aaa | aa
B → BBb |Bb | b |C
C → cC | c
A regra P → P , obtida a partir de P → APB, foi descartada por motivos óbvios. E
como P ∈ VAG, segue-se que L(G) = L(G
′)∪ {λ}. Uma GLC equivalente a G, em que
a única regra λ serve apenas para gerar a palavra λ, teria P ′ como variável de partida
e, além dessas últimas regras, as seguintes:
P ′ → APB |AP |AB |PB |A |B |C |λ
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 171
Entrada: uma GLC G = (V,Σ, R, P ) e uma variável X ∈ V .
Sáıda: enc(X).
E ← {X};
repita
N ← {Z ∈ V −E |Y → Z ∈ R para algum Y ∈ E};
E ← E ∪N
até N = ∅
retorne E.
Figura 3.22 Algoritmo para variáveis encadeadas.
Note-se que P ′ → λ só serve para gerar a palavra λ.
Nenhuma das duas formas normais mencionadas anteriormente admite regras da
forma X → Y , em que X e Y são variáveis. Tais regras são denominadas regras
unitárias. O método para se obter uma GLC sem regras unitárias equivalente a uma
GLC dada faz uso do conceito de variáveis encadeadas. Seja uma gramática G =
(V,Σ, R, P ). Diz-se que uma variável Z ∈ V é encadeada a uma variável X ∈ V se
Z = X ou se existe uma sequência de regras X → Y1, Y1 → Y2, . . . , Yn → Z em R,
n ≥ 0; no caso em que n = 0, tem-se apenas a regra X → Z. Ao conjunto de todas as
variáveis encadeadas a X é dado o nome de enc(X). Segue uma definição recursiva.
Definição 51 O conjunto das variáveis encadeadas a X ∈ V de uma GLC G =
(V,Σ, R, P ), enc(X), é definido recursivamente assim:
• X ∈ enc(X);
• se Y → Z ∈ R e Y ∈ enc(X), então Z ∈ enc(X).
O algoritmo da Figura 3.22 mostra uma forma de construir tal conjunto procedural-
mente. O método a seguir mostra como usar os conjuntos enc para eliminar as regras
unitárias.
Método 17 Eliminação de regras unitárias
Uma GLC equivalente a G = (V,Σ, R, P ), sem regras unitárias, é G′ = (V,Σ, R′, P ) em
que
R′ = {X → w |w 6∈ V e existe Y ∈ enc(X) tal que Y → w ∈ R}.
Teorema 22 Seja uma GLC G. A GLC G′ sem regras unitárias, como definida no
Método 17, é equivalente a G.
Prova
Para provar a equivalência entre G e G′, será mostrado que para todo X ∈ V e todo
w ∈ Σ∗ X
∗
⇒G w se, e somente se, X
∗
⇒G′ w.
(→) Será mostrado, por indução sobre n, que para todo n ≥ 0, para todo X ∈ V e
todo w ∈ Σ∗ se X
n
⇒G w, então X
∗
⇒G′ w.
172 Editora Thomson Introdução aos fundamentos da computação
Para n = 0, sendo X ∈ V , não existe w ∈ Σ∗ tal que X
0
⇒G w; logo, a afirmativa
vale por vacuidade. Seja n ≥ 0 arbitrário, e suponha, como hipótese de indução, que
para todo X ∈ V e todo w ∈ Σ∗ se X
n
⇒G w, então X
∗
⇒G′ w. Sejam X ∈ V e w ∈ Σ
∗
arbitrários e suponha que X
n+1
⇒G w. Nesse caso,
X ⇒G Y1 ⇒G Y2 . . .⇒G Yk
n+1−k
⇒G w,
sendo que Y1, Y2, . . . , Yk−1 ∈ V e Yk 6∈ V , k ≥ 1. Pela definição de G
′, X → Yk ∈ R
′.
Logo, X ⇒G′ Yk. Supondo que YK = Z1Z2 . . . Zm, Zi ∈ V ∪ Σ, e que w = u1u2 . . . um,
sendo que Zi
pi⇒G ui, como pi ≤ n, pela hipótese de indução, se Zi ∈ V , então Zi
∗
⇒G′ ui
e, portanto,
X ⇒G′ Z1Z2 . . . Zm
∗
⇒G′ u1Z2 . . . Zm
∗
⇒G′ u1u2 . . . Zm
∗
⇒G′ u1u2 . . . um = w.
(←) Segue da definição das regras de G′ que se X
∗
⇒G′ w então X
∗
⇒G w.
Segue um exemplo de eliminação de regras unitárias.
Exemplo 93 Seja novamente a GLC para expressões aritméticas cujas regras são re-
produzidas a seguir:
E → E+T |T
T → T∗F |F
F → (E) | a
Os conjuntos enc(X) para cada variável X são:
• enc(E) = {E,T, F};
• enc(T ) = {T, F};
• enc(F ) = {F}.
A GLC equivalente, sem regras unitárias, obtida de acordo com o Método 17, é então
({E,T, F}, {a,+, ∗, (, )}, R′, E), em que R′ tem as regras:
E → E+T |T∗F | (E) | a
T → T∗F | (E) | a
F → (E) | a
As formas normais de Chomsky e de Greibach a serem abordadas a seguir requerem
que a GLC não contenham variáveis inúteis, regras λ, nem regras unitárias. Note-se
que:
a) Ao se eliminar regras λ podem aparecer regras unitárias. Exemplo: GLC com as
regras A→ BC e B → λ.
Newton José Vieira Caṕıtulo 2: Máquinas de estados finitos 173
b) Ao se eliminar regras unitárias não podem aparecer regras λ, visto que novas
regras só contêm o lado direito de regras já existentes (que não podem ser λ).
c) Ao se eliminar regras λ podem aparecer variáveis inúteis. Exemplo: o do item
(a), caso B → λ seja a única regra B.
d) Ao se eliminar regras unitárias podem aparecer variáveis inúteis. Exemplo: GLC
que contém A→ B e B não aparece do lado direito de nenhuma outra regra (B
torna-se inútil).
e) Ao se eliminar variáveis inúteis, não podem aparecer novas regras, inclusive regras
λ ou unitárias.
Com isto, conclui-se que a seguinte ordem garante a obtenção de uma GLC equivalente
a uma dada (a menos da palavra λ) sem variáveis inúteis, regras λ, nem regras unitárias:
1. eliminar regras λ;
2. eliminar regras unitárias;
3. eliminar śımbolos inúteis.
Novamente, deve-se notar que a palavra λ pode ser gerada através do artif́ıcio já mos-
trado.
A discussão anterior permite enunciar o teorema a seguir.
Teorema 23 Para qualquer GLC G = (V,Σ, R, P ), existe uma GLC que gera L(G)−
{λ} cujas regras são das formas:
• X → a em que a é terminal; e
• X → w para |w| ≥ 2.
Prova
Esse resultado segue da discussão apresentada anteriormente.
A seguir, a definição de forma normal de Chomsky.
Definição 52 Uma GLC G = (V,Σ, R, P ) é dita estar na forma normal de Chomsky
(FNC ) se não contém variáveis inúteis e cada uma de suas regras está em uma das
formas:
• X → Y Z para Y,Z ∈ V;
• X → a para a ∈ Σ.
Segue um método para obtenção de GLC na FNC.
Método 18 Obtenção de FNC
Para obter uma GLC na FNC que gere L(G) − {λ} a partir de uma GLC G, basta
seguir os passos:
174 Editora Thomson Introdução aos fundamentos da computação
1. Eliminar regras λ.
2. Eliminar regras unitárias.
3. Eliminar variáveis inúteis.
4. Modificar cada regra X → w tal que |w| ≥ 2, se necessário, de forma que ela fique
contendo apenas variáveis. Para isso, substituir cada ocorrência de cada a ∈ Σ
que apareça em w por uma variável, da seguinte forma: se existe uma regra da
forma Y → a e esta é a única regra Y , substituir as ocorrências de a por Y em
w; caso contrário, criar uma regra Y → a, em que Y é uma variável nova, e
substituir as ocorrências de a por Y em w.
5. Substituir cada regra X → Y1Y2 . . . Yn, n ≥ 3, em que cada Yi é