Linguagens livres de contexto

Prévia do material em texto

Linguagens livres de contexto
Conceitos fundamentais das linguagens formais e autômatos, gramáticas e propriedades das linguagens
livres de contexto e os autômatos de pilha.
Prof. Tomás de Aquino Tinoco Botelho
1. Itens iniciais
Propósito
Apresentar os conceitos fundamentais das gramáticas livres de contexto e descrever os autômatos de pilha e
sua importância na construção de compiladores e interpretadores de linguagens de programação, uma vez
que são a base para a definição da parte sintática das linguagens de programação.
Objetivos
Identificar noções e terminologias das gramáticas livres de contexto.
Aplicar a simplificação das gramáticas livres de contexto.
Descrever os autômatos de pilha e seu funcionamento.
Identificar as propriedades das linguagens livres de contexto.
Introdução
Veremos os conceitos e a prática sobre gramáticas livres de contexto, bem como os autômatos de pilha, que
são máquinas de estado finito reconhecedoras das linguagens geradas pelas gramáticas livres de contexto. 
As linguagens livres de contexto são amplamente utilizadas na parte de análise sintática em linguagem de
programação, como C, Java e C#. 
O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por um
autômato de pilha, o que faz com que essas linguagens sejam passíveis de análise. 
As gramáticas livres de contexto permitiram o desenvolvimento de notações bastante adequadas para a
formalização da sintaxe das linguagens formais, o que ensejou o desenvolvimento de técnicas muito eficientes
de construção de reconhecedores sintáticos e na formalização das linguagens de programação. 
• 
• 
• 
• 
1. Gramáticas livres de contexto
Conceitos básicos
Símbolo, alfabeto e cadeia
Antes de tudo, é preciso conhecer as seguintes definições:
Símbolo
Símbolo é uma entidade definida como um
ponto em geometria. É uma abstração. Como
exemplo citamos os símbolos matemáticos de
igualdade (=), produto (*) e divisão (/), bem
como os lógicos comparativos de maior (>) e
menor (babb, bbaa, bbbb.....}. 
Hierarquia de Chomsky
Tipos de Gramáticas
A Hierarquia de Chomsky é a classificação de gramáticas formais em quatro níveis de acordo com as
definições a seguir.
Hierarquia de Chomsky.
Veja a seguir as definições dos tipos acima apontados.
Gramática tipo 0
Como uma gramática de estrutura de frase sem qualquer restrição, podemos dizer que todas as gramáticas
são gramáticas tipo 0. As gramáticas irrestritas como as do tipo 0 são especificadas pelo seguinte formalismo
matemático:
Em outras palavras, as regras de produção contêm do LE símbolos não terminais antecedidos e sucedidos por
símbolos terminais e não terminais, incluindo a palavra vazia. É importante notar que o LE nunca conterá a
palavra vazia, uma vez que o “V” no centro da cadeia não está com o “*”, garantindo que do LE existe, pelo
menos um símbolo não terminal.
Do LD é possível qualquer combinação de símbolos do conjunto {V U T}+, inclusive a palavra vazia (λ). 
Gramática tipo 1
A gramática tipo 1 é chamada de gramática sensível ao contexto (GSC). Para ela, todas as produções são
sensíveis ao contexto se todas as regras em P estiverem no formato:
As regras de produção do LE contêm símbolos não terminais antecedidos e sucedidos por símbolos terminais
e não terminais, incluindo a palavra vazia. É importante notar que o LE nunca conterá a palavra vazia, uma vez
que o “V” no centro da cadeia não está com o “*”, garantindo que do LE existe, pelo menos um símbolo não
terminal.
Do LD é possível qualquer combinação de símbolos do conjunto {V U T}+. Como sabemos, neste caso, do LD
não está incluída a palavra vazia (λ). 
Gramática tipo 2
A gramática tipo 2 é chamada de gramática livre de contexto (GLC), pois suas regras de produção podem ser
aplicadas independentemente do contexto do símbolo não terminal. 
Não importa quais símbolos existem na GLC, um único símbolo não terminal existente no lado esquerdo de
uma regra pode sempre ser substituído pelo lado direito. E isso a distingue da gramática sensível ao contexto
(GSC). Para essa gramática, todas as produções são livres de contexto se todas as regras em P estiverem no
formato: 
O lado esquerdo da produção contém exatamente uma variável, e no lado direito é possível qualquer
combinação de símbolos do conjunto {V U T}*.
As GLCs são importantes para definir linguagens de programação. Por exemplo, as linguagens que requerem o
balanceamento de parênteses são geradas pela gramática:
A maioria das expressões aritméticas em linguagens de programação é gerada por gramáticas livres de
contexto.
Em ciência da computação, como o uso de conceitos recursivamente definidos aumentou, as GLC foram
usadas mais e mais. As primeiras aplicações das gramáticas eram principalmente para descrever a estrutura
de linguagens de programação. Uma aplicação mais recente foi a utilização de GLC em uma parte essencial da
Extensible Markup Language (XML). 
Gramática tipo 3
A gramática tipo 3 é chamada de gramática regular e gera as chamadas linguagens regulares. Para essa
gramática, todas as produções em P devem ser no formato:
No lado direito da produção há, no máximo, um não terminal sempre acompanhado de um símbolo terminal. 
Atenção
Concluindo, a partir da representação da figura e, usando os conceitos de teoria dos conjuntos,
podemos dizer que toda gramática regular é uma gramática livre de contexto, toda gramática livre de
contexto é uma gramática sensível ao contexto, e toda gramática sensível ao contexto é uma gramática
irrestrita. 
Gramáticas livres de contexto 
Introdução
A linguagem gerada pela gramática livre de contexto (GLC) é chamada de linguagem livre de contexto (LLC).
Na descrição matemática, podemos descrevê-la como a produção: 
Onde, α pertence ao conjunto de não terminais e |α|= 1, ou seja, haverá apenas um não terminal do lado
esquerdo (LE) e β ϵ V U T, que quer dizer que β é uma combinação de não terminais e terminais.
Contexto
Os símbolos não terminais são os símbolos produtores porque geram alguns símbolos extras. Assim, as regras
de produção estão no formato seguinte:
A cadeia do LE tem um símbolo não terminal e a do LD contém uma combinação de terminais e não terminais.
Se algum símbolo estiver presente com o não terminal produtor no LE da regra de produção, então esse
símbolo extra é chamado de contexto. O contexto pode ser de dois tipos: (a) contexto esquerdo e (b) contexto
direito.
Em uma GLC, no LE de cada regra de produção, há apenas um não terminal (nenhum contexto é adicionado
com ele); por esse motivo, esse tipo de gramática é chamado de GLC. 
BNF
A forma normal de Backus Naur (BNF) é uma notação formal para descrever a sintaxe de uma linguagem,
tendo sido utilizada para a descrição da linguagem de programação ALGOL 60. 
A BNF é amplamente usada como notação para as gramáticas de linguagens de programação, conjuntos de
instruções e protocolos de comunicação, e como notação para representar partes de gramáticas de
linguagens naturais. 
Os símbolos utilizados na BNF são:
 
::= ➜ denota “é definido como” 
I ➜ denota “ou”
 ➜ usado para denotar categorias
Uma especificação BNF é um conjunto de regras de derivação, escritas como:
Onde é um não terminal e consiste em sequências de símbolos e/ou sequências separadas pela barra vertical,
'|', indicando uma escolha. Esta notação indica as possibilidades de substituição para símbolo do lado
esquerdo. Símbolos que nunca aparecem no lado esquerdo são ditos terminais. 
Veja o exemplo a seguir onde vemos uma BNF possível para um endereço postal do Brasil: 
{A cadeia contém, exatamente, um símbolo não terminal}→{Uma cadeia de terminais e/ou
não terminais}
• 
• 
• 
Exemplo
\ltendereço-postal>; ::= \lt parte-do-nome>;\lt endereço-da-rua>;\lt parte-do-CEP>;\ltparte-do-nome>;
::= \ltparte-pessoal>;\ltúltimo-nome>; \ltparte-opc-jr>;\lt FDL>; |\ltparte-pessoal>; \ltparte-
do-nome>; \ltparte-pessoal>; ::= \ltinicial>; "."|\ltprimeiro-nome>;\ltendereço-da-rua>; ::= \ltnome-da-
rua>;\ltnúmero-do-imóvel>; \ltnum-apto-opc>; \ltFDL>;\ltparte-do-CEP>; ::= \ltCEP>;\ltnome-da-
cidade>;"-" \ltcódigo-do-estado>; \ltFDL>; 
Isso se traduz para o português como: um endereço postal consiste na parte-do-nome, seguida pela parte do
endereço-da-rua, seguida pela parte do CEP, sendo cada parte decomposta. 
Vejamos um exemplo prático para a computação: 
Exemplo
::=|::=0|1|2|3|4|5|6|7|8|9 
Isso pode ser descrito como: um número é um dígito ou um número seguido por um dígito e um dígito é
qualquer um dos caracteres de 0 a 9.
Da BNF vem a BNF estendida que usa algumas notações de expressão regular como + ou *.
Como exemplo, o identificador de uma linguagem de programação é denotado como: 
Exemplo
::=letra(letra|dígito)*::=a|b|c|....|z|A|B|C|....|Z::=0|1|2|3|4|5|6|7|8|9 
Exemplos práticos
Exemplo 1
Vamos construir uma GLC para a linguagem .
Solução: W é uma cadeia composta de qualquer combinação de a e b. Então, WR também é uma cadeia
composta de qualquer combinação de a e b, mas é uma cadeia que é inversa de W. “C” é um símbolo terminal
como a, b. Portanto, se tomarmos “C” como um espelho, poderemos ver o reflexo de W na parte composta
WR, por exemplo, C, abCba, abbaCabba e assim por diante. 
Como W ϵ (a, b)*, os símbolos nulos também são aceitos no lugar de a, b. Isso significa que apenas C é aceito
por esse conjunto de linguagens.
A partir da discussão acima, as regras de produção são:
 
