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.

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,