Sumários

20 Novembro 2018, 09:30 • André Souto

Variantes das máquinas de Truing:

- Stay.

- Multi-fita.

- Fita duplamente infiinta.

- Não deterministica.

Prova que todas são equivalentes ao modelo de fita simples e portanto reconhecem/decidem as mesmas linguagens.

Os enumeradores.

Prova de equivalência entre enumeradores e máquinas de Turing de fita simples.

Operações com linguagens decidíveis e com linguagens reconhecíveis.

Estudar secção 3.2 do Sipser.

19 Novembro 2018, 08:00 • André Souto

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

16 Novembro 2018, 11:30 • André Souto

Resolução de exercícios da folha nº6 sobre autómatos de pilha e gramáticas.

Exercício para avaliação contínua.

16 Novembro 2018, 08:00 • André Souto

Resolução de exercícios da folha nº6 sobre autómatos de pilha e gramáticas.

Exercício para avaliação contínua.

14 Novembro 2018, 09:30 • André Souto

Revisão da definição formal de Máquina de Turing e de computação.

Máquinas de Turing que terminam para qualquer input (máquinas de decisão).

Definição de linguagem Turing-reconhecível e Turing-decidível.

Exemplos de Máquinas de Turing para algumas linguagens e de configurações em máquinas de Turing.

Menção às variantes das máquinas de Turing:

Variante Stay

Variante Multi-fita

Variante de fita infinita para ambos os lados

Variante não determinista.

Estudar secções 3.1 e 3.2 do Sipser.