Sumários

Aula Teórica 13

9 novembro 2010, 10:00 • Maria Paula Antunes Abrantes Gouveia

Configuração de máquina de Turing, configurações inicial, de aceitação, de rejeição  e de paragem. Classificador. Linguagem reconhecida por máquina de Turing e linguagem decidida por máquina de Turing. Linguagem decidível. Máquina de Turing como calculadora de funções. Exemplo: máquina de Turing quecalcula a função que a cada palavra binária faz corresponder a sua negação (exercício 2.9 a) da lista de exercícios para a aula prática 9 ).

Aula Teórica 13

9 novembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia

Exemplo: máquina de Turing que decide a linguagem w2w  onde w é uma palavra binária (exercício 2.4 a) da lista de exercícios para a aula prática 9). Configuração de máquina de Tiring, configurações inicial, de aceitação, de rejeição  e de paragem. Classificador. Linguagem reconhecida por máquina de Turing e linguagem decidida por máquina de Turing. Linguagem decidível. Máquina de Turing como calculadora de funções. Exemplo: máquina de Turing que calcula a função que a cada palavra binária faz corresponder a sua negação (exercício 2.9 a) da lista de exercícios para a aula prática 9 ).

Aula Prática 8

9 novembro 2010, 08:30 • Manuel Biscaia Martins

Exercicios 2.5 a) c) e 2.6 da  lista de exercícios para a aula prática 7. Exercícios 1.1  a) c) e 1.2 da  lista de exercícios para a aula prática 8.

Aula Prática 7

5 novembro 2010, 12:00 • Manuel Biscaia Martins

Exercício 3.2a) da  lista de exercícios para a aula prática 6. Exercícios 1.1 a) b), 2.3 d), 2.4 c) d) e) f) da  lista de exercícios para a aula prática 7.

Aula Teórica 12

4 novembro 2010, 12:00 • Maria Paula Antunes Abrantes Gouveia

Exemplos de linguagens que não são livres de contexto.  Breve referência ao lema da bombagem para linguagens livres de contexto. Máquina de Turing: definição algébrica. Noção informal de aceitação de palavra por máquina de Turing. Exemplo: máquina de Turing que reconhece a linguagem 00^*.