S→aSa/bSb/C
A GLC para essa linguagem é G = (V,T,P,S), onde:
 
V = {S}
T = {a, b, c}
P = S→aSa/bSb/C
S = {S}
Exemplo 2
Vamos construir uma GLC para a expressão (0 + 1)* 0 1*.
Solução: A expressão regular em português pode ser escrita como:
Qualquer combinação de 0s e 1s seguida por um único 0 e terminando com qualquer número de 1s.
Nesta expressão regular, um único 0 está entre (0 + 1)* e 1*, ou seja, nesta linguagem, apenas 0 pode existir
entre ambas a expressões com ‘*’. Para construir agramática para esta expressão, mantenha esse único ‘0’
fixo. Então, antes e depois deste 0, considere dois não terminais A e B que podem ser substituídos várias
vezes.
Assim, as regras de produção (P) da gramática para construir esta expressão regular são:
 
S→ASB|0
A→0A|1A|λ
B→1B|λ
A GLC para essa linguagem é G = (V,T,P,S), onde:
 
V = {S,A,B}
T = {0, 1}
P = S→ASB|0
A→0A|1A|λ
B→1B|λ
S = {S}
Exemplo 3
Vamos construir uma GLC para uma cadeia na qual há um número igual de números binários.
Solução: Números binários significam 0 e 1. Qualquer cadeia que pertença à linguagem consiste em um
número igual de 0 e 1. Esses números podem vir em qualquer ordem, mas na cadeia os números de 0 e 1 são
iguais.
A cadeia pode começar com 0 ou pode começar com 1. 0 pode vir depois de 0 ou 1 pode vir depois de 0. 1
pode vir depois de 1 ou 0 pode vir depois de 1.
As regras de produção (P) para essa gramática são:
 
S→0S1|1S0|λ
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
A GLC para essa linguagem é G = (V,T,P,S), onde:
 
V = {S}
T = {0, 1}
P = S→0S1|1S0|λ
S = {S}
Gramáticas livres de contexto
Assista agora a um vídeo no qual são apresentados os principais conceitos de gramáticas livres de contexto e
sua aplicação no tema em exemplos práticos de computação. 
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Tipos de gramáticas
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Exemplo 1 - Construção de uma GLC
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
A seguinte expressão define uma gramática livre de contexto P = {A→β | A ϵ V Λ β ϵ (V U T)*}. Avalie as
afirmativas a seguir:
I. O lado esquerdo da produção contém exatamente uma variável.
II. No lado direito é possível qualquer combinação de símbolos do conjunto {V U T}*.
III. É uma gramática tipo 3, sendo importante para definir linguagens de programação.
Quais as afirmativas estão corretamente relacionadas com uma gramática livre de contexto?
A
• 
• 
• 
• 
II e III
B
I e III
C
I e II
D
I, II e III
E
II
A alternativa C está correta.
A afirmativa 3 está incorreta, pois a gramática livre de contexto é uma gramática tipo 2, sendo importante
para definir linguagens de programação.
Questão 2
Considere o seguinte subconjunto da gramática da linguagem C, expresso em BNF:
As regras para identificadores de variáveis em linguagem C são:
 
1. Um identificador é uma sequência de letras, dígitos e sublinhados.
2. Um identificador deve começar com uma letra ou sublinhado.
3. Os identificadores permitem letras maiúsculas e minúsculas.
 
Onde “|” representa “ou” e λ representa a cadeia vazia.
 
 ::= |
 ::= |||λ
 ::= a|b|...|z|A|B|...|Z
 ::= 0|1|...|9
 ::= _
 
Assinale a alternativa que representa corretamente a produção descrita no texto:
A
, e ϵ T
B
{a|b|...|z|A|B|...|Z} ϵ T*
C
 → é uma regra de produção válida
D
{0|1|...|9} ϵ(V U T)*
E
 ::= λ
A alternativa C está correta.
Esta produção está conforme descrita no texto. A alternativa 'a' está errada porque apresenta símbolos não
terminais apenas, e o lado direito é o conjunto T dos terminais. As alternativas 'b' e 'd' estão erradas porque
os conjuntos não contemplam a cadeia vazia e a alternativa 'e' está nitidamente incorreta.
2. Simplificação de gramáticas livres de contexto
Remoção de símbolos não geradores 
Algoritmo para remoção
GLCs podem conter diferentes tipos de símbolos inúteis, produções unitárias e produções nulas. Esses tipos
de símbolos e produções aumentam o número de etapas na geração de uma linguagem a partir de uma GLC. 
A gramática reduzida, ou simplificada, contém menor número de não-terminais e produções, de modo que a
complexidade de tempo para o processo de geração da linguagem torna-se menor, não afetando a linguagem
definida pela gramática original. Uma GLC pode ser simplificada usando os três passos a seguir. 
Remoção de símbolos inúteis:
Remoção de símbolos não geradores
Símbolos não geradores são aqueles símbolos
que não produzem nenhuma cadeia terminal.
Remoção de símbolos inacessíveis ou
não alcançáveis
Símbolos não alcançáveis são aqueles que não
podem ser alcançados a qualquer momento a
partir do símbolo inicial.
Remoção de produções unitárias;
Remoção de produções nulas.
Toda linguagem livre de contexto pode ser gerada por uma gramática livre de contexto em que não há
símbolos inacessíveis ou inúteis. 
Esses dois tipos de símbolos inúteis podem ser removidos de acordo com o seguinte algoritmo: 
1
Encontre os símbolos não geradores
Ou seja, os símbolos que não geram nenhuma cadeia terminal. Se o símbolo inicial encontrado for
não gerador, deixe esse símbolo. O símbolo inicial não pode ser removido porque o processo de
geração da linguagem começa a partir desse símbolo.
2
Remova os símbolos não geradores
Para isso, remova as produções cujo lado direito e esquerdo contenham esses símbolos.
3
Encontre os símbolos não alcançáveis
Ou seja, os símbolos que não podem ser alcançados, começando pelo símbolo inicial. Remova os
símbolos não alcançáveis, como a regra (b).
Exemplo 1
Vamos remover os símbolos inúteis da seguinte GLC (KANDAR, 2013):
• 
• 
• 
 
S → AC
S → BA
C → CB
C → AC
A → a
B → aC/b
Solução: Existem dois tipos de símbolos inúteis: símbolos não geradores e não alcançáveis. Primeiro, vamos
encontrar os símbolos não geradores.
Aqueles símbolos que não produzem nenhuma cadeia apenas com símbolos terminais são símbolos não
geradores. Aqui, C é um símbolo não gerador, pois não produz nenhuma cadeia apenas com símbolos
terminais.
Então, temos que remover o símbolo C. Para remover C, todas as produções que contenham C como símbolo
(LE ou LD) devem ser removidas. Ao remover as produções, a gramática minimizada será:
 
S → BA
A → a
B → b
 
Agora, temos que encontrar símbolos não alcançáveis, ou seja, os símbolos que não podem ser alcançados a
qualquer momento a partir do símbolo inicial. Não há símbolo não alcançável na gramática minimizada. Assim,
a forma minimizada da gramática removendo símbolos inúteis é a mesma acima. 
Exemplo 2
Vejamos mais um exemplo prático (Kandar, 2013). Vamos remover os símbolos inúteis da seguinte GLC:
 
