Nome da Atividade
LINGUAGENS FORMAIS
CÓDIGO
22000197
Carga Horária
60 horas
Tipo de Atividade
DISCIPLINA
Periodicidade
Semestral
Unidade responsável
CRÉDITOS
4
CARGA HORÁRIA TEÓRICA
4
CARGA HORÁRIA OBRIGATÓRIA
4
FREQUÊNCIA APROVAÇÃO
75%
Ementa
Introdução a Teoria de Linguagens Formais. Hierarquia de Chomsky. Linguagens Regulares. Linguagens Livres de Contexto. Linguagens Sensíveis ao Contexto.
Objectives
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
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.
Turmas Ofertadas
Turma | Período | Vagas | Matriculados | Curso / Horários | Professores | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|
T1 | 2024 / 1 | 51 | 46 |
Ciência da Computação (Bacharelado) Horários
|
LUCIANA FOSS Professor responsável pela turma |
||||||
T2 | 2024 / 1 | 40 | 35 |
Ciência da Computação (Bacharelado) Engenharia de Computação (Bacharelado) Horários
|
LUCIANA FOSS Professor responsável pela turma |
Disciplinas Equivalentes
Disciplina | Curso |
---|---|
LINGUAGENS FORMAIS | Ciência da Computação (Bacharelado) |
LINGUAGENS FORMAIS | Engenharia de Computação (Bacharelado) |