Decidibilidade de linguagens regulares
20 Novembro 2019, 09:30 • André Souto
Codificação de uma MT em string.
A máquina de Turing universal.
Recapitulação de linguagens Turing-reconhecíveis e Turing-decidíveis.
Definição de linguagem indecídível.
Exemplos de linguagens baseadas em autómatos e expressões regulares que são decidíveis: linguagem de aceitação, a linguagem vazia e igualdade.
(Nota: A aula foi dada pela Prof. Andreia Mordido por o docente estar em missão no estrangeiro devidamente autorizado).
Estudar a secção 4.1 do sipser.