Sumários

25 Novembro 2019, 08:00 • André Souto

Continuação da resolução de exercícios sobre máquinas de Turing.

Resolução de um exercício prático para a avaliação contínua.

22 Novembro 2019, 11:30 • Andreia Mordido

Resolução de exercícios sobre conversão de uma CFG para PDA.

Resolução de exercícios sobre máquinas de Turing.

22 Novembro 2019, 08:00 • André Souto

Resolução de exercícios sobre conversão de uma CFG para PDA.

Resolução de exercícios sobre máquinas de Turing.

22 Novembro 2019, 08:00 • Andreia Mordido

Resolução de exercícios sobre conversão de uma CFG para PDA.

Resolução de exercícios sobre máquinas de Turing.

20 Novembro 2019, 09:30 • André Souto

Codificação de uma MT em string.

A máquina de Turing universal.

Recapitulação de linguagens Turing-reconhecíveis e Turing-decidíveis.

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.

(Nota: A aula foi dada pela Prof. Andreia Mordido por o docente estar em missão no estrangeiro devidamente autorizado).

Estudar a secção 4.1 do sipser.