Linguagens Formais e Autômatos | Anderson Almeida Ferreira

Universidade Federal de Ouro Preto – UFOP

Instituto de Ciências Exatas e Biológicas – ICEB

Departamento de Computação – DECOM

Disciplina: Linguagens Formais e Autômatos – BCC242 – 1/2011

Turma: 11

Prof. Anderson Almeida Ferreira

Objetivo:

Ao final do curso é esperado que os alunos compreendam as definições e propriedades de modelos matemáticos de computação, tais como, linguagens, autômatos e gramáticas.

Ementa:

Gramáticas. Linguagens Regulares, Livres-de-Contexto e Sensíveis-ao-Contexto. Tipos de Reconhecedores. Operações com Linguagens. Propriedades das Linguagens. Autômatos de Estados Finitos Determinístico e não Deterministico. Autômatos de Pilha. Máquina de Turing. Hierarquia de Chomsky.

Conteúdo Programático:

Conceitos Preliminares

Linguagens Formais
Gramáticas
Problemas de Decisão

Máquinas de Estados Finitos

Autômatos Finitos Determinísticos
Algumas propriedades dos AFDs
Minimizaçãao de AFDs
Autômatos Finitos Não Determinísticos
Equivalência entre AFDs e AFNs
Linguagens Regulares
O lema do bombeamento
Propriedades de fechamento
Expressões Regulares
Gramáticas Regulares

Autômatos de Pilha

Gramáticas Livres do Contexto

Definição
Derivações e ambigüidade
Manipulação de gramáticas e formas normais

Autômatos de Pilha Determinísticos
Autômatos de Pilha Não Determinísticos
GLCs e autômatos de pilha
Propriedades das Linguagens Livres do Contexto

Máquinas de Turing
Hierarquia de Chomsky

Processo Avaliativo:

04 avaliações teóricas:

Avaliação 1 – Valor: 20,0 pontos – Data: 20/04/11
Avaliação 2 – Valor: 20,0 pontos – Data: 18/05/11
Avaliação 3 – Valor: 25,0 pontos – Data: 06/06/11
Avaliação 4 – Valor: 25,0 pontos – Data: 04/07/11

Listas de exercícios:

Lista de exercício I Data de entrega: 20/04/11
Lista de exercício II Data de entrega: 18/05/11
Lista de exercício III - Data de entrega: 06/06/11
Lista de exercício IV - Data de entrega: 04/07/11

Material Didático:

Transparências de aula:

Apresentação da disciplina

Conceitos preliminares: Linguagem, Gramática
Autômato Finito Determinístico: Autômato Finito Determinístico, Linguagens e Operações Regulares, Propriedades de Fecho, Minimização de AFD
Autômato Finito não Determinístico: Autômato Finito não Determinístico

Ferramentas

JFlap

Bibliografia:

M. SIPSER, Introduction to the Theory of Computation, PWS Publishing Company, 1996.
N. J. VIEIRA, Introdução aos Fundamentos da Computação, Pioneira Thomson Learning, 2006.
T. A. SUDKAMP, Languages and machines: an introduction to the theory of computer science, Pearson Education, 2006.
J. E. HOPCROFT, R. MOTWANI, J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, 3/e, Pearson Education, 2006.
Daniel I. A. Cohen, Introduction to Computer theory, Willey, 1997.

Última Atualização: 20/04/11