Sumários

3 Dezembro 2018, 08:00 • André Souto

Resolução de exercícios da folha 8 e 9 sobre decidibilidade.

30 Novembro 2018, 11:30 • André Souto

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

30 Novembro 2018, 08:00 • André Souto

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

28 Novembro 2018, 09:30 • André Souto

Continuação da aula anterior sobre decidibilidade de linguagens.

Decidibilidade de linguagens livres de contexto:

-- Aceitação de uma string gerada por uma CFG;

-- Aceitação de uma string gerada por uma expressão regular;

-- Linguagem gerada por uma CFG ser vazia;

-- Qualquer linguagem livre de contexto é decidível.

Noção de indecidibilidade.

Noção de conjunto contável.

Exemplos de conjuntos contáveis.

A técnica de diagonalização.

Prova que o conjunto dos números reais e das partes dos números naturais não são contáveis.

Estudar as secções 4.1 e 4.2 do Sipser.

28 Novembro 2018, 08:00 • André Souto

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