Linguagens Formais e Autômatos

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, 2002.