Una quadrupla (V, $\sum$, R, S) dove:
Prima si costruisce il DFA per il linguaggio regolare, poi lo si trasforma in CFG.
| Grammatiche possono generare stessa stringa in modi diversi, sono dette ambigue. Se linguaggi possono essere generati solo così, sono detti inerentemente ambigui. Es: aibjck | i = j oppure j = k |
Se ogni regola della grammatica è della forma:
Per ottenerla:
| A -> $\epsilon$ fa diventare S -> ASA | aB in S -> ASA | aB | SA | AS | S |
Sono potenti automi che hanno a disposizione una pilla pushdown per contenere quantità non limitata di dati. Tra deterministici e non deterministici c’è differenza computazionale.
Automi a pila non deterministici sono computazionalmente equivalenti alle grammatiche context-free.
Una sestupla (Q, $\sum$, $\Gamma$, $\delta$, q0, F) dove:
Nel diagramma di stato si scrive a,b -> c che vuol dire
Se a è vuoto, può leggere e scrivere sulla pila senza input Se b è vuoto, può scrivere senza togliere dalla pila Se c è vuoto, può togliere dalla pila senza scrivere
Un linguaggio è context-free se e solo se esiste un automa a pila che lo riconosce.
Se un linguaggio è context-free, allora esiste un automa a pila che lo riconosce.
Convertiamo da una CFG G a un PDA P
Dobbiamo realizzare una pila che dato un input, riuscirà a generarlo. Alla fine li confronteremo e accetteremo se uguali. Per farlo lavoreremo sulle stringhe intermedie generate ad ogni derivazione. Quindi distinguiamo il comportamento in base a se troviamo una variabile o un terminale sulla cima della pila.
1) Inserisce simbolo marcato $ e la prima variabile nella pila 2) Se sulla cima della pila c’è A, scegli non deterministicamente una regola per A e sostituisce con la parte destra di A 3) Se sulla cima della pila c’è terminale a, legge l’input e lo confronta. Se sono uguali, ripete. Se sono diversi, rifiuta su questo ramo 4) Se sulla cima c’è il simbolo $, entra nello stato accettante. L’input è stato completamente letto 5) Ripete dal punto 2
Nuova notazione (r, u) $\in$ $\delta$(q, a, s) Siamo nello stato q, leggiamo a dal input, s è nella cima della pila. Andremo allo stato r e nella pila sostituiremo s con u.
Nel diagramma del PDA avremo stato qstart con inserimento di $. Lettura variabile iniziale. Stato qloop con le regole per i terminali e sostituzione parte destra per le variabili. Stato qaccept quando leggo il $ dalla pila e sono quindi vuoto. ___
Se un linguaggio è riconosciuto da un automa a pila, allora è context-free.
Convertiamo da PDA a CFG
G dovrebbe generare una stringa, se quella stringa fa andare P da uno stato iniziale ad accettante.
Ideare una variabile Apq che porta la pila da p a q, nello stesso stato.
Il PDA sarà
Ogni linguaggio regolare è context-free. Questo perché un linguaggio regolare è riconosciuto da un automa finito. Quest’ultimo è un automa a pila che ignora la sua pila.
Se A è linguaggio context-free, allora esiste un numero p tale che, se s è una stringa in A di lunghezza almeno p, può essere divisa in cinque parti s = uvxyz:
1) per ogni i >= 0, uvixyiz $\in$ A 2) |vy| > 0 3) |vxy| <= p
Alcuni linguaggi non context-free:
| anbncn | n >= 0 -> pumping up |
| aibjck | 0 <= i <= j <= k -> pumping up e pumping down |
| ww | w $\in$ {0, 1}* -> usando 0p1p0p1p |
Simile ad un automa, memoria illimitata.
Una setupla (Q, $\sum$, $\Gamma$, $\delta$, q0, qaccept, qreject) dove:
La configurazione è lo stato della macchina durante la computazione, composto dalla posizione della testina e della situazione del nastro.
La configurazione C1 produce la configurazione C2 se la MdT passa tra le due in un unico passo.
Un linguaggio è Turing-riconoscibile se esiste una MdT che lo riconosce.
L’insieme delle stringhe che M accetta rappresenta il linguaggio riconosciuto da M.
Una stringa è accettata se produce una serie di configurazioni che terminano in uno stato di accettazione.
Le MdT che si fermano su ogni input sono dette decisori, in quanto decidono se accettare o rifiutare, non ciclano mai. Un decisore decide un linguaggio se riconosce tale linguaggio.
Un linguaggio è Turing-decidibile se esiste una MdT che lo decide.
Ogni linguaggio decidibile è Turing-riconoscibile.
Descrizione di come si muove la testina, dei controlli che fa sullo stato che è ed eventuali sostituzioni.
Sono delle varianti che non vanno però a modificare la classe di linguaggi riconosciuti o aumentare il potere computazionale.
Inizialmente solo nastro 1 ha input, gli altri vuoti. Ogni testina è su un nastro.
Ogni macchina multinastro ha una MdT a nastro singolo equivalente.
Lo si fa usando il simbolo # per delimitare l’inizio e la fine dei nastri, inoltre si aggiunge il simbolo puntato per identificare la testina virtuale dei vari nastri.
Avrà una funzione di transizione
Qx$\Gamma$ -> P(Qx$\Gamma$x{L, R})
Ogni macchina di Turing non deterministica ha una MdT deterministica equivalente.
Si esegue un approccio di ricerca ad albero in ampiezza. La MdT D avrà 3 nastri con input, copia di N, stato di D rispetto all’esplorazione su N.
Quindi il nastro 3 avrà la scelta successiva del passo. Se vuota o non valida, resetta con la stringa successiva del cammino.
Questo per evitare loop su un cammino infinito.
N può diventare un decisore se si fermasse su ogni input di ogni ramificazione.
Ha una stampante collegata, che genera un output delle stringhe che compongono il linguaggio.
La TM esegue l’input e lo confronta con E. Se appare, accetta.
E invece ignora l’input ed esegue M su ogni stringa. Se M accetta, E stampa la stringa.
Il decimo è verificare con un algoritmo se un polinomio ha una radice intera.
Riuscire a dimostrare l’esistenza o meno di un algoritmo, avendo però definito formalmente cos’è un algoritmo.
La tesi di Church-Turing dimostra il collegamento tra una nozione intuitiva e una definizione formale, di algoritmo.
Noi proviamo a verificare se è Turing-riconoscibile cercando una radice su un polinomio a singola variabile. Esso può diventare decidibile definendo poi i limiti entro il quale deve terminare. Questo modo però per trovare i limiti non è applicabile nel caso di più variabili. Ecco perché l’algoritmo del problema non esiste.
Descriviamo l’input della macchina, che è spesso una stringa o trasformato in tale. Verifichiamo in caso che sia nella forma corretta.
Problema dell’accettazione per DFA.
ADFA è il linguaggio per indicare se un automa finito deterministico accetta una data stringa.
Esso è decidibile. Quindi verificare il linguaggio è equivalente a verificare la decibilità del problema computazionale.
M decide ADFA:
1) Su input <B, w> dove B è un DFA e w è una stringa 2) Simula B su w 3) Se la simulazione termina in uno stato di accettazione, accetta. Se non termina in uno stato di accettazione, rifiuta.
Trasformiamo l’NFA in un DFA equivalente C. Eseguiamo C su M. Accetta, se accetta. Altrimenti rifiuta.
Converte in un NFA equivalente. Esegue su N. Accetta, se accetta. Altrimenti rifiuta.
| Test del vuoto. {<A> | A è un DFA e L(A) = $\varnothing$} |
1) Marca stato iniziale di A 2) Ripete finché non sono marcati nuovi stati: 3) Marca uno stato che ha una transizione proveniente da uno stato già marcato 4) Se nessuno stato di accettazione è marcato, accetta. Altrimenti rifiuta.
Costruiamo linguaggio L(C) = (L(A) interseca $\overline{L(B)}$ ) U ($\overline{L(A)}$ interseca L(B))
Solo stringhe riconosciute da A o da B, differenza simmetrica.
Se L(C) è vuoto allora L(A) e L(B) sono uguali.
1) Costruiamo DFA C 2) Eseguiamo TM di E su input C 3) Accetta, se accetta. Altrimenti rifiuta.
Per essere sicuri sia un decisore trasformiamo nella forma di Chomsky, così avremo al massimo 2n-1 passi dove n è la lunghezza di w. TM S
1) Convertiamo G in una grammatica equivalente in forma normale di Chomsky 2) Lista tutte le derivazioni di 2n-1 passi o un passo se n=0 3) Se una di queste genera w, accetta. Altrimenti rifiuta.
Non possiamo usare teorema precedente dato che ci possono essere infinite w. Partiamo quindi al contrario cercando tutte le variabili che generano stringhe di terminali.
1) Marca tutti i terminali di G 2) Ripete finché nessuna nuova variabile viene marcata: 3) Marca una variabile A che ha la regola in G, A -> U1U2Un dove ogni simbolo è già stato marcato. 4) Se la variabile iniziale non è segnata, accetta. Altrimenti rifiuta.
Questo perché la classe dei linguaggi context-free non è chiusa rispetto a complemento o intersezione.
A è un CFL.
G una CFG per A, progettiamo una TM M che decide A.
Creiamo una copia di G in M. Su input w
1) Esegue TM S su G, w 2) Se S accetta, accetta. Altrimenti rifiuta.
Turing-riconoscibili Decidibili Context-free Regolari
Essendo però riconoscibile, dimostra che i riconoscitori sono più potenti dei decisori.
Macchina universale U che cicla su M se M cicla su w.
Serve a dimostrare l’indecidibilità di ATM.
Funzione iniettiva e suriettiva è detta biettiva: per ogni elemento di B esiste un solo elemento di A. Ogni elemento di A è mappato in unico elemento in B. Se tale funzione esiste, A e B hanno la stessa cardinalità.
Insieme R dei numeri reali non è numerabile.
L’insieme dei linguaggi è non numerabile, mentre l’insieme delle MdT si. Quindi alcuni linguaggi non sono ne decidibili ne turing-riconoscibili.
Dimostriamo per assurdo, usando un decisore H che si ferma su M.
Costruiamo una MT D che chiama H per determinare M.
Se provassimo D(<D>) avremmo
Ovviamente una contraddizione. Quindi ne D ne H possono esistere.
Se un linguaggio ed il suo complemento sono turing-riconoscibili, allora è decidibile.
Se un linguaggio è decidibile allora è riconoscibile. Il complemento di un linguaggio decidibile è anch’esso decidibile.
M1 riconosce A e M2 riconosce $\overline{A}$, M è decisore per A.
1) Esegue sia M1 sia M2 su w in parallelo 2) Se M1 accetta, accetta; se M2 accetta, rifiuta.
Dato che M si ferma se una delle due macchine accetta, è un decisore. Inoltre accetta solo le stringhe di A, altrimenti respinge, quindi è un decisore per A, ed A è decidibile.
Questo perché ATM è riconoscibile e abbiamo visto essere non decidibile, quindi $\overline{A~TM~}$ non può essere coTuring riconoscibile.
Ridurre un problema in modo che risolvendo il secondo, si abbia anche una soluzione al primo.
Se A è riducibile a B, e A è indecidibile allora anche B lo è.
Problema della fermata, decidere se una MdT si ferma dato un input.
Per assurdo supponiamo che è decidibile e dimostriamo che ATM è riducibile a HALTTM.
Abbiamo R che decide HALTTM. Costruiamo S per decidere ATM.
Se R decide HALTTM allora S dedice ATM ma è indecidibile, quindi anche HALTTM lo è.
Qui avremo S che esegue una modifica di M1, dove controllo che l’input sia = a w.
Se R decide ETM allora S dedice ATM ma è indecidibile, quindi anche ETM lo è.
Riduciamo da ETM, quindi fissiamo che una delle due TM abbia il linguaggio vuoto.
Se R dedice EQTM, S dedice ETM. Questo non è possibile.
Una storia di computazione è l’insieme di configurazioni da C1 a Cl dove Cl accetta per M.
Automa linearmente limitato: la testina non si sposta fuori dal input.
Il numero di configurazioni è = stati * lunghezza nastro * simbolin
Questo perché altrimenti tornerebbe su una stessa configurazione, andando quindi in ciclo.
Tramite un LBA. Dove accetta se esiste una configurazione accettante per M, altrimenti rifuta. E ritorna l’opposto.
Cioè se R accetta, vuol dire che insieme vuoto.
Il decisore quindi per ATM farebbe l’opposto.
L’unica stringa accettante sarebbe w, quindi M accetta w. Di conseguenza S accetta (M, w) ma non è possibile.
Una CFG genera tutte le possibili stringhe.
Se esiste una MdT che si ferma avendo solo f(w) sul nastro su input w.
Un linguaggio si dice riducibile mediante funzione, indicato con A <=m B, se esiste una funzione calcolabile da $\sum$* -> $\sum$*, dove per ogni w, w $\in$ A sse f(w) $\in$ B. f è chiamata riduzione da A a B.
Un oracolo è un dispositivo che riferisce se w appartiene al linguaggio. Una MdT con oracolo, può interrogare un oracolo. MB oracolo per linguaggio B.
Tramite oracolo, ETM è decidibile rispetto a ATM.
Turing riducibilità: A <=T B se A è decidibile rispettto a B.