S → aB/bX
A → BAd/bSX/a
B → aSB/bBX
X → SBD/aBx/ad
Solução: Primeiro, vamos encontrar símbolos não geradores, os não terminais que não produzem nenhuma
cadeia com símbolos terminais.
Aqui, B não está produzindo nenhuma cadeia apenas com símbolos terminais, então este é um símbolo não
gerador. Para remover B das regras de produção da gramática dada, todas as produções que contenham B
como símbolo serão removidas. Ao remover B da gramática, as regras de produção modificadas serão:
 
S → bX
A → bSX/a
X → ad
Agora temos que encontrar símbolos não alcançáveis, ou seja, os símbolos que não podem ser alcançados a
partir do símbolo inicial.
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Aqui, o símbolo A não pode ser alcançado por nenhum caminho em nenhum momento a partir do símbolo
inicial S. Portanto, A é um símbolo inalcançável. Para remover A, todas as produções que contenham A como
símbolo serão removidas. Ao remover A das regras de produção da gramática, a gramática minimizada será:
 
S → bX
X → ad
Remoção de produções unitárias
Produções unitárias
Produções unitárias são produções da forma A→B, em que A e B são não terminais, e costumam ser
descartadas das GLC porque nada acrescentam às formas sentenciais às quais são aplicadas, constituindo
mera renomeação de símbolos (no caso, de A para B).
Em outras palavras, é chamada de produção unitária a produção cuja forma corresponde a: 
Toda linguagem livre de contextopode ser gerada por outra gramática livre de contexto isenta de produções
unitárias. 
A produção unitária aumenta o número de passos e a complexidade na hora de gerar a linguagem a partir da
gramática. Isso ficará claro se tomarmos um exemplo (KANDAR, 2013).
Seja a seguinte gramática: 
A partir daqui, se vamos gerar uma cadeia, ela pode ser gerada da seguinte maneira:
O número de passos é 6. A gramática, removendo a produção unitária e minimizando, será:
Assim, a cadeia será gerada da seguinte forma: 
• 
• 
não terminal → único não terminal
S→AB, A→E, B→C, C→D, D→b, E→a
S → AB → EB → aB →aC → aD → ab
S→AB, A→a, B→b
S→AB→aB→ab
O número de passos agora é 3.
Algoritmo para remoção
A remoção de produções unitárias de uma GLC pode ser realizada a partir do seguinte algoritmo:
Exemplo 1
Seja a seguinte GLC, vamos remover a produção unitária (KANDAR, 2013).
Solução: Nesta gramática, as produções unitárias são A→E, B→C e C→D. Se quisermos remover a produção
unitária A→E da gramática, primeiro temos que encontrar uma produção não unitária na forma E→{alguma
cadeia de terminal ou não terminal ou ambos}. 
Existe uma produção E→a. Assim, a produção A→a será adicionada à regra de produção. A gramática
modificada será:
Para remover a produção unitária B→C, temos que encontrar uma produção não unitária C→{alguma cadeia de
terminal ou não terminal ou ambos}. Mas não há tal produção na gramática. Assim, no momento, nada pode
ser reduzido.
Para remover a produção unitária C→D, encontramos uma produção não unitária D→b. Assim, a produção
C→b será adicionada ao conjunto de regras de produção, e C→D será removida. A gramática modificada será: 
Agora, a produção unitária B→C poderá ser removida por B→b, pois há uma produção não unitária C→b. A
gramática modificada será:
Esta é a gramática sem produções unitárias, mas não está minimizada. Existem símbolos inúteis (símbolos não
alcançáveis) C, D e E. Então, se quisermos minimizar a gramática, esses símbolos devem ser removidos. Ao
remover os símbolos inúteis, a gramática será:
Enquanto (existir produção unitária na forma A→B) { Selecione a produção unitária
A→B Para (toda produção não unitária B→α) { Adicione a produção
A→α à gramática. Elimine a regra A→B dessa gramática. } }
S→AB, A→E, B→C, C→D, D→b, E→a
S→AB, A→a, B→C, C→D, D→b, E→a
S→AB, A→a, B→b, C→b, D→b, E→a
S→AB, A→a, B→b, C→b, D→b, E→a
Exemplo 2
Remova a produção unitária da gramática a seguir (KANDAR, 2013).
Solução: As produções unitárias na gramática são: B→C, C→D
Para remover a produção unitária B→C, temos que procurar uma produção não unitária da forma C→{alguma
cadeia de terminal ou não terminal ou ambos}. Não há tal regra de produção, então, tentamos remover a
produção unitária C→D.
Existe uma produção não unitária D→b. Assim, a produção unitária C→D será removida incluindo uma
produção C→b.
As regras de produção modificadas serão: 
Existe uma produção unitária B→C. Essa produção unitária pode ser removida incluindo uma produção B→b na
gramática.
As regras de produção modificadas serão: 
Esta gramática é livre de produções unitárias, mas não está minimizada. Existem símbolos inúteis na forma de
símbolos não alcançáveis. Aqui, os símbolos não alcançáveis são C e D, que não podem ser alcançados a
partir do símbolo inicial S. Ao remover os símbolos inúteis, a gramática se tornará:
Remoção de produções nulas
Produção nula
Uma produção na forma NT→λ é chamada de produção nula. Se λ (cadeia nula) estiver no conjunto de idiomas
gerado a partir da gramática, essa produção nula não poderá ser removida. Se obtivermos S→λ, então essa
produção nula não pode ser removida das regras de produção. 
S→AB, A→a, B→b
S→AB, A→a, B→C, C→D, D→b
S→AB, A→a, B→C, C→b, D→b
S→AB, A→a, B→b, C→b, D→b
S→AB, A→a, B→b
Atenção
Toda linguagem livre de contexto que não contém a cadeia nula pode ser gerada por uma gramática livre
de contexto em que não há produções que levem à cadeia nula. 
Algoritmo para remoção
O algoritmo a seguir mostra como transformar uma gramática G em outra equivalente G′, isenta de produções
nulas.
Passo I
Se A→λ é uma produção a ser eliminada, então
procuramos todas as produções cujo lado
direito contém A.
Passo II
Substitua cada ocorrência de A em cada uma
dessas produções para obter a produção não λ.
Passo III
Essas produções não nulas devem ser
adicionadas à gramática para manter a potência
de geração da linguagem.
Exemplo 1
Remova a produção λ da gramática a seguir (KANDAR, 2013).
Solução: Nas regras de produção anteriores, há uma produção nula A→λ. A gramática não produz a cadeia
nula como linguagem e, portanto, essa produção nula pode ser removida.
De acordo com o primeiro passo, temos que procurar todas as produções cujo lado direito contém A. Existe
um S→aA.
De acordo com o segundo passo, temos que substituir cada ocorrência de ‘A’ em cada uma das produções. Há
apenas uma ocorrência de ‘A’ em S→aA. Então, após a substituição, ele se tornará S→a.
De acordo com o passo três, essas produções serão adicionadas à gramática.
Assim, nova gramática será: 
S→aA A→b/λ
S→aA|a A→b
Note que não há mais regras de produção que levem à cadeia nula λ.
Vejamos mais um exemplo interessante sobre a remoção de produções nulas. 
Exemplo 2
Remova a produção λ da gramática a seguir.
Solução: Na gramática acima, existe uma produção nula X→λ. No conjunto da linguagem produzida pela
gramática, não há cadeia nula e, portanto, essa produção nula pode ser removida.
Para remover essa produção nula, temos que procurar todas as produções cujo lado direito contém X. Existem
duas dessas produções na gramática S→aX e S→bX.
Temos que substituir cada ocorrência de ‘X’ em cada uma das produções para obter uma produção não nula.
Em ambas as produções, X ocorreu apenas uma vez. Assim, após a substituição, as produções passarão a ser
S→a e S→b, respectivamente.
Essas produções devem ser adicionadas à gramática para manter a potência geradora da linguagem. Então,
depois de somar essas produções, a gramática será:
Vamos apresentar um exemplo interessante em que não é possível remover produções nulas.
Simplificação de gramáticas livres de contexto
Assista agora a um vídeo no qual são apresentados os algoritmos para remoção de símbolos não geradores,
remoção de produções unitárias e remoção de produções nulas em gramáticas livres de contexto.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Remoção dos símbolos inúteis
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
S→aX|bX X→a|b|λ
S→aX|bX|a|b X→a|b
Remoção das produções unitárias
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Considerando os símbolos não geradores, avalie as seguintes alternativas:
 
I. Não geram nenhuma sequência de terminais e não terminais.
II. Não geram nenhuma sequência de terminais.
III. Não geram nenhuma sequência de produções.
 
