Sumários

Exercícios sobre PDA's e Máquinas de Turing

20 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.


Exercícios sobre PDAs e Máquinas de Turing

19 Novembro 2019, 11: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.


Exercícios sobre PDA's e Máquinas de Turing

19 Novembro 2019, 10:30 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.
A aula foi interrompida por simulacro.


Enumeradores e operações com linguagens decidíveis e Turing reconhecíveis.

19 Novembro 2019, 09:30 André Souto

Prova de como simular uma máquina de Turing multifita e não determinista numa máquina de Turing.

Noção de máquina enumeradora.
Prova que uma máquina enumeradora reconhece L se e só se L é Turing reconhecível.
O 10º problema de Hilbert e a tese de Church Turing.
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.


Exercícios sobre PDA's e Máquinas de Turing

18 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.