Compiladores

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

9 - Hierarquia de Classes de

Linguagens e Conclusões

9.1 Hierarquia de Chomsky 9.2 Conclusões 9.3 Leitura Complementar: Gramática de Grafos

Linguagens Formais e Autômatos - P. Blauth Menezes

3

9 - Hierarquia de Classes de Linguagens e Conclusões
Linguagens Formais e Autômatos - P. Blauth Menezes

4

9 Hierarquia de Classes de Linguagens e Conclusões
9.1 Hierarquia de Chomsky
◆

Constituída pelas classes & inclusões próprias
• • • • Regulares ou Tipo 3 Livres do Contexto ou Tipo 2 Sensíveis ao Contexto ou Tipo 1 Recursivamente Enumeráveis ou Tipo 0

Linguagens Formais e Autômatos - P. Blauth Menezes

5

Linguagens Recursivamente Enumeráveis ou Tipo 0 Linguagens Sensíveis ao Contexto ou Tipo 1 Linguagens Livres do Contexto ou Tipo 2

Linguagens Regulares ou Tipo 3

◆

Noam Chomsky definiu estas classes como (potenciais) modelos para linguagens naturais
6

Linguagens Formais e Autômatos - P. Blauth Menezes

◆

Linguagens de programação
• nem sempre são tratadas adequadamente na Hierarquia de Chomsky

◆

Existem linguagens que não são livres do contexto para as quais
• poder dos formalismos sensíveis ao contexto é excessivo • inadequados principalmente no que se refere à complexidade

◆

Conhecimento das linguagens sensíveis ao contexto
•