CC218: Modelos de Computação

(2013/2014)
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


Caracterização


Objectivos

Ensinar conceitos e resultados fundamentais sobre três modelos de computação básicos (autómatos finitos, autómatos de pilha e máquinas de Turing) e sobre as classes de linguagens formais associadas, com foco nas linguagens regulares e independentes de contexto.

Resultados de aprendizagem e competências: Capacidade de especificar linguagens formais simples usando formas de descrição alternativas e capacidade de determinar a sua classificação na hierarquia de poder computacional.

Programa

Noção de linguagem formal. Autómatos finitos determinísticos e não determinísticos. Expressões regulares e autómatos finitos. Propriedades das linguagens regulares. Minimização de autómatos finitos. Lema da repetição para linguagens regulares. Linguagens e gramáticas independentes de contexto. Árvores de derivação. Ambiguidade. Simplificações de gramáticas independentes de contexto e formas normais. Autómatos de pilha. Propriedades das linguagens independentes de contexto (LIC). Lema da repetição para LICs. Máquinas de Turing e noção de computabilidade.


Avaliação


Aulas


Bibliografia e Apontamentos


Ana Paula Tomás, Departamento de Ciência de Computadores, FCUP, Universidade do Porto, 2014