Decidibilidade
23 Novembro 2022, 09:30 • Ana Respicio
Problemas decidíveis relacionados com linguagens regulares: problema de testar se uma expressão regular denota uma palavra, problema da aceitação de uma dada palavra por um autómato finito não determinista, problema da vacuidade da linguagem de um autómato finito determinista, e problema da equivalência entre dois autómatos finitos deterministas.
Problemas decidíveis relacionados com linguagens independentes do contexto: problema de determinar se uma gramática independente do contexto gera uma determinada palavra, problema de determinar se uma se uma gramática independente do contexto gera a linguagem vazia.
Sipser até Teorema 4.8 (inclusive e sem prova).