Definição de linguagem indecídível.

Exemplos de linguagens baseadas em autómatos e expressões regulares que são decidíveis: linguagem de aceitação, a linguagem vazia e igualdade.

Estudar a secção 4.1 do sipser.

A aula foi dada em regime síncrono não presencial com transmissão via Zoom. 

Noção de algoritmo e descrição de alto nível de uma máquina de Turing.

Noção de codificação para inputs de máquinas de Turing.

Exemplos de codificação em grafos e máquina que decide a linguagem dos grafos conexos.

Estudar a secção 3.2 e 3.1 do Sipser.

Aula em regime não presencial síncrono e trasmitida via Zoom.