Sumários

Máquinas de Turing

22 Novembro 2016, 10:30 Ana Respicio

Folha 7 - exercícios 1, 3, 4a, 4b, 5a, 6


Terminologia para descrever Máquinas de Turing. Decidibilidade.

22 Novembro 2016, 09:30 Ana Respicio

Terminologia para descrever Máquinas de Turing. Codificar objetos como strings. Exemplos. Codificação de um grafo.
O problema de determinar se um grafo não orientado é conexo é decidível. Prova.
Hierarquia de classes de linguagens.
Decidibilidade. Problemas decidíveis e linguagens decidíveis. 
A_AFD é decidível. Prova.


Autómatos de Pilha. Máquinas de Turing.

21 Novembro 2016, 08:00 Alexandre Miguel dos Santos Martins Pinto

Folha 7: exercícios 1a, b, c; 3, 4a, b; 5a; 6


Autómatos de Pilha. Máquinas de Turing.

18 Novembro 2016, 11:30 Alexandre Miguel dos Santos Martins Pinto

Folha 7: exercícios 1a, b, c; 3, 4a, b; 5a; 6


Autómatos de Pilha. Máquinas de Turing.

18 Novembro 2016, 08:00 Alexandre Miguel dos Santos Martins Pinto

Folha 7: exercícios 1a, b, c; 3, 4a, b; 5a; 6