Decidibilidade de linguagens
26 Novembro 2019, 09:30 • André Souto
Continuação da aula anterior: Decidibiliade da linguagem vazia em DFA e da igualdade entre linguagens de DFA.
Decidibilidade de linguagens baseadas em linguagens livres de contexto.
Introdução aos problemas indecidíveis.
O problema de aceitação em máquinas de Turing. Prova que é Turing-reconhecível.
Periplo para a demonstração que é indecidível.
Argumentos de diagonalização.
Noção de conjunto enumerável.