Qual opção inclui afirmativas corretas?
A
I e II
B
II e III
C
III
D
II
E
I
A alternativa D está correta.
Símbolos não geradores são aqueles símbolos que não geram nenhuma sequência de terminais.
Questão 2
Qual das seguintes alternativas é uma produção unitária (T = Terminal e NT = Não terminal)?
A
(cadeia de NT)→(cadeia de NT)
B
(NT único)→(cadeia de NT)
C
(NT)→(NT único)
D
(cadeia de NT)→(NT único)
E
(T único)→(T único)
A alternativa C está correta.
Produções unitárias são produções da forma A→B, em que A e B são não terminais, e costumam ser
descartadas das GLC porque nada acrescentam às formas sentenciais às quais são aplicadas, constituindo
mera renomeação de símbolos.
3. Autômatos de pilha
Conceitos fundamentais
Autômatos finitos
Um autômato finito (AF), também conhecido como máquina de estados finita (MEF), fornece o modelo maissimples de um dispositivo de computação. É chamado finito porque tem um número finito de estados. O
estado do sistema memoriza as informações relativas à entrada anterior. A partir daí, é necessário determinar
o comportamento futuro do sistema, ou seja, qual o próximo estado a ser atingido, a partir daquela entrada
específica. 
Atenção
A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado
armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no
início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita
por uma condição que precisa ser realizada para que a transição ocorra. 
Os autômatos finitos são empregados como reconhecedores de expressões regulares geradas por gramáticas
regulares. A seguir uma figura de um AF.
Esquema de autônomo finito.
Definição: Um AF pode ser definido da seguinte forma: é um AF se:
Diagrama mecânico de um autômato finito
Mecanicamente, autômatos finitos podem ser descritos como uma fita de entrada contendo os símbolos de
entrada (I) com um cabeçote de leitura varrendo as entradas da esquerda para a direita. As entradas são
alimentadas ao controle finito que contém as funções de transição (fs). De acordo com as funções de
transição, ocorre a mudança de estado (Q).
O diagrama mecânico de autômatos finitos é mostrado na figura a seguir. 
Diagrama mecânico de autômatos.
A fita de entrada contém o símbolo de entrada e é dividida em vários quadros, que contêm caracteres do
alfabeto de entrada. Ambas as extremidades da fita de entrada contêm marcadores. Entre dois marcadores a
cadeia a ser lida é colocada. Essa cadeia precisa ser processada da esquerda para a direita. 
A cabeça varre cada quadro na fita de entrada e lê uma entrada de cada vez. A cabeça pode se mover da
esquerda para a direita ou da direita para a esquerda. Mas, na maioria dos casos, a cabeça move-se, somente,
da esquerda para a direita. 
Comentário
O controle finito pode ser considerado como a unidade de controle de um AF. Um autômato sempre
reside em um estado. O cabeçote de leitura escaneia a entrada da fita de entrada e a envia para controle
finito. O controle finito sabe que a máquina está neste estado e está recebendo esta entrada, então ele
decide que irá para algum outro estado. As regras de transição de estado são escritas no controle finito. 
Conceito de pilha
Uma pilha é um tipo abstrato de dado. É uma estrutura de dados baseada no princípio de Last In First Out
(LIFO), ou seja, o último que entra é o primeiro que sai, caracterizando um empilhamento de dados. Pilhas
possuem somente uma entrada chamada de topo e são fundamentalmente compostas por duas operações: 
push (empilhar), que adiciona um elemento no topo da pilha, e pop (desempilhar), que remove o último
elemento adicionado, aquele que está no topo da pilha. A figura a seguir ilustra as operações de push e pop. 
Operações de push e pop .
Observe que essas operações são controladas por um apontador (topo) que indica sempre a próxima posição
vazia onde pode ser empilhado um dado. No início do empilhamento da figura acima, o topo tem valor 2,
indicando que a próxima posição vazia, onde pode ser empilhado um dado, é a posição 2 da pilha. No canto
inferior direito, vemos que ainda há um elemento na pilha (1). O topo aponta para a posição 2. Ao ser retirado e
elemento 1, o topo ficará com valor 1, indicando que a pilha está vazia. 
Comentário
Conceitualmente, as pilhas podem crescer indefinidamente, mas, na prática, estão limitadas pela
memória disponível do computador. Um sistema baseado em pilha é aquele que armazena a informação
temporária em pilhas. 
O conceito de pilha é amplamente utilizado na informática, como, por exemplo, durante a execução de um
programa, para o armazenamento de valores de variáveis locais a um bloco e para manter o endereço de
retorno ao trecho de programa que chamou a função ou procedimento atualmente em execução.
Os dispositivos que fazem uso de pilha costumam definir a forma de operação como uma das seguintes
possibilidades: 
Pilha tipo stack
Além das operações de empilhamento e
desempilhamento de elementos no topo da
pilha (push e pop), permite que os demais
elementos sejam endereçados diretamente,
somente para consulta.
Pilha pushdown
Permite o acesso apenas ao elemento
armazenado no topo, através das operações de
empilhamento e desempilhamento (push e pop).
Não permite o endereçamento dos demais
elementos.
Autômatos de pilha
Definição de autômato de pilha
Os autômatos de pilha (em inglês, push down automata – PDA) são o formato de máquina de autômatos finitos
para linguagens livres de contexto. É um autômato finito com a anexação de uma quantidade auxiliar de
armazenamento chamada de pilha. Os autômatos de pilha são projetados para reconhecer linguagem geradas
por GLC, as LLC. 
Uma linguagem anbn não é reconhecível pelos autômatos finitos devido à limitação de memória, mas os
autômatos de pilha podem memorizar o número de ocorrências de ‘a’ e combiná-lo com o número de
ocorrências de ‘b’ com a ajuda da pilha. 
Os autômatos de pilha constituem a segunda instância, em uma escala de complexidade crescente, do
modelo genérico de reconhecedor, prestando-se ao reconhecimento de linguagens livres de contexto.
Um PDA consiste em 7 tuplas: 
Onde:
 
