Máquinas de Turing I

9 março 2011, 14:00 • José Félix Costa

Máquinas de Turing.

Exercícios.

Nota 1: Esta foi uma aula prática de recapitulação do assunto supramencionado.

Nota 2: Máquina de Turing em LEGO.

Nota 3: Para avalição do estado de conhecimentos, vejam se conseguem ler o seguinte documento: Laplace's Daemon.

Exercícios (TPC): Indique máquinas de Turing que decidam as linguagens: (a) palavras da forma 1^n 0 1^n, (b) palavras sobre o singleton {1}, cujo tamanho é uma potência de 2, (c) palavras da forma w#w, onde w é uma palavra binária.

Férias de Carnaval

8 março 2011, 10:00 • José Félix Costa

Nesta data os alunos encontravam-se de férias.

Férias de Carnaval

7 março 2011, 10:00 • José Félix Costa

Nesta data os alunos encontravam-se de férias.

Autómatos e gramáticas II

2 março 2011, 14:00 • José Félix Costa

Exercícios sobre autómatos finitos, autómatos de pilha, gramáticas regulares e gramáticas livres de contexto.

Nota 1: Com esta aula concluímos a PARTE I da matéria.

Nota 2: Para estudar máquinas de Turing, poderão ainda recorrer ao livro de Michael Sipser (Parte II), embora a referência bibliográfica para as aulas que se seguem seja outra que, oportunamente, vos indicarei.

Autómatos infinitos V

1 março 2011, 10:00 • José Félix Costa

Autómatos de (uma) pilha. Definição, critério de aceitação, exemplos.

Teorema: Uma linguagem é livre de contexto se e só se existe um autómato de pilha que a reconhece.^1

Breve introdução às máquinas de Turing.

Hierarquia de Chomsky.

-------------------------------------

1. Note-se que diversos autores definem linguagem livre de contexto como aquela que é reconhecida por autómato de pilha. No nosso conceito, uma linguagem é livre de contexto quando é gerada por gramática livre de contexto.