1. Si ferma su tutti gli ingressi: Il TM deve eventualmente raggiungere uno stato di accettazione o uno stato di rifiuto, indipendentemente dalla stringa di input. Non può loop per sempre.
2. accetta stringhe nella lingua L: Se una stringa `w` è in l, la TM si ferma in uno stato di accettazione.
3. Rifiuta le stringhe non nella lingua L: Se una stringa `w` non è in L, la TM si ferma in uno stato di rifiuto.
In altre parole, un linguaggio decidabile ha una macchina Turing che funge da tester di abbonamento perfetto:dà sempre una risposta "sì" o "no" e lo fa sempre in un periodo di tempo finito.
Ecco una ripartizione delle tecniche e delle considerazioni comuni:
1. Costruire una macchina Turing (TM) Descrizione:
* Descrizione di alto livello: Inizia con una descrizione chiara e leggibile dall'uomo dell'algoritmo della TM. Questo dovrebbe spiegare la logica e i passaggi necessari per elaborare l'input. Pensalo come pseudo-codice.
* Descrizione a livello di implementazione (opzionale): * Puoi * fornire una descrizione di livello inferiore, specificando gli stati, la funzione di transizione, l'alfabeto a nastro, ecc. Questo è spesso noioso e non richiesto se non esplicitamente richiesto o se l'algoritmo è molto sottile e richiede una definizione precisa. Concentrati prima sulla descrizione di alto livello.
* La chiarezza è la chiave: La cosa più importante è che la tua descrizione sia comprensibile e convincente. Una descrizione di alto livello scarsamente scritta può essere più difficile da capire di una descrizione formale ben scritta.
2. Strategie generali per la progettazione di decidi:
* simula altre macchine: Se puoi dimostrare che L può essere deciso simulando un'altra lingua decidibile (o più lingue di questo tipo), hai dimostrato che L è decidabile. La decidibilità è chiusa sotto molte operazioni (unione, intersezione, complemento, concatenazione, stella di Kleene).
* Converti in un problema più semplice: Prova a riformulare il problema in un problema equivalente ma più facile da risolvere.
* Considera i casi di base e la ricorsione: Se il problema ha una struttura ricorsiva, un algoritmo ricorsivo può essere tradotto in un decisore della macchina Turing. Assicurarsi che la ricorsione sia limitata per garantire la risoluzione.
* Ricerca esaustiva: Se lo spazio di input è finito o può essere limitato, è spesso possibile utilizzare una ricerca esaustiva per verificare tutte le possibilità. Il punto cruciale è che la ricerca deve essere garantita per terminare.
* Leva LAGGI DECIDABILI LINGUE: Costruire la consapevolezza che alcune lingue sono già decidibili. Ad esempio, lingue regolari, lingue senza contesto e molti altri.
3. Tecniche per dimostrare la risoluzione:
* Conteggio: Mostra che l'algoritmo coinvolge un contatore che aumenta o diminuisce rigorosamente verso un limite.
* Dimensione decrescente: Mostra che ogni fase dell'algoritmo riduce le dimensioni del problema fino a raggiungere una base di base banale.
* Nessun loop infinito: Sostenere in modo convincente che l'algoritmo non può entrare in un ciclo infinito. Ciò potrebbe comportare la dimostrazione che la macchina muove sempre la testa a nastro o che gli stati visitati sono sempre distinti in un certo periodo.
* Lunghezza di simulazione: Se l'algoritmo simula un altro TM, stabilire un limite superiore sul numero di passaggi che la simulazione prenderà. Questo dipende spesso dalla dimensione dell'input.
4. Esempi e scenari comuni:
* Lingue regolari: Per mostrare una lingua normale è decidabile, fornire un DFA per la lingua. Un TM può simulare il DFA e fermarsi in uno stato di accettazione o rifiutare in base allo stato finale del DFA.
* Lingue senza contesto: Utilizzare l'algoritmo CYK o un algoritmo di analisi simile. Questi algoritmi hanno un runtime finito.
* Undecidabilità: Comprendi il problema di arresto. * Non può * decidere se una macchina arbitraria di Turing si interrompe su un input arbitrario. Se riesci a ridurre il problema di arresto al tuo problema, hai mostrato che il tuo problema è indecidibile (non decidibile).
* Test di vuoto: Mostrare un linguaggio è * vuoto * (non contiene stringhe) è talvolta più facile che mostrare che è decidabile. Ad esempio, il linguaggio di una macchina Turing non è * decidabile. Tuttavia, dato un DFA o CFG, determinare se la lingua che rappresenta è vuota * è * decidabile.
5. Cosa non fare:
* Non affermare solo che è decidabile senza giustificazione. È necessario fornire un argomento ragionevole, che di solito significa descrivere l'algoritmo.
* Non fornire un tm che * solo * accetta stringhe nella lingua. Deve anche * rifiutare * stringhe * non * nella lingua e deve fermarsi.
* Non fornire un algoritmo che * potrebbe * fermare ma ha il potenziale per loop per sempre. Un decisore * deve * fermare.
* Non confondere la decidibilità con la riconoscibilità. Un linguaggio riconoscibile richiede solo un TM per fermare e accettare se l'input è nella lingua. Può loop per sempre se l'input non è nella lingua. Le lingue decidabili sono sempre riconoscibili, ma il contrario non è vero.
* Non cercare di fornire una "prova per esempio". Mostrando che un input specifico è accettato o respinto non dimostra nulla sulla decidibilità della lingua.
Esempio 1:a ={0
n
1
* Descrizione di alto livello:
1. Scansionare la stringa di input per assicurarsi che consiste solo su 0s seguito da 1s. In caso contrario, rifiuta.
2. Mentre ci sono sia 0 e 1.
* Attraversare il più a sinistra 0.
* Attraversare la più a sinistra 1.
3. Se non rimangono 0s e no 1, accetta.
4. Se rimangono solo 0 o solo 1, rifiuta.
* Giustificazione: Questo algoritmo si ferma per tutti gli input. I passaggi 1 e 3/4 stanno terminando i controlli. Passaggio 2 Croce uno 0 e uno 1 in ogni iterazione. Il numero di 0 e 1 è finito, quindi il ciclo terminerà. Se il numero di 0 e 1s era uguale, accettiamo. Altrimenti, rifiutiamo.
Esempio 2:dato un dfa d, la sua lingua L (d) è vuota? A dfa ={
* Descrizione di alto livello:
1. Segna lo stato di inizio di D.
2. Ripeti fino a quando non vengono contrassegnati i nuovi stati:
* Contrassegna qualsiasi stato che può essere raggiunto da uno stato attualmente contrassegnato seguendo una freccia in D.
3. Se qualche stato di accettazione di D è contrassegnato, rifiuta.
4. Altrimenti, accetta.
* Giustificazione: Questo algoritmo si ferma. Il passaggio 2 esplora tutti i possibili stati raggiungibili. Il numero di stati in D è finito, quindi il ciclo terminerà. Se possiamo raggiungere uno stato accettante, la lingua non è vuota e rifiutiamo. Altrimenti, lo è e accettiamo. Si noti che `d` è garantito per essere un DFA per assunzione e quindi ha stati finiti.
Seguendo queste strategie e comprendendo le proprietà delle macchine Turing e delle lingue decidabili, è possibile dimostrare efficacemente che una lingua è decidibile. Ricorda di concentrarti su una descrizione chiara e convincente dell'algoritmo e su un solido argomento per la sua risoluzione e correttezza.
Programmazione © www.354353.com