Una quadrupla (V,
- V è insieme delle variabili
-
$\sum$ è insieme terminali - R è insieme delle regole
- S è stato iniziale
Prima si costruisce il DFA per il linguaggio regolare, poi lo si trasforma in CFG.
- Una variabile R per ogni stato
- Regola Ri -> aRq se c'è transazione da stato i a stato q tramite a nel DFA
- Regola Ri ->
$\epsilon$ se stato i è accettante
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:
- A -> BC
- A -> a
Per ottenerla:
- Aggiungiamo nuova variabile iniziale
- Eliminiamo le regola A ->
$\epsilon$ , poi in ogni regola dove appare A nel lato destro, scriviamo tutte le occorenze senza la A.- A ->
$\epsilon$ fa diventare S -> ASA | aB in S -> ASA | aB | SA | AS | S
- A ->
- Eliminiamo le regole unitarie A -> B, poi aggiungiamo A -> u per la regola B -> u, dove u è una stringa di variabili e terminali
- Rimpiazziamo le regole A->u1u2u3 in poi con A->u1A1 e A1->u2A2 e A2 -> u3.
- Infine convertimo le ui che sono terminali con una nuova regola Ui -> ui e sostituiamo i terminali.
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,
- Q è insieme degli stati
-
$\sum$ è alfabeto dell'input -
$\delta$ è funzione transizione Qx$\sum$$\epsilon$ x$\Gamma$$\epsilon$ -> P(Qx$\Gamma$$\epsilon$ ) -
$\Gamma$ è alfabeto della pila - q0 è stato iniziale
- F è insieme degli stati accettanti
Nel diagramma di stato si scrive a,b -> c che vuol dire
- legge input a
- toglie b dalla cima della pila
- scrive c sulla pila
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.
- Inserisce simbolo marcato $ e la prima variabile nella pila
- Se sulla cima della pila c'è A, scegli non deterministicamente una regola per A e sostituisce con la parte destra di A
- 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
- Se sulla cima c'è il simbolo $, entra nello stato accettante. L'input è stato completamente letto
- Ripete dal punto 2
Nuova notazione (r, 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à
- unico stato accettante
- svuota la pila prima di accettare
- una transizione o push o pop
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:
- per ogni i >= 0, uvixyiz
$\in$ A - |vy| > 0
- |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.
- Può sia scrivere sia leggere sul nastro
- La testina si muove a destra e sinistra
- Nastro è infinito
- Gli stati di accettazione e rifiuto sono immediati
Una setupla (Q,
- Q è insieme degli stati
-
$\sum$ è alfabeto dell'input senza simbolo blank -
$\delta$ è funzione transizione Qx$\Gamma$ -> Qx$\Gamma$x{L, R} -
$\Gamma$ è alfabeto del nastro con blank - q0 è stato iniziale
- qaccept è stato di accettazione
- qreject è stato di rifiuto
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:
- Su input <B, w> dove B è un DFA e w è una stringa
- Simula B su w
- 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) =
- Marca stato iniziale di A
- Ripete finché non sono marcati nuovi stati:
- Marca uno stato che ha una transizione proveniente da uno stato già marcato
- Se nessuno stato di accettazione è marcato, accetta. Altrimenti rifiuta.
Costruiamo linguaggio L(C) = (L(A) interseca
Solo stringhe riconosciute da A o da B, differenza simmetrica.
Se L(C) è vuoto allora L(A) e L(B) sono uguali.
- Costruiamo DFA C
- Eseguiamo TM di E su input C
- 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
- Convertiamo G in una grammatica equivalente in forma normale di Chomsky
- Lista tutte le derivazioni di 2n-1 passi o un passo se n=0
- 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.
- Marca tutti i terminali di G
- Ripete finché nessuna nuova variabile viene marcata:
- Marca una variabile A che ha la regola in G, A -> U1U2Un dove ogni simbolo è già stato marcato.
- 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
- Esegue TM S su G, w
- 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.
- Accetta se M accetta w
- Rifiuta se M non accetta w
Costruiamo una MT D che chiama H per determinare M.
- Esegue H su input <M, <M> >
- Accetta se H rifiuta, rifiuta se H accetta
Se provassimo D(<D>) avremmo
- Accetta se D non accetta
- Rfiuta se D non rifiuta
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
- Esegue sia M1 sia M2 su w in parallelo
- 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{ATM}$ 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.
- Esegue R su (M, 2)
- Se R rifiuta, rifiuta
- Se R accetta, simula M su w finchè non si ferma
- Se M accetta, accetta. Se rifiuta, rifiuta
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.
- Costruiamo M1
- Esegue R su M1
- Se R accetta, rifiuta. Se R rifiuta, accetta
Se R decide ETM allora S dedice ATM ma è indecidibile, quindi anche ETM lo è.
- Costruiamo M2
- Se x ha forma 0n1n, accetta
- Se non ha forma, esegue M e accetta, se accetta
- Esegue R su M2
- Se R accetta, accetta. se R rifiuta, rifiuta
Riduciamo da ETM, quindi fissiamo che una delle due TM abbia il linguaggio vuoto.
- Eseguiamo R su (M, M1) dove M1 rifiuta ogni input
- Se R accetta, allora accetta. Se R rifiuta, rifiuta.
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
- Simula M per qngn passi o finchè non si ferma
- Se M è ferma, accetta se ha accettato. Rifiuta, se ha rifiutato. Se non si è fermata, rifiuta.
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
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.