Programa Resumido Elementos de linguagens formais, cadeias, alfabetos, linguagens, gramáticas e reconhecedores. Hierarquia de Chomsky. Expressões regulares, Autômatos finitos. Autômatos de pilha, Gramáticas livres de contexto. Relação entre autômatos e linguagens. Máquinas de Turing. Computabilidade. Complexidade computacional. Decidibilidade. Aplicações dos elementos da teoria à Engenharia de Computação.

• Docente: Ricardo Luis de Azevedo da Rocha