Para provar que um idioma L é decidível, você deve mostrar que existe uma máquina de Turing (ou um modelo computacional equivalente) que interrompe e aceita cordas em L e rejeita strings não em L. Existem várias maneiras de demonstrar isso:
1. Construindo uma máquina de Turing (ou algoritmo): Esta é a abordagem mais direta. Você descreve explicitamente uma máquina de Turing (ou um algoritmo de alto nível que pode ser facilmente traduzido em uma máquina de Turing) que decide o idioma. Esta descrição precisa cobrir:
*
Entrada: Como a máquina de Turing recebe a sequência de entrada.
*
Estados: Os diferentes estados que a máquina pode estar dentro.
*
Transições: Como a máquina se move entre os estados com base no estado atual e o símbolo lido da fita.
*
Aceitação/rejeição: Como a máquina sinaliza a aceitação (por exemplo, inserindo um estado de "aceitar") ou rejeição (por exemplo, inserir um estado de "rejeição").
*
interromper: Fundamentalmente, você deve demonstrar que a máquina * sempre é interrompida, independentemente de a sequência de entrada estar em L ou não. Esta é a parte mais desafiadora.
Exemplo: Considere o idioma l ={w | w é um palíndromo}. Podemos descrever uma máquina de Turing que:
1. Varredura a fita de entrada da esquerda para a direita, marcando o primeiro e o último símbolos.
2. Move os marcadores um passo para dentro de ambas as extremidades.
3. Repete a etapa 2 até que os marcadores se encontrem (a corda é um palíndromo) ou os marcadores cruzam (a corda não é um palíndromo).
4. Aceita se os marcadores se reúnem e rejeitam se eles cruzarem.
Esta máquina sempre pára, provando L é decidível.
2. Redução para uma linguagem decidível conhecida: Se você puder mostrar que seu idioma L pode ser reduzido a uma linguagem decidível conhecida L ', isso também é decidível. Uma redução é uma função computável para que:
* x ∈ L se e somente se f (x) ∈ L '
Se você tiver um algoritmo para decidir L ', poderá usá -lo para decidir l primeiro aplicando a redução f. Como o F e o algoritmo para L 'são computáveis, o processo combinado também é computável, decidindo L.
Exemplo: Seja l a linguagem das cordas que representam expressões aritméticas válidas. Podemos reduzir o L para uma linguagem gramatical livre de contexto (CFG) L 'que é decidível (existem algoritmos de análise para CFGs). A redução envolveria a transformação da corda de expressão aritmética em uma árvore de análise de acordo com a gramática. Se a transformação for bem -sucedida e uma árvore de análise válida for gerada, a string estará em L; Caso contrário, não é.
3. Usando propriedades de fechamento de idiomas decidíveis: Os idiomas decidíveis são fechados sob certas operações como união, interseção, concatenação, estrela de Kleene e complemento. Se você puder expressar seu idioma l usando essas operações em idiomas decidíveis conhecidos, também é decidível.
Exemplo: Se L1 e L2 forem decidíveis, L1 ∪ L2 também será decidível. Você pode decidir L1 ∪ L2 executando os algoritmos de decisão para L1 e L2 na sequência de entrada; Se um aceita, o sindicato aceita.
em resumo: Provar a decidabilidade se resume a mostrar que existe um algoritmo determinístico (ou máquina de Turing) que sempre interrompe e classifica corretamente todas as cadeias de entrada como pertencentes ao idioma ou não. O método que você escolher depende do idioma específico e de sua intuição sobre suas propriedades. A abordagem mais comum está construindo diretamente uma máquina ou algoritmo de Turing, mas as propriedades de redução e fechamento são ferramentas poderosas para idiomas mais complexos.
