LLC

Linguagens Formais e
Autômatos
P. Blauth Menezes [e-mail] Departamento de Informática Teórica
Instituto de Informática / UFRGS

Linguagens Formais e Autômatos - P. Blauth Menezes

1

Linguagens Formais e Autômatos
P. Blauth Menezes
1
2
3
4
5
6
7
8
9

Introdução e Conceitos Básicos
Linguagens e Gramáticas
Linguagens Regulares
Propriedades das Linguagens Regulares
Autômato Finito com Saída
Linguagens Livres do Contexto
Propriedades e Reconhecimento das Linguagens
Livres do Contexto
Linguagens Recursivamente Enumeráveis e
Sensíveis ao Contexto
Hierarquia de Classes e Linguagens e Conclusões

Linguagens Formais e Autômatos - P. Blauth Menezes

2

6 – Linguagens Livres do Contexto
6.1
6.2
6.3
6.4
6.5
6.6
6.7

Gramática Livre do Contexto
Árvore de Derivação
Gramática Livre do Contexto Ambígua
Simplificação de Gramática Livre do Contexto
Formas Normais
Recursão à Esquerda
Autômato com Pilha

Linguagens Formais e Autômatos - P. Blauth Menezes

3

6 – Linguagens Livres do Contexto

Linguagens Formais e Autômatos - P. Blauth Menezes

4

6 Linguagens Livres do Contexto
◆

Estudo da Classe das Linguagens Livres do Contexto ou Tipo 2 é de fundamental importância
• universo mais amplo de linguagens comparativamente com as LR
• trata, adequadamente, questões típicas de linguagens de programação ∗ parênteses balanceados
∗ construções bloco-estruturadas, etc.

◆

Algoritmos reconhecedores e geradores
• relativamente simples
• eficiência razoável

Linguagens Formais e Autômatos - P. Blauth Menezes

5

◆

Aplicações típicas
• centradas em linguagens artificiais
∗ em especial, nas linguagens de programação
• analisadores sintáticos
• tradutores de linguagens
• processadores de texto em geral

◆

Hierarquia de Chomsky
• Classe das Linguagens Livres do Contexto
• contém propriamente a Classe das Linguagens Regulares

◆

Entretanto, é uma classe relativamente restrita
• fácil definir linguagens que não pertencem a esta classe

Linguagens Formais e Autômatos - P. Blauth