Noção de indecidibilidade e problemas decidíveis sobre linguagens regulares e livres de contexto

23 Novembro 2021, 09:30 André Souto

Recapitulação de linguagens Turing-reconhecíveis e Turing-decidíveis.

Definição de linguagem indecídível. 

Linguagens de aceitação A_, de reconhecimento da linguagem vazia E_ e de igualdade de linguagens reconhecidas EQ_.

Decidibilidade de linguagens baseadas em autómatos e expressões regulares.

Decidibilidade de linguagens baseadas em gramáticas livres de contexto.

Estudar a secção 4.1 do sipser.