CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais
| Código: | CC0066 | ||||||||
| Componente Curricular: | Autômatos e Linguagens Formais | ||||||||
| Semestre de Oferta: | 5 | Tipo: | Disciplina | Caráter: | Obrigatória | ||||
| Unidade Acadêmica Responsável: | Centro de Ciências e Tecnologia - CCT | ||||||||
| Área: | Matemática | ||||||||
| Créditos: | 4 | Carga horária: | 64h | Teórica: | 64h | Prática | - | Extensão: | - |
| Pré-requisito: | Lógica para Ciência da Computação | ||||||||
| Co-requisito: | - | ||||||||
| Equivalência: | CC0028 | ||||||||
Objetivos
editarApresentar ao aluno os conceitos fundamentais de linguagem formais e Teoria dos Autômatos; familiarizar o aluno com os diferentes modelos de autômatos e gramáticas e o tratamento formal de tais formalismos; preparar o aluno para o posterior estudo sobre computabilidade, técnicas de construção de compiladores e processamento de linguagem natural; e refinar sua habilidade para tratar com conceitos formais abstratos.
Ementa
editarLinguagens Regulares e Livres de Contexto; Operações com linguagens; Propriedades das Linguagens; Lema do Bombeamento para linguagens regulares e para linguagens livres de contexto; Geradores de Linguagens: Expressões Regulares, Gramáticas Livres de Contexto; Reconhecedores: Autômatos Finitos Determinísticos, Autômatos Finitos Não Determinísticos, Autômatos de Pilha.
Conteúdo
editarAutômatos Finitos:
- Autômatos Finitos Determinísticos - AFDs
- Autômatos Finitos Não-determinísticos - AFNs
- Corretude de AFDs
Expressões Regulares:
- Operações Regulares e Expressões Regulares
- Corretude de Expressões Regulares
- Equivalência entre Autômatos Finitos e Expressões Regulares
Lema do Bombeamento das linguagens regulares:
- Lema do Bombeamento
Gramáticas livres-de-contexto:
- Gramáticas Livres-de-contextos - GLCs
- Corretude de GLCs
Autômatos com Pilha:
- Autômatos com Pilha - APs
- Equivalência entre GLCs e APs
Lema do Bombeamento das linguagens livres-de-contexto:
- Lema do Bombeamento das LLCs
Autômatos de pilha determinísticos:
- Autômatos de pilha determinísticos
Avaliação
editarO aluno será avaliado através de duas avaliações escritas e dois trabalhos. A média das avaliações progressivas do aluno será calculada através da média aritméticas ponderada das quatro avaliações, onde cada avaliação escrita tem peso 3,5 e cada trabalho tem peso 1,5.
Bibliografia Básica
editar- Sipser, M. Introdução à Teoria da Computação. 2ª edição traduzida. São Paulo: Cengage Learning, 2021.
Bibliografia Complementar
editar- Hopcroft, J. E., Ullman, D. J. e Motwani, R. Introdução à Teoria de Autômatos, Linguagens e Computação. 2ª edição. Rio de Janeiro: Editora Campus, 2003.