Nome da Atividade
LINGUAGENS FORMAIS
CÓDIGO
1110034
Carga Horária
68 horas
Tipo de Atividade
DISCIPLINA
Periodicidade
Semestral
Unidade responsável
CARGA HORÁRIA TEÓRICA
4
FREQUÊNCIA APROVAÇÃO
75%
CARGA HORÁRIA OBRIGATÓRIA
4
CRÉDITOS
4

Ementa

Introdução a Teoria de Linguagens Formais. Hierarquia de Chomsky. Linguagens Regulares. Linguagens Livres de Contexto. Linguagens Sensíveis ao Contexto.

Objetivos

Objetivo Geral:

Apresentar os conceitos formais de reconhecedores e geradores de linguagens.

Conteúdo Programático

1. Introdução a teoria de linguagens formais: alfabetos e linguagens
2. Gramáticas e hierarquia de Chomsky
3. Linguagens regulares
• Autômato finito determinístico
• Autômato finito não-determinístico
• Minimização de autômato finito
• Expressões regulares
• Conversões entre autômatos finitos, expressões regulares e gramáticas
• Lema do Bombeamento
4. Linguagens livres de contexto
• Gramática livre de contexto (GLC)
• Simplificações de GLC e formas normais
• Autômato de pilha
• Conversões entre GLC e autômato de pilha
5. Linguagens sensíveis ao contexto
• Gramática sensível ao contexto
• Autômato de fita limitada

Bibliografia

Bibliografia Básica:

  • HOPCROFT, John, ULLMAN, Jeffrey, MOTWANI, Rajeev. Introdução à teoria de automatos, linguagens e computação. Editora Elsevier, 2002.
  • TAYLOR, R. Gregory. Models of computation and formal languages. New York: Oxford University Press, 1998.
  • MENEZES, Paulo F. B. Linguagens formais e automatos. Editora Sagra Luzzatto, 1997.

Bibliografia Complementar:

  • LEWIS, Harry R., PAPADIMITRIOU, Christos. Elementos de teoria da computação. Editora Bookman, 2008.
  • AHO, Alfred V. Compiladores : princípios, técnicas e ferramentas. Editora LTC e Guanabara Koogan, 1995.
  • SIPSER, Michael. Introdução à teoria da computação. Editora Thompson, 2007.
  • RAMOS, Marcus V. M., NETO, João J., VEGA, I. Santiago. Linguagens formais: teoria, modelagem e implementação. Editora Bookman, 2009.
  • LINZ, Peter. An introduction to formal languages and automata. Massachusetts: Jones & Bartlett, 2006.

Página gerada em 18/03/2024 23:27:42 (consulta levou 0.108031s)