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:

Introdução

Teoria de autômatos
Strings e linguagens
Gramáticas
Algoritmos
Linguagens formais
Hierarquia de chomsky

Linguagens Regulares

Autômatos finitos
Operações regulares
Linguagens finitas e linguagens regulares
Propriedades de fecho de linguagens regulares
Autômatos finitos não determinísticos
Expressões regulares
Equivalência entre AFDs, AFNs e REX
Minimização de AFs
Linguagens não regulares

Linguagens Livre de Contexto

Gramáticas livre de contexto
Gramáticas linear à direita
Forma Normal de Chomsky
Autômatos de pilha
Equivalências entre CFG e PDA
Linguagens não livres de contexto

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: 13/06/11
Avaliação 4 – Valor: 25,0 pontos – Data: 06/07/11
Avaliação Especial – Valor: 10,0 pontos – Data: 18/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: 13/06/11
Lista de exercício IV - Data de entrega: 06/07/11

Resultado Final

Material Didático:

Transparências de aula:

Apresentação da disciplina

Conceitos preliminares: Linguagem, Gramática
Linguagens Regulares: Autômato Finito Determinístico, Linguagens e Operações Regulares, Propriedades de Fecho, Minimização de AFD, Autômato Finito não Determinístico, Expressões regulares e equivalência com Autômatos Finitos, Lema do Bombeamento
Linguagens Livres de Contexto: Gramática Livre de Contexto e Linear a Direita, Automato com Pilha, Equivalência entre PDA e CFG, Linguagem não-livre-do-contexto

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: 19/07/11