Linguagens Formais – MAB703

Ementa:

1 – Alfabetos e Linguagens. Operações sobre Linguagens
2 – Linguagens Regulares. Autômatos Finitos Determinísticos e Não-Determinísticos. Expressões Regulares e Gramáticas Regulares. Propriedades de Fechamento das Linguagens Regulares
3 – Linguagens Não-Regulares. Lema do Bombeamento para Linguagens Regulares.
4 – Linguagens Livres de Contexto. Autômatos de Pilha Determinísticos e Não-Determinísticos. Gramáticas Livres de Contexto. Propriedades de Fechamento das Linguagens Livres de Contexto.
5 – Linguagens Sensíveis a Contexto. Lema do Bombeamento para Linguagens Livres de Contexto.
6 – Modelos Formais de Computação. Máquinas de Turing Determinísticas e Não-Determinísticas. Funções Recursivas. Linguagens Recursivas e Recursivamente Enumeráveis. Propriedades de Fechamento das Linguagens Recursivas e
Recursivamente Enumeráveis.
7 – Máquina de Turing Universal. Tese de Church-Turing.

Bibliografia:

1 – “Elementos de Teoria da Computação” – Harry R. Lewis e Christos H. Papadimitriou – 2a Edição – Ed. Bookman
2 – “Introdução à Teoria de Autômatos, Linguagens e Computação” – John E. Hopcroft, Jeffrey D. Ullman e Rajeev
Motwani – Ed. Campus Elsevier 3 – “Introdução a Teoria da Computação” – Michael Sipser – Ed. Thomson Pioneira
4 – “Automata and Formal Languages: An Introduction” – Dean Kelley – Ed. Prentice-Hall 5 – “Computability,
Complexity and Languages” – Martin D. Davis, Ron Sigal e Elaine J. Weyuker – 2a Edição – Ed. Morgan Kaufmann