linguagens

Cursos:

Bacharelado em Ciência da Computação e
Bacharelado em Sistemas de Informação
Disciplinas: (1493A) Teoria da Computação e Linguagens Formais,
(4623A) Teoria da Computação e Linguagens Formais e
(1601A) Teoria da Computação
Professora: Simone das Graças Domingues Prado [e-mail] e-mail: home-page: wwwp.fc.unesp.br/~simonedp/discipl.htm

Apostila 03
Assunto:

Linguagens Livres de Contexto

Objetivos:

⇒
⇒
⇒

Estudar as linguagens livres de contexto
Estudar as gramáticas livres de contexto
Estudar os autômatos com pilha

Conteúdo:
1.
2.
3.
4.
5.
6.
7.
8.

Introdução
Gramática Livre de Contexto
Árvore de derivação
Ambigüidade
Simplificação de GLC
Formas Normais
Autômato com pilha
Propriedades das Linguagens Livres de Contexto

_______________________________________________________________________________________________________________
Teoria da Computação e Linguagens Formais - Simone Domingues Prado – Apostila 03

-1-

1. Introdução
Foi visto na primeira apostila (TC01.pdf) a hierarquia de Chomsky (veja a figura 1). Na segunda
(TC02.pdf) foram tratadas as linguagens regulares que são as mais simples das linguagens, sendo possível desenvolver algoritmos de reconhecimento ou de geração de pouca complexidade, grande eficiência e de fácil implementação.

Figura 1. Hierarquia de Chomsky
As Linguagens Livres de Contextos compreendem uma abordagem mais ampla do que as Linguagens
Regulares tratando, de forma apropriada, as questões de balanceamentos entre parênteses e blocos de programas. Os seus algoritmos são simples e possuem uma boa eficiência.
Nessa Apostila serão abordadas as Linguagens Livres de Contexto a partir de dois formalismos:
• Operacional ou reconhecedor – uso dos autômatos com pilha (AP)
• Axiomático ou gerador – gramática livre de contexto (GLC)

2. Gramática Livre de Contexto
Definição 1.
Uma gramática G = (V, T, S, P) é dita ser uma Gramática Livre de Contexto (GLC) se