MAC0414  Linguagens Formais e Autômatos

OBJETIVOS:  Estudo de vários formalismos que definem o conjunto das linguagens regulares e livres de contexto.

PROGRAMA:  Palavras, linguagens, operações sobre linguagens. Linguagens regulares. Autômatos finitos determinísticos e não determinísticos. Teorema de Kleene. Algoritmo polinomial para reconhecimento de padrões dados por expressões regulares. Autômatos reduzidos. Gramáticas livres de contexto e lineares. Teorema da iteração. Autômato a pilha. Gramáticas e análise sintática: ambigüidade, desambigüição de gramáticas; análise sintática descendente: gramática SLL(1), LL(k), LL(k)-forte; análise sintática ascendente: gramáticas de precedência, gramáticas LR(0), SLR(1), LR(k), LALR(k).

PRÉ-REQUISITOS:  MAT0213 ou MAC0122.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:  4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:  Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA: 

• H.R. Lewis, C.H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.
• J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Weley, 2000.
• A.V. Aho, R. Sethi, J.D. Ullman, Compilers, Principles, Techniques and Tools, Addison-Wesley, 1986.
• P.B. Menezes, Linguagens Formais e Autômatos, 3a ed., Sagra Luzzatto, Porto Alegre, 2000.

OBSERVAÇÃO:  Disciplina obrigatória no currículo do BCC. Corresponde aos capítulos 1 a 3 do livro de Lewis e Papadimitriou.

[Veja dados da disciplina no JúpiterWeb]