Institutional PortalUFPEL

Objetivo Geral:

Apresentar os conceitos formais de reconhecedores e geradores de linguagens.

1. Introdução a teoria de linguagens formais: alfabetos e linguagens
2. Gramáticas e hierarquia de Chomsky
3. Linguagens regulares
• Autômato finito determinístico
• Autômato finito não-determinístico
• Minimização de autômato finito
• Expressões regulares
• Conversões entre autômatos finitos, expressões regulares e gramáticas
• Lema do Bombeamento
4. Linguagens livres de contexto
• Gramática livre de contexto (GLC)
• Simplificações de GLC e formas normais
• Autômato de pilha
• Conversões entre GLC e autômato de pilha
5. Linguagens sensíveis ao contexto
• Gramática sensível ao contexto
• Autômato de fita limitada

Bibliografia Básica:

• HOPCROFT, John, ULLMAN, Jeffrey, MOTWANI, Rajeev. Introdução à teoria de automatos, linguagens e computação. Editora Elsevier, 2002.
• TAYLOR, R. Gregory. Models of computation and formal languages. New York: Oxford University Press, 1998
• MENEZES, Paulo F. B. Linguagens formais e automatos. Editora Sagra Luzzatto, 1997.

Bibliografia Complementar:

• LEWIS, Harry R., PAPADIMITRIOU, Christos. Elementos de teoria da computação. Editora Bookman, 2008.
• AHO, Alfred V. Compiladores : princípios, técnicas e ferramentas. Editora LTC e Guanabara Koogan, 1995.
• SIPSER, Michael. Introdução à teoria da computação. Editora Thompson, 2007.
• RAMOS, Marcus V. M., NETO, João J., VEGA, I. Santiago. Linguagens formais: teoria, modelagem e implementação. Editora Bookman, 2009.
• LINZ, Peter. An introduction to formal languages and automata. Massachusetts: Jones & Bartlett, 2006.