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: 

• A. Salomaa, Theory of Automata, Pergamon, London, 1969.
• H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1981.

OBSERVAÇÃO:  Disciplina obrigatória no currículo do BCC.

[Veja dados da disciplina no JúpiterWeb]