Plano de ensino

Linguagens Formais e Autômatos

Bacharelado em Sistemas de Informação — 2020/1

Teoria dos autômatos é o estudo das máquinas abstratas ou autômatos, bem como problemas computacionais que podem ser resolvidos usando esses objetos.

Página da disciplina

Início
Encerramento
Local
Ifes, Campus Serra
Ambiente virtual
Acessar disciplina

Aviso Devido à pandemia de COVID-19, e seguindo as diretrizes do Ifes, esta disciplina será ministrada remotamente.

Plano de Ensino

  • Carga Horária: 60h
  • Aulas Previstas: 72

Objetivos

Objetivo Geral

Capacitar o aluno a aplicar os fundamentos teóricos de Linguagens, Gramáticas e Autômatos à solução de problemas e aplicações computacionais.

Objetivos Específicos

  1. Apresentar as linguagens formais, as máquinas de estado (autômatos) e as gramáticas principais da Hierarquia de Chomsky, mostrando o relacionamento existente entre cada tipo de linguagem, os autômatos que as reconhecem e as gramáticas que as geram.
  2. Evidenciar a linguagem reconhecida por um autômato como uma expressão de sua computabilidade e discutir os limites da computação convencional.
  3. Compreender as teorias de computabilidade e decidibilidade, que serão expostas com base no modelo das máquinas de Turing.
  4. Propiciar o desenvolvimento de um raciocínio lógico e formal, necessário também em outras sub-áreas da computação.

Ementa

Conjuntos, relações, funções e indução matemática. Hierarquia de Chomsky. Alfabetos e linguagens. Gramaticas. Autômatos finitos. Expressões regulares. Linguagens regulares, livres de contexto e sensíveis a contexto. Autômatos de pilha. Parsing. Maquinas de Turing. Decidibilidade, Computabilidade e Complexidade Computacional.

Bibliografia Básica

  1. Paulo Blauth Menezes. Linguagens Formais e Autômatos, 5ª ed. Sagra Luzzatto. Porto Alegre -- RS, 2005.
  2. Newton José Vieira. Introdução aos Fundamentos da Computação: Linguagens e Máquinas, 1ª ed. Cengage Learning. Rio de Janeiro -- RJ, 2006.

  3. John E. Hopcroft; Jeffrey D. Ullman; Rajeev Montwani. Introdução à Teoria de Autômatos, Linguagens e Computação, 1ª ed. Campus. Rio de Janeiro -- RJ,