camila

Linguagens Livres de Contexto e
Autômato com Pilha

Tópicos
• Estudo das linguagens livres de contexto.
• Estudo dos Autômatos com Pilha

Contextualização

PushDown Automata

Importância
• Compreende um universo mais amplo de linguagens.
• Trata adequadamente questões como parênteses balanceados, construções bloco-estruturadas. • Compreende a sintaxe da maioria das linguagens de propósitos gerais como
Pascal, C e Java.

Fonte:http://www.inf.puc-rio.br/~inf1626/docs/Notas-de-Aula.pdf

Considerações
• A classe das linguagens livres de contexto contém a classe das linguagens regulares. • Constitui uma classe de linguagens relativamente restrita, sendo fácil definir linguagens que não pertencem a esta classe. Formalismos abrangidos
• Gramática livre de contexto
– Restrições são definidas de maneira mais livre que na gramática regular.

• Autômato com pilha
– Estrutura básica análoga ao AFN, adicionada de uma memória auxiliar tipo pilha (a qual pode ser lida ou gravada).

Tópicos abrangidos
•
•
•
•

Árvore de derivação.
Gramática Ambígua.
Simplificação de Gramática.
Forma Normal.

Linguagens Livres do contexto
• Ou Tipo 2
• São definidas a partir das gramáticas livres do contexto.

Gramática Livre do Contexto
• Definição Formal
– Uma gramática livre do contexto G é uma gramática
G = (V, T, P, S)
– Restrição para as regras
A→
onde A é uma variável de V, e , uma palavra de (V ∪ T)*

Ou seja:
– Uma gramática livre do contexto é uma gramática na qual o lado esquerdo das produções contém exatamente uma variável.
– (Veja como era na última linguagem estudada, pág 100,
Menezes, novo)

O sentido do termo
“LIVRE DO CONTEXTO”
• Considere A → .
• A variável A deriva  sem depender (sendo
“livre”) de qualquer análise dos símbolos que antecedem ou sucedem A (o “contexto”) na palavra que está sendo derivada.

Exemplo 01
• Seja L = {anbn | n≥0}
• Problema: duplo balanceamento
• Seja