Q denota um conjunto finito de estados;
Σ denota um conjunto finito de símbolos de entrada;
Γ denota um conjunto finito de símbolos de pilha;
δ denota as funções de transição;
01 D
45 E
01 D
45 E0 é o estado inicial do PDA ( 0 01D
444∈ );
01 D
46 7 0 é o símbolo do fundo da pilha;
F é o estado final do PDA.
No PDA, a função de transição δ está na forma:
Dos sete elementos que compõem este sistema formal, apenas três são diferentes dos autômatos finitos — δ,
Γ e —, uma vez que os demais estão em correspondência direta. O alfabeto de pilha (Z0) especifica os
símbolos que podem ser armazenados na pilha. Por convenção, um desses símbolos, denotado ,
representa o conteúdo inicial da pilha a cada vez que o autômato de pilha principia o reconhecimento de uma
nova sentença. 
Ao longo de sua operação, elementos de Γ são acrescentados e/ou removidos da pilha, e seu conteúdo total
pode ser interpretado, em um dado instante, como sendo um elemento de Γ*. Por convenção, cadeias de Γ,
que representam o conteúdo da pilha em um determinado instante, são interpretadas considerando-se os
símbolos mais à esquerda da cadeia no topo da pilha, e os símbolos mais à direita da cadeia no fundo da pilha.
A função de transição é denotada por δ, representada por:
Diagrama mecânico
1. 
2. 
3. 
4. 
5. 
6. 
7. 
O PDA está em algum estado. Com um símbolo de entrada da fita de entrada e com o símbolo do topo da
pilha, o PDA se move para a direita, podendo mudar seu estado e empurrar (push) algum símbolo na pilha ou
retirar (pop) algum símbolo do topo da pilha.
Conforme a imagem, temos:
Fita de entrada
A fita de entrada contém os símbolos de entrada. A fita é dividida em vários quadros. Cada quadro
contém um único caractere de entrada. A cadeia colocada na fita de entrada é percorrida da
esquerda para a direita. Os lados inicial e final da cadeia de entrada podem conter um número infinito
de símbolos em branco ou a fita pode ser limitada por um símbolo inicial (@) e um terminal ($).
Cabeça de leitura
A cabeça varre cada quadrado na fita de entrada e lê a entrada da fita. A cabeça se move da
esquerda para a direita. A entrada escaneada pelo cabeçote de leitura é enviada ao controle finito do
PDA.
Controle finito
O controle finito pode ser considerado como uma unidade de controle de um PDA. Um autômato
sempre reside em um estado. O cabeçote de leitura escaneia a entrada da fita de entrada e a envia
para o controle finito. Uma cabeça bidirecional também é adicionada com o controle finito ao topo da
pilha. Dependendo da entrada retirada da fita e da entrada do topo da pilha, o controle finito decide
para qual estado o PDAse moverá e qual símbolo de pilha ele empurrará ou retirará da pilha ou se não
fará nada na pilha.
Pilha
Uma pilha é um armazenamento temporário de símbolos de pilha. Cada movimento do PDA indica uma
das seguintes ações para a pilha:
Um símbolo de pilha pode ser inserido no topo da pilha (push);
Um símbolo de pilha pode ser retirado do topo da pilha (pop);
A pilha não será alterada.
A pilha é o componente do PDA que o diferencia dos autômatos finitos. Na pilha, há sempre um
símbolo que denota a parte inferior da pilha. A pilha está vazia quando apenas está inserido
na base.
Pushdown autômata
Push é uma operação onde um símbolo é adicionado ao topo da pilha. Em autômatos finitos, os estados atuam
como uma forma de memória primitiva. Os estados memorizam os não terminais encontrados no momento da
derivação de uma cadeia. 
Comentário
Assim, apenas o estado é suficiente para percorrer uma expressão regular como no caso de autômatos
finitos. Vamos considerar um caso de , onde . Não é uma expressão regular, mas uma LLC. Aqui, n é
qualquer número. Na cadeia, há um número igual de 'a' e 'b'. 
Nesta cadeia, todos os ‘a’s aparecem antes de ‘b’. Dessa forma, a máquina, para percorrer anbn tem que
lembrar o número de ‘a’s para percorrer um número igual de ‘b’. ‘n’ é qualquer número. Portanto, para
memorizar o número de ‘a’s na cadeia, a máquina requer um número infinito de estados, ou seja, a máquina
não será uma máquina de estados finitos.
Para remover esse gargalo, precisamos adicionar uma memória auxiliar na forma de uma pilha. Para cada
ocorrência de ‘a’ na cadeia L, um símbolo é inserido na pilha. Para cada ocorrência de b (após terminar ‘a’), um
símbolo será retirado da pilha. Por este processo, a correspondência de ‘a’ e ‘b’ será feita. Ao adicionar uma
pilha aos autômatos finitos, o PDA é gerado. 
Funcionamento dos autômatos de pilha
Descrição instantânea
A descrição instantânea (instant description - ID) é assim chamada porque descreve a configuração do PDA
em uma determinada instância. O ID lembra as informações do estado e o conteúdo da pilha em uma
determinada instância de tempo.
Um ID é um formato de tripla (q,w,κ), onde q ∈ Q (conjunto finito de estados), w ∈ Σ (alfabeto = conjunto
finito de símbolos de entrada) e κ ∈ Γ (conjunto finito de símbolos de pilha).
Vejamos as duas maneiras de declarar uma cadeia aceita por um PDA. 
Aceitação por pilha vazia
• 
• 
• 
Sabemos que em cada PDA há uma pilha anexada. Na parte inferior da pilha, há o chamado símbolo do fundo
da pilha, z0. Em cada movimento do PDA, um símbolo chamado símbolo de pilha é inserido ou retirado da
pilha. O símbolo z0 sempre permanece na pilha.
Uma cadeia w pode ser declarada aceita por uma pilha vazia se, após o processamento de todos os símbolos
de w, a pilha estiver vazia. 
Em notação matemática, podemos dizer que se é um PDA, a cadeia w é
declarada aceita pela pilha vazia se: 
Em outras palavras, uma cadeia é aceita por um PDA por pilha vazia se, após um número indeterminado de
mudanças de estado, ambas as seguintes condições forem atendidas:
 
A cadeia está totalmente percorrida (finalizada);
A pilha está vazia.
Aceitação pelo estado final
Uma cadeia w pode ser declarada aceita pelo estado final se, após a passagem total da cadeia w, o PDA
entrar em um estado final. Em notação matemática, podemos dizer que se é um
PDA, a cadeia w é declarada aceita pelo estado final se: 
Em outras palavras, uma cadeia é aceita por um PDA pelo estado final se ambas as seguintes condições forem
atendidas:
 
A cadeia está totalmente percorrida (finalizada);
O PDA entra em um estado final.
 
Exemplo prático
Para melhor entendimento desta teoria, vamos construir um PDA para aceitar a linguagem 
 tanto por pilha vazia quanto pelo estado final.
Solução: A cadeia é anbn onde n≥1. As observações que podemos extrair dessa cadeia são:
 
A cadeia consiste em um alfabeto com dois símbolos terminais ‘a’ e ‘b’.
Todos os ‘a’ aparecem antes de ‘b’.
O número de ‘a’ é igual ao número de ‘b’.
Há pelo menos um ‘a’ e um ‘b’ na menor cadeia dessa linguagem.
• 
• 
• 
• 
• 
• 
• 
• 
Temos que verificar e garantir o mesmo número de ‘a’ e ‘b’ em cada cadeia para que seja reconhecida. Vamos
usar um símbolo de pilha z1, que é inserido na pilha (push), quando um ‘a’ é lido da fita de entrada. No início, o
PDA está no estado q0 e o topo da pilha é z0 (já que no início não há outro símbolo na pilha). 
Nesse estado, o autômato obtém uma entrada ‘a’ da fita de entrada (a cadeia começa com ‘a’ por definição).
Assim, A função δ é: e um símbolo de pilha z1 é inserido, conforme a figura a
seguir. 
A partir do próximo símbolo ‘a’ da fita de entrada, o PDA está no estado Q0 e o topo da pilha é z1, então outro
z1 é inserido na pilha. A função δ é: e mais um símbolo de pilha z1 é inserido,
conforme a figura a seguir.
Por esta função δ, todos os ‘a’ restantes são percorridos. Após último ‘a’ ser lido na fita de entrada, começam a
ser lidos os ‘b’. Quando o primeiro ‘b’ é lido, o PDA está no estado q0 com o topo da pilha contendo z1. 
Quando ‘b’ for lido, o topo da pilha z1 será exibido e o PDA mudará seu estado para q1 (para que não haja
chance de inserir Z1 na pilha se algum ‘a’ ocorrer). 
O PDA é projetado apenas para a cadeia anbn, mas a cadeia de entrada pode não estar nessa forma e não
poderá ser aceita pelo PDA. A função δ é: 
Quando o próximo ‘b’ aparece, o PDA está no estado q1 com o topo da pilha z1. Esse z1 é retirado (pop). A
função δ é: 
Por meio dessa função, todos os ‘b’s restantes são lidos.
Se a cadeia de entrada estiver na forma anbn, onde n≥1, então, depois de percorrer o último ‘b’, o PDA estará
no estado q1 com o topo da pilha z0 (todos os outros símbolos da pilha foram retirados).
Se tivermos que projetar o PDA aceito pela pilha vazia, a função δ será: 
Se tivermos que projetar o PDA aceito pelo estado final, a função δ será:
Assim, o PDA para :
Onde:
 
01 D
444
01 D
45 E
01 D
45 E
01 D
45 E
01 D
45 3={ 0, 1, };
Σ = {a, b};
01 D
44D
01 D
44DΓ={ 0, 1};
01 D
45 EEstado inicial = { 0};
01 D
46 7Símbolo do fundo da pilha = { 0};
01 D
45 E
01 D
45 3Estado final = { }.
δ é definido da seguinte forma:
 
