Ementa

Autômatos. Linguagens e expressões regulares. Gramáticas e Autômatos a Pilha. Máquina de Turing. Decidibilidade e Computabilidade; Complexidade Computacional.

Objetivos

Permitir ao aluno realizar exploração das linguagens formais e máquinas enquanto modelos abstratos da computação, de modo a compreender as relações existentes entre linguagens formais e computabilidade, conscientes que tais fundamentos persistem, independente das tecnologias vigentes associadas à computação. Conhecer os fundamentos da computação e perceber o limite do que pode ser computável, com isso, ser capaz de utilizar tais conceitos para solucionar problemas do mundo real, considerando aspectos de computabilidade.