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:	CC0064 - Lógica para Ciência da Computação
Co-requisito:	-
Equivalência:	CC0028

Objetivos

Apresentar 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

Linguagens 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

Autô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

Linguagens não-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

O 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

1. Sipser, M. Introdução à Teoria da Computação. 2ª edição traduzida. São Paulo: Cengage Learning, 2021.

Bibliografia Complementar

1. 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.