Ementa

Linguagens formais (regulares, livres de contexto, sensíveis ao contexto, com estrutura de frase). Gramáticas. A hierarquia de Chomsky. Autômatos finitos determinísticos e não determinísticos. Autômatos com pilha. Máquinas de Turing (o problema da parada, tese de ChurchTuring), Modelos de computação equivalentes à máquina de Turing. Proposições sobre computabilidade. Conceitos básicos de classes de complexidade de linguagens.

Objetivos

Proporcionar aos alunos conhecimentos teóricos e práticos de Linguagens Formais e elementos de Teoria da Computação, bem como de suas aplicações em Ciência da Computação. Mostrar os formalismos envolvidos nas etapas de análise léxica e sintática de linguagens, bem como os fundamentos teóricos do processo de computação e suas limitações.