Indecidibilidade

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.