Decidibilidade da linguagem
Uma linguagem é chamada Decidable ou Recursive se houver uma máquina de Turing que aceita e pára em cada string de entrada w. Cada linguagem decidível é Turing-Aceitável.
Um problema de decisão P é decidível se o idioma L de todas as instâncias sim para P é decidível.
Para uma linguagem decidível, para cada string de entrada, a TM para no estado de aceitação ou rejeição, conforme ilustrado no diagrama a seguir -
Exemplo 1
Descubra se o seguinte problema é decidível ou não -
É um número 'm' primo?
Solução
Números primos = {2, 3, 5, 7, 11, 13, ………… ..}
Divida o número ‘m’ por todos os números entre '2' e '√m' começando em '2'.
Se algum desses números produzir um resto zero, então ele vai para o “estado Rejeitado”, caso contrário, ele vai para o “estado Aceito”. Portanto, aqui a resposta pode ser 'Sim' ou 'Não'.
Hence, it is a decidable problem.
Exemplo 2
Com uma linguagem normal L e corda w, como podemos verificar se w ∈ L?
Solução
Pegue o DFA que aceita L e verifique se w é aceito
Alguns problemas mais decidíveis são -
- O DFA aceita o idioma vazio?
- É L 1 ∩ L 2 = ∅ para conjuntos regulares?
Note -
Se um idioma L é decidível, então seu complemento L' também é decidível
Se um idioma é decidível, então há um enumerador para ele.