Portal do Ementário

A disciplina Linguagens Formais e Autômatos visa dotar os acadêmicos de conhecimentos sobre as linguagens formais, sobre os mecanismos reconhecedores (autômatos) de cada tipo de linguagem e sobre os mecanismos geradores de cada tipo de linguagem (gramáticas). Ao final da disciplina, os alunos deverão ser capazes de identificar a classe a que uma linguagem pertence e suas principais propriedades decorrentes.

Gramáticas formais e autômatos. Gramáticas regulares. Gramáticas livres de contexto. Gramáticas sensíveis ao contexto. Tipos de reconhecedores. Operações com linguagens. Propriedades das linguagens. Autômatos finitos. Autômatos de pilha. Linguagens recursivas.

[1] Hopcroft, J. E.; Motwani, R.; Ullman, J. D.; Introdução à teoria de autômatos: linguagens e computação. 2ed, Ed. Campus, 2002. ISBN: 8535210725. [2] Lewis, H. R.; Papadimitriou, C.; Elementos de Teoria da computação. 2ed, Ed. Bookman, 2000. ISBN: 8573075341. [3] Vieira, N. J.; Introdução aos Fundamentos da Computação: Linguagens e Máquinas. Ed. Thomson, 2006. ISBN: 8522105081.

[1] Sipser, M.; Introdução à Teoria da Computação. Ed. Thomson, 2007. ISBN: 9878522104994. [2] Menezes, P. F. B.; Linguagens Formais e Autômatos. 4ed, Ed. Sagra Luzzatto, 2002. ISBN: 8524105542. [3] Linz, P.; An Introduction to Formal Language and Automata. 4ed, Ed. Jones & Bartlett, 2006. ISBN: 9780763737986.