Portal do Ementário

Discutir o conceito de máquinas de estados finitos. [Familiaridade] Criar expressões regulares enquanto formalismo denotacional para uma linguagem. [Uso] Criar máquinas abstratas (autômatos, Máquina de Moore, Máquina de Mealy) para a resolução de problemas de reconhecimento de linguagens. [Uso] Criar gramáticas para gerar linguagens. [Avaliação] Implementar algoritmos que representem as etapas léxica e sintática de um compilador. [Uso] Enquadrar elementos de linguagens formais na Hierarquia de Chomsky. [Familiaridade] Explicar por que o problema da parada não tem solução algorítmica. [Familiaridade]

Hierarquia de Chomsky. Linguagens regulares, livres de contexto, sensíveis ao contexto e enumeráveis recursivamente com seus respectivos teoremas e abstrações denotacionais (expressões regulares), geradoras (gramáticas) e reconhecedoras (máquinas de estado finito). Tese de Church. Máquinas de Turing. Decidibilidade. O problema da parada. Computabilidade.

MENEZES, Paulo Fernando Blauth. Linguagens formais e autômatos. 5 ed. Porto Alegre: Sagra Luzzatto, 2008. HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à teoria de autômatos, linguagens e computação. 2. ed. Rio de Janeiro: Elsevier, 2002. ROSA, João Luís Garcia. Linguagens formais e autômatos. Rio de Janeiro: LTC, 2010.

SUDKAMP, Thomas A. Languages and machines: an introduction to the theory of computer science. 2. ed. Massachusets: Addison-Wesley Publishing Company, Inc., 1997. GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação. 4a ed. Porto Alegre: Sagra Luzzatto, 2001. LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2a ed. Porto Alegre: Artmed, 2000. HOWIE, John M. Automata and languages. Oxford: Clarendon Press, 1991. 294 p. ISBN 0198534426 (enc.) VIEIRA, Newton José. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo: Pioneira Thomson Learning, 2006. xiii, 319 p. ISBN 9788522105083 (broch.)