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.