01 D
6 F F
01 D
45 E
01 D
44E
01 D
46 7
01 D
45 E
01 D
46 7
01 D
46 7( 0, , 0)→( 0, 1, 0)
01 D
6 F F
01 D
45 E
01 D
44E
01 D
46 7
01 D
45 E
01 D
46 7
01 D
46 7( 0, 1, 0)→( 0, 1, 1)
01 D
6 F F
01 D
45 E
01 D
44F
01 D
46 7
01 D
45 E
01 D
7 06( 0, , 1)→( 1, )
01 D
6 F F
01 D
45 E
01 D
44F
01 D
46 7
01 D
45 E
01 D
7 06( 1, , 1)→( 1, )
01 D
6 F F
01 D
45 E
01 D
7 06
01 D
46 7
01 D
45 E
01 D
7 06( 1, , 0)→( 1, ) (aceito por pilha vazia)
01 D
6 F F
01 D
45 E
01 D
7 06
01 D
46 7
01 D
45 E
01 D
45 3
01 D
46 7( 1, , 0)→( , 0) (aceito por atingir o estado final)
Funcionamento dos autômatos de pilha
Assista agora a um vídeo no qual é apresentado o funcionamento dos autômatos de pilha.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Autômatos finitos
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Autômatos de pilha
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Analise as afirmativas relativas ao diagrama mecânico do PDA?
I. O PDA contém uma pilha.
II. A cabeça lê e escreve.
III. A cabeça se move da esquerda para a direita.
Quais as afirmativas verdadeiras?
A
I e II.
B
I e III.
C
I, II e III.
D
Somente I.
E
Somente III.
A alternativa B está correta.
A cabeça de leitura apenas lê, não escreve na fita, que permanece inalterada.
Questão 2
A descrição instantânea lembra:
A
As informações de estado e conteúdo da fita de entrada em uma determinada instância de tempo.
B
As informações da pilha e conteúdo da fita em uma determinada instância de tempo.C
As informações da fita de entrada e do conteúdo da pilha em uma determinada instância de tempo.
D
As informações de estado, fita de entrada e conteúdo da pilha em uma determinada instância de tempo.
E
As informações de estado e conteúdo da pilha em uma determinada instância de tempo.
A alternativa E está correta.
Conforme definição de descrição instantânea, ela descreve a configuração do PDA em uma determinada
instância e o ID lembra as informações do estado e o conteúdo da pilha em uma determinada instância de
tempo.
4. Propriedades das linguagens livres de contexto
Propriedades de fechamento
Fechamento na união
Um conjunto é fechado (sob uma operação) se e somente se a operação em dois elementos do conjunto
produz outro elemento do próprio conjunto. Se essa operação produzir um elemento fora do conjunto, a
operação não será fechada.
Atenção
O fechamento é uma propriedade que descreve a aplicação da propriedade em quaisquer dois
elementos do conjunto e o resultado também deve estar contido no conjunto. 
Sejam L1 uma LLC com a GLC G1 = (V1, Σ1, P1, S1) e L2 com a G2 = (V2, Σ2, P2, S2). Temos que provar que L3
= L1 U L2 também é uma LLC. 
Vamos construir uma gramática G3 = (V3, Σ3, P3, S3) usando as duas gramáticas G1 e G2 como: 
Fica claro que G3 contém todos os símbolos não terminais de G1 e de G2 (V1 U V2). O alfabeto de L3 contém
todos os símbolos dos alfabetos de L1 e de L2 (Σ1 U Σ2). Adicionalmente, todas as produções de G3 são
formadas por produções de G1 e de G2, e o símbolo inicial de G3 nos leva aos símbolos iniciais S1 ou S2,
permitindo a utilização das produções de uma ou de outra das gramáticas. Assim, fica provado que L3 = L1 U
L2.
Fechamento na concatenação
Sejam L1 uma LLC com a GLC G1 = (V1, Σ1, P1, S1) e L2 com G2 = (V2, Σ2, P2, S2). Temos que provar que L3 =
L1L2 também é uma LLC.
Para tanto, vamos construir uma gramática G3 = (V3, Σ3, P3, S3) usando as duas gramáticas G1 e G 2 como: 
Fica claro que G3 contém todos os símbolos não terminais de G1 e de G2 (V1 U V2). O alfabeto de L3 contém
todos os símbolos dos alfabetos de L1 e L2 (Σ1 U Σ2). Adicionalmente, todas as produções de G3 são
formadas por produções de G1 e de G2, e o conjunto da linguagem gerado a partir da gramática G3 contém
todas as cadeias derivadas de S1 assim como de S2. Desse modo, fica provado que L3 = L1L2.
Fecho de Kleene
Seja L1 uma LLC com a GLC G1 = (V1, Σ1, P1, S1). Temos que provar que L1* também é uma LLC. Então, vamos
construir uma gramática G2 = (V2, Σ2, P2, S2) usando a gramática G1 como segue:
V3 = V1 U V2 ∪ {S} Σ3 = Σ1 U Σ2 P3 = P1 U P2 {S3→S1|S2}
V3 = V1 U V2 ∪ {S} Σ3 = Σ1 U Σ2 P3 = P1 U P2 {S3→S1S2}
Note que L1* contém todos os símbolos não terminais de V1 mais o seu próprio símbolo inicial. As produções
de P2 contém as de G1, sendo possível a concatenação das produções a partir de S1S2. Finalmente, S2 tem
uma produção que leva à cadeia vazia (λ). Já vimos que é possível retirar as produções nulas criando uma
GLC equivalente que gera a mesma LLC. Portanto, L2(G2) = L1*.
Não fechamento na intersecção
A família de linguagens livres de contexto não é fechada na interseção. Provaremos utilizando um
contraexemplo. 
Considere as duas linguagens: 
Claramente, L1 e L2 são LLC. Por exemplo, uma gramática para L1 é:
Logo, essa gramática é uma GLC.
Alternativamente, notamos que L1 é a concatenação de duas linguagens livres de contexto, então é livre de
contexto conforme já demonstrado anteriormente (Fechamento na Concatenação). Ocorre que a intersecção
das duas linguagens é: 
 é uma linguagem sensível ao contexto, tipo 1 na hierarquia de Chomsky. Como provamos que uma
instância de intersecção não é livre de contexto, podemos concluir que linguagens livres de contexto não são
fechadas sob a operação de interseção.
Não fechamento na complementação
A partir da teoria dos conjuntos, podemos provar que, para duas LLC L1 e L2, vale a lei de D´Morgan:
V2 = V1 U {S2} P2 = S2→S1S2|λ
S→S1S2 S1→aS1 b|λ S2→cS2|λ
Se a família de linguagens livres de contexto fosse fechada sob complementação, então o lado direito da
expressão acima seria uma linguagem livre de contexto para qualquer L1 e L2 livre de contexto.
Porém, isso contradiz o que acabamos de mostrar, uma vez que essa complementação é equivalente à
interseção das duas linguagens e, conforme demonstrado anteriormente, a intersecção de duas linguagens
livres de contexto não é necessariamente livre de contexto. Consequentemente, a família de linguagens livres
de contexto não é fechada sob complementação. 
Toda linguagem regular é uma LLC
Pela definição recursiva de conjunto regular, sabemos que Ø e λ são expressões regulares. Se R é uma
expressão regular, então R+R (união), RR (concatenação) e R* (fecho de Kleene) também são expressões
regulares. Uma expressão regular R é uma sequência de símbolos terminais. Ø e λ também são LLC, e
sabemos que LLC são fechadas sob união, concatenação e fecho de Kleene. Portanto, podemos escrever que 
toda linguagem regular é uma LLC.
Lema da altura da árvore de derivação
Aplicação de estruturas em árvores
Uma árvore possui um nó raiz a partir do qual derivam outros nós, seguindo uma lei de formação. Árvores
costumam ser representadas esquematicamente com a raiz na parte superior da figura, e com os arcos e
demais vértices “crescendo” para baixo.
Vértices, onde o número de filhos é igual a zero, são denominados folhas da árvore. Os demais são
denominados vértices internos. Inclui-se, por essa definição, entre os vértices internos de uma árvore, o
vértice-raiz dessa árvore. 
A profundidade de um nó é a distância deste nó até a raiz. A maior profundidade de um nó, é a altura
da árvore.
As árvores são estruturas muito utilizadas para representar derivações em linguagens computacionais ou
mesmo para a linguagem natural. São especialmente importantes no estudo das linguagens formais e, muito
aplicadas na prática, para a análise e construção de compiladores.
Forma normal de Chomsky
Um outro tipo de forma normal, além da BNF, é aquela em que o número de símbolos à direita de uma
produção é estritamente limitado. Em particular, a cadeia à direita de uma produção consiste em não mais que
dois símbolos. Um exemplo disso é a forma normal de Chomsky (CNF). Definição:
Uma gramática livre de contexto está na forma normal de Chomsky se todas as produções são da forma
A→BC ou A→a, onde A, B, C estão em V e “a” está em T.
Por exemplo, a gramática está na forma normal de Chomsky, conforme abaixo:
Já a gramática não está porque ambas as produções S→AAS e A→aa violam as condições da CNF, dado que:
Assim, qualquer gramática livre de contexto tem uma gramática equivalente na forma normal de Chomsky. 
S→AS|a A→SA|b
S→AS|AAS A→SA|aa
Lema da altura da árvore de derivação
Antes de discutir o enunciado do lema do bombeamento, precisamos provar o seguinte lema:
Seja G uma GLC em CNF e A uma árvore de derivação que pertence a G. Se o comprimento do caminho mais
longo em A for menor ou igual a k, então a maior altura de A é de comprimento menor ou igual a . 
Árvore de Derivação
Demonstração: Vamos provar pelo método de indução em k. Seja k o caminho mais longo para todas as
árvores com rótulo raiz S. Quando o caminho mais longo da árvore S tem comprimento 1, a raiz tem apenas um
filho, e esse é o símbolo terminal. Quando a raiz tem dois filhos, os rótulos são variáveis (lembre-se: a GLC
está em CNF). Então, a altura de S é de comprimento 1. Temos aqui uma base para indução.
Seja k > 1 e seja A uma árvore S com o caminho mais longo de comprimento menor ou igual a k. A gramática
está na CNF, então a raiz de A, ou seja, S, tem exatamente dois filhos com rótulos S1 e S2. O comprimento do
caminho mais longo das duas subárvores com os dois filhos como raiz é menor ou igual a k – 1 (Veja a figura
acima).
Se w1 e w2 são cadeias A1 e A2, respectivamente, por indução: 
Seja w a altura de A, então w = w1w2 é a concatenação das duas cadeias geradas.
A altura de A é de comprimento menor ou igual a .
Lemado bombeamento
Lema do bombeamento para LLC
O lema do bombeamento é uma ferramenta eficaz para mostrar que certas linguagens não são regulares. 
Atenção
O lema do bombeamento para linguagens regulares é baseado no fato de que todas as cadeias em uma
linguagem regular devem apresentar um certo padrão repetitivo. Se uma linguagem L contém uma
cadeia que não segue esse padrão, então L não é regular. 
Um raciocínio semelhante leva ao lema de bombeamento para linguagens livres de contexto. Para linguagens
regulares, o padrão é uma consequência da finitude da representação do autômato finito determinístico. Com
linguagens livres de contexto, o padrão é mais facilmente visto através da gramática.
O lema de bombeamento para LLC é usado para provar que certos conjuntos não são livres de contexto. Cada
LLC cumpre algumas propriedades gerais. Mas se um conjunto ou linguagem preenche todas as propriedades
do lema de bombeamento para LLC, não se pode dizer que a linguagem é livre de contexto. O inverso é
verdadeiro, ou seja, se uma linguagem quebra as propriedades pode-se afirmar que a linguagem não é livre de
contexto.
Seja L uma LLC. Então, podemos encontrar um número natural n tal que:
 
