Linguagens Formais e Autômatos

📌 Informações Gerais da Disciplina

• Código: CSECBJI.40
• Período: 5º Período | Núcleo: Profissionalizante | Carga Horária: 60
• Docente Responsável: Fabrício Barros (fabricio.goncalves@iff.edu.br)
• Livro / Material Didático Principal: Elementos de Eletrônica Digital (Capuano & Idoeta)

📋 Ementa e Objetivos Pedagógicos

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

🔒 Pré-requisitos e Dependências Curriculares (Trancas)

📋 Pré-requisitos Exigidos:

• CSECBJI.14 - Matemática Discreta

🔓 Disciplinas Trancadas (Liberadas após conclusão):

• CSECBJI.48 - Compiladores

📖 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 e Complementar (ABNT)

📕 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,

📝 Anotações e Arquivos Didáticos

• 📁 Acessar Repositório Dinâmico de Anotações da Disciplina