1. Costruire una macchina Turing (o algoritmo):
Questo è l'approccio più diretto. Descrivi esplicitamente una macchina Turing (o un algoritmo di alto livello che può essere facilmente tradotto in una macchina Turing) che decide la lingua. Questa descrizione deve coprire:
* Input: Come la macchina Turing riceve la stringa di input.
* afferma: I diversi stati in cui la macchina può essere in.
* Transizioni: Come la macchina si sposta tra gli stati in base allo stato corrente e al simbolo letto dal nastro.
* Accettazione/rifiuto: In che modo la macchina segnala l'accettazione (ad es. Inserisci uno stato "accetta") o il rifiuto (ad esempio, inserendo uno stato "rifiuto").
* Harting: Fondamentalmente, è necessario dimostrare che la macchina * si ferma sempre, indipendentemente dal fatto che la stringa di input sia in L o meno. Questa è la parte più impegnativa.
Esempio: Considera la lingua l ={W | w è un palindrome}. Possiamo descrivere una macchina Turing che:
1. Scansiona il nastro di input da sinistra a destra, segnando il primo e l'ultimo simboli.
2. Sposta i marcatori un passo verso l'interno da entrambe le estremità.
3. Ripete il passaggio 2 fino a quando i marcatori non si incontrano (la stringa è un palindromo) o i marcatori si incrociano (la stringa non è un palindromo).
4. Accetta se i marcatori si incontrano e rifiuta se si incrociano.
Questa macchina si ferma sempre, dimostrando che L è decidabile.
2. Riduzione a un linguaggio decidabile noto:
Se puoi dimostrare che la tua lingua L può essere ridotta a una lingua decidabile nota L ', questo è anche decidabile. Una riduzione è una funzione calcolabile F tale che:
* x ∈ L se e solo se f (x) ∈ L '
Se hai un algoritmo per decidere l ', puoi usarlo per decidere l applicando prima la riduzione f. Poiché sia F che l'algoritmo per L 'sono calcolabili, il processo combinato è anche calcolabile, decidendo così L.
Esempio: Sia L il linguaggio delle stringhe che rappresentano espressioni aritmetiche valide. Possiamo ridurre L a una lingua grammaticale (CFG) senza contesto L 'che è decidabile (esistono algoritmi di analisi per i CFG). La riduzione implicherebbe la trasformazione della stringa di espressione aritmetica in un albero di analisi secondo la grammatica. Se la trasformazione ha successo e viene generata un albero di analisi valido, la stringa è in L; Altrimenti, non lo è.
3. Utilizzo delle proprietà di chiusura delle lingue decidabili:
Le lingue decidabili sono chiuse sotto determinate operazioni come Union, Intersection, Concatenation, Kleene Star e Complement. Se riesci a esprimere la tua lingua L usando queste operazioni su lingue decidabili note, anche L è decidabile.
Esempio: Se L1 e L2 sono decidabili, anche L1 ∪ L2 è decidabile. Puoi decidere L1 ∪ L2 eseguendo gli algoritmi di decisione per L1 e L2 sulla stringa di input; Se uno dei due accetta, l'Unione accetta.
In sintesi: La decidibilità di dimostrazione si riduce a dimostrare che esiste un algoritmo deterministico (o macchina Turing) che si fermerà sempre e classificherà correttamente ogni stringa di input come appartenente alla lingua o meno. Il metodo che scegli dipende dalla lingua specifica e dall'intuizione sulle sue proprietà. L'approccio più comune è la costruzione diretta di una macchina o algoritmo Turing, ma le riduzioni e le proprietà di chiusura sono strumenti potenti per linguaggi più complessi.
Programmazione © www.354353.com