Todo z ϵ L com z ≥ n pode ser escrito como w = uvwxy, para algumas cadeias u,v,w,x,y.
|vx| ≥ 1.
|vwx| ≤ n.
 para todo 
Assumimos que o conjunto é livre de contexto e, aplicando o lema do bombeamento, obtemos uma
contradição. Essa prova pode ser feita da seguinte maneira:
Assuma que L é livre de contexto. Encontre um número natural tal que|z|≥ n.
Então, podemos escrever z = uvwxy para algumas cadeias u,v,w,x,y.
Encontre um k adequado tal que . Isso é uma contradição e, portanto, L não é livre de
contexto.
Exemplo prático
Mostre que onde não é livre de contexto (Kandar, 2013).
Solução: 
Suponha que essa linguagem L seja uma LLC. Seja n um número natural obtido usando o lema do
bombeamento.
 
Seja . Então, . De acordo com o lema de bombeamento para CFL, podemos
escrever uvwxy, onde (para o caso ).
 
uvwxy . Como , (|vwx , então v ou não pode conter todos
os três símbolos a, b e c. Então, v ou x estará em qualquer uma das seguintes formas. 
 1. Contêm apenas a e b, ou seja, na forma . 
 2. Ou conter apenas b e c, ou seja, na forma . 
 3. Ou conter apenas a repetição de qualquer um dos símbolos entre a, b e c.
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
 
Vamos tomar o valor de k como 2. ou estará na forma (como v é uma cadeia aqui ‘aba’ não é
igual a ou ) ou . Assim, não pode estar na forma . Então, 
Se v ou x contiver a repetição de qualquer um dos símbolos entre a, b e c, então v ou x terá a forma de 
ou . Tomemos o valor de k como 0. uwy. Nessa cadeia, o número de ocorrências de um dos
outros dois símbolos em uvy é menor que n. Então, 
Propriedades decidíveis
Vaziez
Há uma série de problemas de decisão relacionados a GLC. A seguir estão dois deles.
Se uma determinada LLC é vazia ou não. (Ela gera alguma cadeia de terminal?)
Se uma determinada LLC é finita. (Ela gera uma palavra de até um certo comprimento?)
Para o propósito deste item, assumimos que a linguagem é descrita por sua gramática. 
Caso o símbolo inicial S gere uma cadeia de terminais, então ela não é vazia; caso contrário, a LLC
correspondente é vazia. 
Dada uma gramática livre de contexto G = (V,T,P,S), existe um algoritmo para decidir se L(G) é ou não vazia. 
Prova: Por simplicidade, suponha que . Isso pode ser feito retirando produções nulas. Usamos o
algoritmo para remover símbolos e produções inúteis. Se o símbolo inicial S for considerado inútil, então L(G) é
vazia, caso contrário L(G) contém pelo menos um elemento. 
Finitude
Dada uma gramática livre de contexto G = (V,T,P,S), existe um algoritmo para decidir se L(G) é ou não infinita.
Uma linguagem L gerada a partir de uma dada GLC é finita se não houver ciclos no grafo direcionado gerado a
partir das regras de produção dessa GLC. A cadeia mais longa gerada pela gramática é determinada pela
derivação do símbolo inicial.
O número de vértices do grafo direcionado é o mesmo que o número de não terminais na gramática. Se
houver uma regra de produção S→AB, o grafo direcionado é como mostrado: 
Neste caso a LLC é finita. Vejamos um exemplo para melhor fixação.
Seja a gramática: 
1. 
2. 
O gráfico direcionado para a gramática é mostrado a seguir:
O gráfico não contém nenhum loop, assim, a linguagem gerada pela GLC é finita. 
A derivação da gramática é S→AB→BCB→aaa.
Uma linguagem L gerada a partir de uma dada GLC é infinita se houver pelo menos um ciclo no grafo
direcionado gerado a partir das regras de produção dessa GLC. Vejamos um exemplo para melhor fixação.
Seja a seguinte gramática: 
O gráfico de transição não terminal para a gramática é mostrado a seguir.
O gráfico contém loops, logo a linguagem gerada pela GLC é infinita.
S→AB A→BC B→a C→a
S→AB A→SC|a B→SC |a C→AB|b
Exemplos práticos
LLC e linguagem regular
Sabemos que uma gramática regular é um subconjunto de uma LLC. Assim, para toda linguagem regular,
existe um LLC. Vejamos um teorema relacionado a esse tópico. 
Teorema 1: Toda linguagem regular é gerada por uma GLC.
Demonstração: Assuma que L é regular. Dessa forma, existe um autômato finito determinístico (AFD) M = {Q,
Σ, δ, q0, F} que aceita L. A partir do AFD M, podemos gerar uma GLC G = {V, Σ, P, S} usando as seguintes
regras.
Todo estado ϵ Q de M é tratado como um não-terminal ϵ V. O estado inicial (estado inicial do AFD).
Para uma função de transição δ(q1, a)→q2, onde q1, q2 ϵ Q e a ϵ Σ, adicione uma produção q1→aq2 em P.
Se q2 é um estado final, adicione q1→aq2 e q1→a em P.
Todas as produções têm um único não terminal no lado esquerdo. Assim, é uma gramática livre de contexto. 
Aplicação de GLC
O compilador é um programa tradutor, sendo a análise sintática uma fase importante no seu projeto, pois os
erros gramaticais chamados de erros de sintaxe são verificados. O analisador sintático verifica se um
programa fonte satisfaz as regras impostas por uma gramática livre de contexto. Se satisfizer, o analisador
cria a árvore de análise sintática desse programa. Caso contrário, o analisador fornece as mensagens de erro.
Na linguagem C, um identificador é descrito pela GLC a seguir: 
Um programador declara as seguintes variáveis:
Um erro de sintaxe será mostrado na quarta linha, onde o identificador começa por um número e não por uma
letra. 
A GLC também é usada para desenvolver a linguagem de marcação XML. 
Construção de GLC
Construa uma GLC para o conjunto de todos os inteiros ímpares (Kandar, 2013).
Um número inteiro é ímpar se sua entrada mais à direita contiver '1', '3', '5', '7' ou '9'. Se o inteiro for positivo,
sua entrada mais à esquerda contém um sinal '+'; se negativo, sua entrada mais à esquerda contém um sinal
'-'. O símbolo inicial será S.
Podemos iniciar a gramática com a seguinte produção:
Podemos iniciar a gramática com a seguinte produção: S→ 
O não terminal pode ser expandido como: →
identificador> ::= letra (letra|dígito)* letra> ::= a|b|c |.... |z|A|B|C |....|Z dígito> ::= 0|1|2|3|4|
5|6|7|8|9
int capital; int r_o_i; int year; int 1st_year_interest
1. 
2. 
O não terminal pode ser expandido como: →| λ
Podemos escrever: →+|-
O não terminal pode ser expandido: →|1|2|3|4|5|6|7|8|9
Finalmente, →|1|3|5|7|9
O conjunto de não terminais V é {S, , , , , }.
As regras de produção são:
Propriedades de fechamento
Assista agora a um vídeo no qual é apresentada uma série de fechamentos abordados no módulo.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Lema do bombeamento para LLC
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Operações sobre LLC
Conteúdo interativoAcesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Considerando que um conjunto é fechado se e somente se a operação em dois elementos do conjunto produz
outro elemento do próprio conjunto, avalie as seguintes opções relacionadas com uma linguagem livre de
contexto:
 
( ) Não fechada para união
( ) Fechada para concatenação
3. 
4. 
5. 
6. 
7. 
S→sinal>inteiro> inteiro>→inteiro1>digito1> inteiro1>→inteiro1>digito>| λ sinal>→+|-
digito>→|1|2|3|4|5|6|7|8|9 digito1>→|1|3|5|7|9
( ) Não fechada para complementação
( ) Fechada para fecho de Kleene
( ) Fechada para diferença
 
Quais as afirmativas são verdadeiras (V) e falsas (F)?
A
V, V, V, V, V
B
F, V, V, F, V
C
F, V, V, V, V
D
F, V, F, V, V
E
V, V, V, F, F
A alternativa C está correta.
Uma linguagem livre de contexto é fechada para união, concatenação, fecho de Kleene e diferença, não
sendo fechada para complementação.
Questão 2
Considerando que o lema do bombeamento é uma ferramenta eficaz para mostrar que certas linguagens não
são regulares, analise as seguintes afirmativas:
 
I - O lema de bombeamento para linguagens regulares é baseado no fato de que todas as cadeias em uma
linguagem regular devem apresentar um certo padrão repetitivo.
II - O lema de bombeamento para LLC é usado para provar que certos conjuntos não são livres de contexto.
III - O lema de bombeamento pode ser outro tipo de forma normal, além da BNF, onde o número de símbolos à
direita de uma produção é estritamente limitado.
 
Quais são as afirmativas verdadeiras?
A
I e II.
B
I e III.
C
I, II e III.
D
Somente I.
E
Somente III.
A alternativa A está correta.
A forma normal de Chomsky é um outro tipo de forma normal, além da BNF, onde o número de símbolos à
direita de uma produção é estritamente limitado, o que invalida a opção III.
5. Conclusão
Considerações finais
Iniciamos tratando de noções e terminologias matemáticas, focando em noções básicas sobre símbolos,
cadeias, alfabetos, gramáticas e linguagens, bem como do importante tema de fechamento e apresentamos a
hierarquia de Chomsky.
As linguagens livres de contexto são fechadas para a operação de união, concatenação e fecho de Kleene e
não são fechadas para as operações de interseção e complementação. 
Uma GLC pode conter diferentes tipos de símbolos inúteis, produções unitárias e produções nulas. Esses tipos
de símbolos e produções aumentam o número de etapas na geração de uma linguagem a partir de uma GLC.
Assim, reduzimos a gramática.
Uma linguagem L gerada a partir de uma dada GLC é finita se não houver ciclos no grafo direcionado gerado a
partir das regras de produção e é infinita se houver pelo menos um ciclo no grafo direcionado gerado a partir
das regras de produção. 
Finalmente, mas não menos importante, são as formas normais de Backus-Naur (BNF) e a forma norma de
Chomsky (CNF). Especialmente a BNF é muito usada na especificação de linguagens de programação. 
Podcast
Ouça agora uma entrevista com o professor Tomás de Aquino Tinoco Botelho, que complementa e
aprofunda o conteúdo abordado.
Conteúdo interativo
Acesse a versão digital para ouvir o áudio.
 Explore +
Conheça a ferramenta para experimentos práticos com linguagens formais: JFLAP. Disponível na internet. 
Veja um exemplo real de especificação da linguagem de programação Java no site da Oracle, no capítulo que
trata de gramática: Chapter 2. Grammars. Disponível na internet. 
Referências
FEITOSA, Hércules et al. Teoria dos conjuntos. 1. ed. Rio de Janeiro: Ciência Moderna, 2021.
 
HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à teoria de autômatos, linguagens e
computação. 1. ed. São Paulo: GEN LTC, 2002.
 
KANDAR, Shyamalendu. Introduction to automata theory, formal languages and computation. Nova York:
Pearson, 2013.
 
LINZ, Peter. An introduction to formal languages and automata. 6. ed. Burlington: Jones & Bartlett Learning,
2016.
 
MENEZES, Paulo. B. Linguagens Formais e Autômatos. 5. ed. Porto Alegre: Sagra Luzzatto, 1997.
	Linguagens livres de contexto
	1. Itens iniciais
	Propósito
	Objetivos
	Introdução
	1. Gramáticas livres de contexto
	Conceitos básicos
	Símbolo, alfabeto e cadeia
	Símbolo
	Alfabeto
	Cadeia
	Concatenação
	Linguagem formal
	Gramática
	Lado esquerdo (LE)
	Lado direito (LD)
	Fechamento
	Fechamento reflexivo
	Fechamento transitivo
	Exemplo
	Representação de linguagens
	Exemplo
	Fecho de Kleene
	Exemplo
	Exemplo
	Exemplo
	Hierarquia de Chomsky
	Tipos de Gramáticas
	Gramática tipo 0
	Gramática tipo 1
	Gramática tipo 2
	Gramática tipo 3
	Atenção
	Gramáticas livres de contexto
	Introdução
	Contexto
	BNF
	Exemplo
	Exemplo
	Exemplo
	Exemplos práticos
	Exemplo 1
	Exemplo 2
	Exemplo 3
	Gramáticas livres de contexto
	Conteúdo interativo
	Vem que eu te explico!
	Tipos de gramáticas
	Conteúdo interativo
	Exemplo 1 - Construção de uma GLC
	Conteúdo interativo
	Verificando o aprendizado
	2. Simplificação de gramáticas livres de contexto
	Remoção de símbolos não geradores
	Algoritmo para remoção
	Remoção de símbolos não geradores
	Remoção de símbolos inacessíveis ou não alcançáveis
	Encontre os símbolos não geradores
	Remova os símbolos não geradores
	Encontre os símbolos não alcançáveis
	Exemplo 1
	Exemplo 2
	Remoção de produções unitárias
	Produções unitárias
	Algoritmo para remoção
	Exemplo 1
	Exemplo 2
	Remoção de produções nulas
	Produção nula
	Atenção
	Algoritmo para remoção
	Passo I
	Passo II
	Passo III
	Exemplo 1
	Exemplo 2
	Simplificação de gramáticas livres de contexto
	Conteúdo interativo
	Vem que eu te explico!
	Remoção dos símbolos inúteis
	Conteúdo interativo
	Remoção das produções unitárias
	Conteúdo interativo
	Verificando o aprendizado
	3. Autômatos de pilha
	Conceitos fundamentais
	Autômatos finitos
	Atenção
	Diagrama mecânico de um autômato finito
	Comentário
	Conceito de pilha
	Comentário
	Pilha tipo stack
	Pilha pushdown
	Autômatos de pilha
	Definição de autômato de pilha
	Diagrama mecânico
	Fita de entrada
	Cabeça de leitura
	Controle finito
	Pilha
	Pushdown autômata
	Comentário
	Funcionamento dos autômatos de pilha
	Descrição instantânea
	Aceitação por pilha vazia
	Aceitação pelo estado final
	Exemplo prático
	Funcionamento dos autômatos de pilha
	Conteúdo interativo
	Vem que eu te explico!
	Autômatos finitos
	Conteúdo interativo
	Autômatos de pilha
	Conteúdo interativo
	Verificando o aprendizado
	4. Propriedades das linguagens livres de contexto
	Propriedades de fechamento
	Fechamento na união
	Atenção
	Fechamento na concatenação
	Fecho de Kleene
	Não fechamento na intersecção
	Não fechamento na complementação
	Toda linguagem regular é uma LLC
	Lema da altura da árvore de derivação
	Aplicação de estruturas em árvores
	Forma normal de Chomsky
	Lema da altura da árvore de derivação
	Lema do bombeamento
	Lema do bombeamento para LLC
	Atenção
	Exemplo prático
	Propriedades decidíveis
	Vaziez
	Finitude
	Exemplos práticos
	LLC e linguagem regular
	Aplicação de GLC
	Construção de GLC
	Propriedades de fechamento
	Conteúdo interativo
	Vem que eu te explico!
	Lema do bombeamento para LLC
	Conteúdo interativo
	Operações sobre LLC
	Conteúdo interativo
	Verificando o aprendizado
	5. Conclusão
	Considerações finais
	Podcast
	Conteúdo interativo
	Explore +
	Referências