Linguagens Formais e Autômatos

Sobre esta disciplina

Período: 5º Período · Núcleo: Profissionalizante · Carga Horária: 60h Tópicos: Linguagens regulares, livres de contexto e sensíveis ao contexto. Autômatos. Máquina de turing. Problema da parada.

Campo	Valor
Código	CSECBJI.40
Núcleo	Profissionalizante
Carga Horária	60
Período	5º Período
Pré-requisitos	CSECBJI.14 - Matemática Discreta

🔒 Trancas

• CSECBJI.48 - Compiladores

📋 Ementa

Linguagens regulares, livres de contexto e sensíveis ao contexto. Autômatos. Máquina de turing. Problema da parada. Noções de cálculo lambda e funções recursivas.

🎯 Objetivos

• Aprender a formalizar problemas computacionais através de linguagens formais, autômatos e máquina de Turing;
• Compreender o funcionamento de tais sistemas e modelos formais;
• Estudar e compreender conceitos de teoria da computação.

📖 Conteúdo Programático

1. Linguagens Regulares
2. Linguagens Livres de Contexto
3. Linguagens Sensíveis ao Contexto
4. Autômatos

• Autômato Finito
• Autômato Determinístico
• Autômato Não-Determinístico
• Autômato de Pilha

5. Máquina de Turing

• Definição do Modelo Computacional de Máquina de Estados e da Máquina de Turing
• Variações e Extensões da Máquina de Turing
• Aplicações da Máquina de Turing

6. Computabilidade
7. Noções de Cálculo-Lambda
8. Funções Recursivas

📕 Bibliografia Básica

1. DIVERIO, T. A., MENEZES, Paulo. B. Teoria da Computação: máquinas universais e computabilidade. 3ª Edição. Porto Alegre: Bookman. 2011.
2. GERSTING, J. L. Fundamentos Matemáticos para Ciência da Computação e suas Aplicações. 7ª Edição.
3. LTC, 2016.
4. ROSEN, Kenneth H. Matemática Discreta e suas Aplicações. 6ª Edição. São Paulo: McGraw-Hill Brasil.

📗 Bibliografia Complementar

1. HOPCROFT, J. E., ULLMAN, J. D., MOTWANI, R. Introdução à teoria de autômatos, linguagens e computação. 2ª Edição. Rio de Janeiro: Campus. 2003.
2. MENEZES, P. B. Linguagens Formais e Autômatos. 6ª Edição. Porto Alegre: Bookman. 2011.
3. PAPADIMITRIOU, C. H., LEWIS, H. R. Elementos da Teoria da Computação. 2ª Edição. Porto Alegre:
4. Bookman.
5. SIPSER, M. Introdução à Teoria da Computação. 2ª Edição. São Paulo: Thomson Learning. 2007.
6. VIEIRA, N. J. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo: Thomson,