|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-AutomiAPila History
Hide minor edits - Show changes to output
Changed lines 12-13 from:
Dato che l'automa a pila ha la stessa potenza descrittiva di una CFG, potremo usarlo per dimostrare che un linguaggio dato è libero dal contesto. E' un equivalenza importante, perché alcuni linguaggi sono più semplici da descrivere in termini di generazione, altri in termini di riconoscimento. to:
Dato che l'automa a pila ha la stessa potenza descrittiva di una CFG, potremo usarlo per dimostrare che un certo linguaggio è libero dal contesto. E' un'equivalenza importante, perché alcuni linguaggi sono più semplici da descrivere in termini di riconoscimento che di generazione. Changed lines 18-19 from:
Lo ''state control'' rappresenta gli stati e le funzioni di transizione, il nastro rappresenta le stringhe in ingresso, mentre le frecce rappresentano la ''testina'' dell'ingresso, che punta al prossimo simbolo che deve essere letto. Nel PDA fa la sua bella comparsa anche lo stack, su cui il PDA può scrivere e leggere simboli in modalità "last in, first out". La scrittura sullo stack è chiamata '''pushing''', e consiste nell'inserimento di un nuovo simbolo nella posizione in cima alla pila, spingendo tutti gli altri più sotto di una posizione; la lettura invece è detta '''popping''' e consiste nell'estrazione del simbolo in prima posizione, che viene appunto letto e rimosso. Si noti che lo stack può contenere una quantità illimitata di informazioni, quindi ad esempio sarà in grado di riconoscere un linguaggio non regolare come: {0'^n^'1'^n^'|n>=0}. Come? Basterà leggere un simbolo da input e ''pushare'' ogni 0 letto nello stack (che è illimitato); quando poi arriveremo agli 1, farà il ''popping'' di uno 0 per ogni 1 letto, e se alla fine dei giochi lo stack è vuoto allora l'ingresso sarà accettato. to:
Lo ''state control'' rappresenta gli stati e le funzioni di transizione, il nastro rappresenta le stringhe in ingresso, mentre le frecce rappresentano la ''testina'' dell'ingresso, che punta al prossimo simbolo che deve essere letto. Nel PDA fa la sua bella comparsa anche lo stack, su cui il PDA può scrivere e leggere simboli in modalità "last in, first out". La scrittura sullo stack è chiamata '''pushing''', e consiste nell'inserimento di un nuovo simbolo nella posizione in cima alla pila, spingendo giù tutti gli altri di una posizione; la lettura invece è detta '''popping''' e consiste nell'estrazione del simbolo in prima posizione, che viene appunto letto e rimosso. Si noti che lo stack può contenere una quantità illimitata di informazioni, quindi ad esempio sarà in grado di riconoscere un linguaggio non regolare come: {0'^n^'1'^n^'|n>=0}. Come? Basterà leggere un simbolo da input e ''pushare'' ogni 0 letto nello stack (che è illimitato); quando poi arriveremo agli 1, farà il ''popping'' di uno 0 per ogni 1 letto, e se alla fine dei giochi lo stack è vuoto allora l'ingresso sarà accettato. Changed line 43 from:
# per ogni i = 0, .. , m-1, abbiamo che ''(r'_i+1_',b)'' ∈ ''δ(r'_i_',w'_i+1_',a)'', dove ''s'_i_'=at'' e ''s'_i+1_'=bt'' per qualche ''a'' e''b'' che appartengono a Γ'_ε_' e con ''t''∈ Γ* (lo stato futuro di M dipende dallo stato attuale, dal simbolo in ingresso e dall stack); to:
# per ogni i = 0, .. , m-1, abbiamo che ''(r'_i+1_',b)'' ∈ ''δ(r'_i_',w'_i+1_',a)'', dove ''s'_i_'=at'' e ''s'_i+1_'=bt'' per qualche ''a'' e ''b'' che appartengono a Γ'_ε_' e con ''t''∈ Γ* (lo stato futuro di M dipende dallo stato attuale, dal simbolo in ingresso e dall stack); Changed line 51 from:
Qualche paragrafo fa avevamo fatto una descrizione alla buona di come avrebbe dovuto comportarsi un automa a pila per riconoscere il linguaggio. Cerchiamo ora di dare una spiegazione più seria. \\ to:
Qualche riga fa avevamo fatto una descrizione alla buona di come avrebbe dovuto comportarsi un automa a pila per riconoscere il linguaggio. Cerchiamo ora di dare una spiegazione più seria. \\ Changed lines 154-156 from:
Più nel dettaglio, P comincia la sua computazione scrivendo la variabile iniziale sullo stack; poi prosegue attraverso una serie di stringhe intermedie ottenute sostituendo le variabili secondo le regole della grammatica; infine quando arriva a una stringa composta da soli terminali la confronta con ''w'': se corrispondono allora P accetta, altrimenti viene abbandonato quel ramo della computazione.\\
Tutto ciò è molto bello, ma dove le memorizzo le stringhe intermedie? Anche se la tentazione è forte, non posso metterle così come sono nello stack. Se infatti dovessi fare una sostituzione di una variabile in una stringa intermedia e questa non si trova in cima allo stack, dove pensate che la prenderemo? Esatto, proprio là. La soluzione è conservare solo una parte della stringa intermedia nello stack, quella che va dalla prima variabile in poi; tutti i simboli che vengono prima devono corrispondere con la stringa in ingresso, altrimenti buttiamo via tutto. to:
Più nel dettaglio, P comincia la sua computazione scrivendo la variabile iniziale sullo stack; poi prosegue attraverso una serie di stringhe intermedie ottenute sostituendo le variabili secondo le regole della grammatica; infine quando arriva a una stringa composta da soli terminali la confronta con ''w'': se corrispondono allora P accetta, altrimenti abbandona quel ramo della computazione.\\
Tutto ciò è molto bello, ma dove le memorizzo le stringhe intermedie? Anche se la tentazione è forte, non posso metterle così come sono nello stack. Se infatti dovessi fare una sostituzione di una variabile in una stringa intermedia e questa non si trova in cima allo stack, dove pensate che la prenderemo? Esatto, proprio là dietro. La soluzione è conservare solo una parte della stringa intermedia nello stack, quella che va dalla prima variabile in poi; tutti i simboli che vengono prima devono corrispondere con la stringa in ingresso, altrimenti buttiamo via tutto. Changed line 160 from:
# δ(q'_start_',ε,ε)=[@{(@]q'_loop,S$[@)}@]\\ to:
# δ(q'_start_',ε,ε)=[@{(@]q'_loop_',S$[@)}@]\\ Changed line 163 from:
## δ(q'_loop_',ε,A)=[@{(@]q'_loop,w) | dove A->''w'' è una regola in R}\\ to:
## δ(q'_loop_',ε,A)=[@{(@]q'_loop_',w) | dove A->''w'' è una regola in R}\\ Changed line 165 from:
## δ(q'_loop_',a,a)=[@{(@]q'_loop,ε[@)}@]\\ to:
## δ(q'_loop_',a,a)=[@{(@]q'_loop_',ε[@)}@]\\ Changed line 167 from:
## δ(q'_loop_',ε,$)=[@{(@]q'_accept,ε[@)}@]\\ to:
## δ(q'_loop_',ε,$)=[@{(@]q'_accept_',ε[@)}@]\\ Changed line 178 from:
Come prima cosa, dovremo prevedere nella nostra grammatica G una variabile ''A'_pq_''' per ogni coppia di stati ''p'' e ''q'' in P. Non è una variabile a caso, ma quella che genera tutte le stringhe che possono portare il PDA da ''p'' a ''q'' lasciando lo stack nelle stesse condizioni in cui lo si è trovato (o vuoto o con lo stesso contenuto). Per riuscirci, dobbiamo fornire a P tre nuove caratteristiche: to:
Come prima cosa, dovremo aggiungere alla nostra grammatica G una variabile ''A'_pq_''' per ogni coppia di stati ''p'' e ''q'' in P. Non è una variabile a caso, ma quella che genera tutte le stringhe che possono portare il PDA da ''p'' a ''q'' lasciando lo stack nelle stesse condizioni in cui lo si è trovato (o vuoto o con lo stesso contenuto). Per riuscirci, dobbiamo fornire a P tre nuove caratteristiche: Changed lines 181-182 from:
# ogni transizione deve consistere o in un'operazione di push o in una di pop, non entrambe (nell'ultimo caso, basta dividere la transizione in due). to:
# ogni transizione deve consistere o in un'operazione di push o in una di pop, non entrambe (basta dividere la transizione in due). Changed line 212 from:
'''(II.b)''' ''Se ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto'', allora A'_pq_' genera ''x''''\\ to:
'''(II.b)''' ''Se ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto, allora A'_pq_' genera ''x''\\ Changed line 219 from:
## lo stack è vuoto solo all'inizio e alla fine della computazione\\ to:
## "lo stack è vuoto solo all'inizio e alla fine della computazione"\\ Changed line 222 from:
## lo stack è vuoto all'inizio e alla fine della computazione, e anche in un altro punto\\ to:
## "lo stack è vuoto all'inizio e alla fine della computazione, e anche in un altro punto"\\ Changed lines 231-232 from:
Avendo dimostrato tutti i possibili "se e solo se" nei casi (I), (II.a) e (II.b), possiamo '''finalmente''' dire che 'sto teorema immondo è dimostrato!\\
E ora, spritz time! to:
Avendo dimostrato tutti i possibili "se e solo se" nei casi (I), (II.a) e (II.b), possiamo '''finalmente''' dire che 'sto teorema immondo è dimostrato!
Changed line 231 from:
Avendo dimostrato tutti i possibili "se e solo se" nei casi (I), (II.a) e (II.b), possiamo '''finalmente''' dire che sto teorema infame è dimostrato!\\ to:
Avendo dimostrato tutti i possibili "se e solo se" nei casi (I), (II.a) e (II.b), possiamo '''finalmente''' dire che 'sto teorema immondo è dimostrato!\\
Changed line 212 from:
'''(II.b)''' ''Se ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto'', allora A'_pq_' genera ''x''\\ to:
'''(II.b)''' ''Se ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto'', allora A'_pq_' genera ''x''''\\
Changed lines 151-152 from:
(I) ''Se un linguaggio è libero dal contesto, allora esiste un PDA che lo riconosce'' to:
'''(I)''' ''Se un linguaggio è libero dal contesto, allora esiste un PDA che lo riconosce'' Changed lines 174-177 from:
(II) ''Se un PDA riconosce un linguaggio, allora è un linguaggio libero dal contesto''
...to be continued...
to:
'''(II)''' ''Se un PDA riconosce un linguaggio, allora è un linguaggio libero dal contesto''
Situazione inversa: abbiamo un PDA P e vogliamo creare un CFG G che generi tutte le stringhe accettate da P. Seguitemi prima con la costruzione, poi verificheremo se ci aiuta a dimostrare l'implicazione (tenetevi pronti: ci sarà un altro "se e solo se" da affrontare).
Come prima cosa, dovremo prevedere nella nostra grammatica G una variabile ''A'_pq_''' per ogni coppia di stati ''p'' e ''q'' in P. Non è una variabile a caso, ma quella che genera tutte le stringhe che possono portare il PDA da ''p'' a ''q'' lasciando lo stack nelle stesse condizioni in cui lo si è trovato (o vuoto o con lo stesso contenuto). Per riuscirci, dobbiamo fornire a P tre nuove caratteristiche:
# deve avere un unico stato accettante q'_accept_';
# deve svuotare il suo stack prima di accettare;
# ogni transizione deve consistere o in un'operazione di push o in una di pop, non entrambe (nell'ultimo caso, basta dividere la transizione in due).
Qualcosa sul comportamento di P già si capisce da queste caratteristiche: la prima operazione su una qualsiasi stringa x sarà di push, e l'ultima di pop. E le altre? Distinguiamo due casi:
* il simbolo estratto dallo stack alla fine della computazione è quello che avevo messo all'inizio, quindi lo stack è vuoto solo in questi due momenti. Simuliamo questa eventualità con la regola:
-->'''A'_pq_'->aA'_rs_'b'''
->, dove ''a'' è il simbolo letto in ingresso al primo passo, ''b'' è il simbolo letto in ingresso all'ultimo passo, ''r'' è lo stato che segue ''p'' ed ''s'' è quello che precede ''q''. Aiutiamoci con uno schema:
%center%Attach:IT-pda2cfg-1.gif
* seconda situazione: il simbolo estratto dallo stack alla fine della computazione non è quello che avevo messo all'inizio, quindi lo stack si è svuotato completamente tra ''p'' e ''q'' almeno una volta, in uno stato che chiameremo ''r''. Per questa eventualità introduciamo la regola:
-->'''A'_pq_'->A'_pr_'A'_rq_''''
->Aiutiamoci anche in questo caso con uno schema:
%center%Attach:IT-pda2cfg-1.gif
La costruzione di G termina aggiungendo per ogni ''p'' ∈ Q la regola: '''A'_pp_'->ε'''.
La costruzione è questa, ma per dimostrare la seconda implicazione del Teorema 1 (ve lo ricordate ancora?) dovremo dimostrare che A'_pq_' genera una stringa ''x'' se e solo se ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto. Distinguiamo ancora i due versi dell'implicazione.
'''(II.a)''' ''Se A'_pq_' genera ''x'', allora ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto''\\
La dimostrazione viene fatta per induzione.
* ''passo base'':\\
La derivazione ha un solo passo, quindi nella parte destra della regola devono esserci solo terminali. L'unica regola di questo tipo in G è A'_pp_'->ε, che è verificata perché se non prendo niente in ingresso parto con lo stack vuoto e finisco con lo stack vuoto.
* ''passo induttivo'':\\
Consideriamo vere le derivazioni con al più k passi, con k>=1, e verifichiamo se sono vere anche per k+1 passi.\\
Supponiamo di avere A'_pq_'-*->x ("A'_pq_' deriva x") in k+1 passi. Come abbiamo visto, nel primo passo di derivazione sono due le regole che possono essere applicate:
## A'_pq_'->aA'_rs_'b\\
Consideriamo una porzione ''y'' della ''x'' generata da A'_rs_', tale che ''x=ayb''. Dato che A'_rs_'-*->y in k passi, l'ipotesi induttiva ci dice che P può andare da ''r'' con stack vuoto ad ''s'' con stack vuoto. Vediamo bene cosa succede: P parte da ''p'' con lo stack vuoto, e dopo aver letto ''a'' va nello stato ''r'' mettendo ''t'' in cima allo stack; poi P legge la stringa ''y'' che lo porta allo stato ''s'' lasciando ''t'' lì dov'è; infine P legge ''b'' che lo porta allo stato ''q'' facendogli fare un pop di ''t'' dallo stack. Perfetto: parto e arrivo con lo stack vuoto;
## A'_pq_'->A'_pr_'A'_rq_'\\
Consideriamo le porzioni ''y'' e ''z'' delle ''x'' che generano rispettivamente A'_pr_' e A'_rq_', tali che ''x=yz''. Dato che A'_pr_'-*->y e A'_rq_'-*->z in massimo k passi, l'ipotesi induttiva ci dice che ''y'' può portare P da ''p'' ad ''r'' con lo stack vuoto all'inizio e alla fine; stessa cosa per ''z'' che porta P da ''r'' a ''q''. Quindi, sommando gli effetti, ''x'' può portare P dallo stato ''p'' con stack vuoto allo stato ''q'' con stack vuoto. Perfetto, abbiamo completato il passo induttivo!
'''(II.b)''' ''Se ''x'' può portare P da ''p'' con stack vuoto a ''q'' con stack vuoto'', allora A'_pq_' genera ''x''\\
Anche in questo caso la dimostrazione va fatta per induzione.
* ''passo base'':\\
La computazione ha 0 passi, quindi stato iniziale e stato finale coincidono. Chiamiamo ''p'' questo stato, per cui vale la regola A'_pp_'-*->x. Ma dato che in 0 passi P può leggere solo la stringa vuota, allora x=ε; sostituiamo il valore di ''x'' nella regola di prima e otteniamo A'_pp_'->ε, che è una regola di G per costruzione! La base è provata!
* ''passo induttivo'':\\
Consideriamo vere le computazioni con al più k passi, con k>=0, e verifichiamo se sono vere anche per k+1 passi.\\
Se supponiamo che P abbia una computazione in cui ''x'' porta ''p'' a ''q'' con stack vuoto in k+1 passi, i casi sono due:
## lo stack è vuoto solo all'inizio e alla fine della computazione\\
Chiamiamo ''t'' il simbolo che metto in cima allo stack alla prima mossa e che tolgo solo all'ultima. Sia ''a'' l'ingresso letto al primo passo, ''b'' quello letto all'ultimo, ''r'' lo stato in cui vado dopo la prima mossa, ed ''s'' lo stato che precede l'ultima. Abbiamo quindi che δ(p,a,ε) contiene (r,t) e δ(s,b,t) contiene (q,ε), perciò la regola A'_pq_'->aA'_rs_'b è in G.\\
Se adesso chiamiamo ''y'' la parte di ''x'' priva dei simboli ''a'' e ''b'' (dove ''x=ayb''), l'ingresso ''y'' può portare P dallo stato ''r'' ad ''s'' senza andare a toccare il simbolo ''t'' nello stack; in altre parole se diamo ''y'' in ingresso a P, questo può andare da ''r'' con lo stack vuoto ad ''s'' con lo stack vuoto. Evitando di considerare ''a'' e ''b'' abbiamo rimosso due passaggi dai ''k+1'' necessari per la computazione di ''x'', quindi ''y'' richiede ''k-1'' passi. Non chiedetemi perché, ma era proprio quello che volevamo sentirci dire! Grazie all'ipotesi induttiva possiamo infatti affermare che A'_rs_'-*->y, e di conseguenza che A'_pq_'-*->x!
## lo stack è vuoto all'inizio e alla fine della computazione, e anche in un altro punto\\
Sia ''r'' lo stato, diverso da quello iniziale e finale, in cui lo stack è vuoto; quindi le parti di computazione che vanno da ''p'' ad ''r'' e da ''r'' a ''q'' impiegano al massimo k passi. Chiamiamo ora ''y'' l'ingresso letto da P nella prima parte ''z'' quello letto nella seconda. L'ipotesi induttiva ci dice che A'_pr_'-*->y e che A'_rq_'-*->z. Ma dato che la regola A'_pq_'->A'_pr_'A'_rq_' è in G, A'_pq_'-*->x, e quindi abbiamo completato il passo induttivo.
[+++Quindi+++], ricapitoliamo. Dovevamo dimostrare questo teorema:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un linguaggio è libero dal contesto se e solo se esiste un automa a pila che lo riconosce.
>><<
Avendo dimostrato tutti i possibili "se e solo se" nei casi (I), (II.a) e (II.b), possiamo '''finalmente''' dire che sto teorema infame è dimostrato!\\
E ora, spritz time!
!!Corollario al Teorema 1
Ebbene sì, quell'incubo aveva anche un corollario:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Ogni linguaggio regolare è libero dal contesto.
>><<
Esticazzi.
Changed line 10 from:
Nel [[capitolo precedente->IT-Linguaggi liberi dal contesto]] abbiamo imparato che una CFG è in grado di costruire un linguaggio libero dal contesto. Ora introduciamo un nuovo tipo di modello computazionale che si occupa di riconoscere i linguaggi, ovvero l' '''automa a pila''' ('''PDA''', ''Push-Down Automata'').\\ to:
Nel [[capitolo precedente->IT-Linguaggi liberi dal contesto]] abbiamo imparato che una CFG è in grado di costruire un linguaggio libero dal contesto (da ora, anche CFL). Ora introduciamo un nuovo tipo di modello computazionale che si occupa di riconoscere i linguaggi, ovvero l' '''automa a pila''' ('''PDA''', ''Push-Down Automata'').\\ Changed lines 140-141 from:
to:
!!Teorema 1 - sull'equivalenza con CFG
A inizio capitolo abbiamo detto che l'automa a pila ha la stessa potenza descrittiva di un CFG. Non l'avessimo mai fatto: ora ci tocca dimostrarlo.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un linguaggio è libero dal contesto se e solo se esiste un automa a pila che lo riconosce.
>><<
'''Dimostrazione'''
Il teorema è un "se e solo se", quindi vanno dimostrati entrambi i sensi delle implicazioni.
(I) ''Se un linguaggio è libero dal contesto, allora esiste un PDA che lo riconosce''
Dato che per definizione un CFL è generato da una grammatica libera dal contesto, non dobbiamo fare altro che dimostrare che ogni CFG G può essere convertita in un equivalente PDA P. In pratica dobbiamo costruire P in modo che se gli passiamo in ingresso una stringa ''w'' generata da G, questi dovrà accettarla. Ma come fa a capire se è davvero generata dalla grammatica a lui equivalente? Dovrà verificare (in modo [@n.d.@] se tra tutte le derivazioni possibili della grammatica ne esiste una che dalla variabile iniziale porta a ''w''. \\
Più nel dettaglio, P comincia la sua computazione scrivendo la variabile iniziale sullo stack; poi prosegue attraverso una serie di stringhe intermedie ottenute sostituendo le variabili secondo le regole della grammatica; infine quando arriva a una stringa composta da soli terminali la confronta con ''w'': se corrispondono allora P accetta, altrimenti viene abbandonato quel ramo della computazione.\\
Tutto ciò è molto bello, ma dove le memorizzo le stringhe intermedie? Anche se la tentazione è forte, non posso metterle così come sono nello stack. Se infatti dovessi fare una sostituzione di una variabile in una stringa intermedia e questa non si trova in cima allo stack, dove pensate che la prenderemo? Esatto, proprio là. La soluzione è conservare solo una parte della stringa intermedia nello stack, quella che va dalla prima variabile in poi; tutti i simboli che vengono prima devono corrispondere con la stringa in ingresso, altrimenti buttiamo via tutto.
Siamo pronti.\\
Sia dato l'automa a pila P=(Q,Σ,Γ,δ,q'_1_',F). Per rendere la costruzione più chiara, descriveremo la funzione di transizione con la notazione breve, che permette di scrivere sullo stack una stringa intera con un unico passo della macchina (normalmente invece per scriverci su una stringa di dieci caratteri, ad esempio ACCABANANA, dovremmo fare 10 passi).\\
I tre stati fondamentali di P sono Q={q'_start_', q'_loop_', q'_accept_'}, in cui q'_start_' è quello iniziale e q'_accept_' l'unico accettato. Diamo ora una descrizione del funzionamento di P:
# δ(q'_start_',ε,ε)=[@{(@]q'_loop,S$[@)}@]\\
"metti il simbolo $ e la variabile iniziale nello stack, quindi vai in q'_loop_'";
# continua a ripetere i seguenti passi:
## δ(q'_loop_',ε,A)=[@{(@]q'_loop,w) | dove A->''w'' è una regola in R}\\
"se in cima allo stack c'è una variabile ''A'', seleziona in modo non deterministico una delle regole per A e sostituisci A con la stringa che si trova a destra della regola";
## δ(q'_loop_',a,a)=[@{(@]q'_loop,ε[@)}@]\\
"se in cima allo stack c'è un simbolo terminale ''a'', leggi il prossimo simbolo dall'ingresso e confrontalo con ''a''. Se corrispondono, ripeti; altrimenti abbandona questo ramo della computazione non deterministica";
## δ(q'_loop_',ε,$)=[@{(@]q'_accept,ε[@)}@]\\
"se in cima allo stack c'è il simbolo $, entra nello stato di accettazione!" (quando si arriva a $ abbiamo infatti la garanzia di aver letto tutta la stringa ''w'')
Ed ecco finalmente il diagramma degli stati di P in tutta la sua fierezza:
%center%Attach:IT-cfg2pda-1.gif
(II) ''Se un PDA riconosce un linguaggio, allora è un linguaggio libero dal contesto''
...to be continued...
Changed line 90 from:
(:cell align=center:){(q'_2_,$)} to:
(:cell align=center:)[@{(@]q'_2_',$[@)}@] Changed lines 94-95 from:
(:cell align=center:){(q'_2_',0)}
to:
(:cell align=center:)[@{(@]q'_2_',0[@)}@]
(:cell align=center:)[@{(@]q'_3_',ε[@)}@] Changed line 105 from:
(:cell align=center:){(q'_3_',ε)} to:
(:cell align=center:)[@{(@]q'_3_',ε[@)}@] Changed line 109 from:
(:cell align=center:){(q'_4_',ε)} to:
(:cell align=center:)[@{(@]q'_4_',ε[@)}@]
Added lines 1-144:
(:title Informatica Teorica - Automi a pila :)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Automi a pila ::'''
%center% %sottotitolo% Appunti & Dimostrazioni del 14 Aprile
!!Concetti iniziali
Nel [[capitolo precedente->IT-Linguaggi liberi dal contesto]] abbiamo imparato che una CFG è in grado di costruire un linguaggio libero dal contesto. Ora introduciamo un nuovo tipo di modello computazionale che si occupa di riconoscere i linguaggi, ovvero l' '''automa a pila''' ('''PDA''', ''Push-Down Automata'').\\
L'automa a pila è molto simile agli automi non deterministici, ma ha un optional che tutti gli NFA gli invidiano: lo '''stack''', che fornisce memoria aggiuntiva al PDA, permettendogli di riconoscere anche i linguaggi non regolari. \\
Dato che l'automa a pila ha la stessa potenza descrittiva di una CFG, potremo usarlo per dimostrare che un linguaggio dato è libero dal contesto. E' un equivalenza importante, perché alcuni linguaggi sono più semplici da descrivere in termini di generazione, altri in termini di riconoscimento.
Ecco un confronto tra gli schemi di un NFA e un PDA:
%center%Attach:IT-nfa-pda.gif
Lo ''state control'' rappresenta gli stati e le funzioni di transizione, il nastro rappresenta le stringhe in ingresso, mentre le frecce rappresentano la ''testina'' dell'ingresso, che punta al prossimo simbolo che deve essere letto. Nel PDA fa la sua bella comparsa anche lo stack, su cui il PDA può scrivere e leggere simboli in modalità "last in, first out". La scrittura sullo stack è chiamata '''pushing''', e consiste nell'inserimento di un nuovo simbolo nella posizione in cima alla pila, spingendo tutti gli altri più sotto di una posizione; la lettura invece è detta '''popping''' e consiste nell'estrazione del simbolo in prima posizione, che viene appunto letto e rimosso. Si noti che lo stack può contenere una quantità illimitata di informazioni, quindi ad esempio sarà in grado di riconoscere un linguaggio non regolare come: {0'^n^'1'^n^'|n>=0}. Come? Basterà leggere un simbolo da input e ''pushare'' ogni 0 letto nello stack (che è illimitato); quando poi arriveremo agli 1, farà il ''popping'' di uno 0 per ogni 1 letto, e se alla fine dei giochi lo stack è vuoto allora l'ingresso sarà accettato.
Concludiamo la panoramica iniziale sottolineando che l'automa a pila può essere sia deterministico che [@n.d.@], che non sono equivalenti in termini di potenza: il PDA [@n.d.@] riconosce molti più linguaggi dell'altro.
!!Definizione formale di automa a pila
La definizione formale di automa a pila è molto simile a quella dell'automa a stati finiti, con l'unica eccezione della presenza dello stack, che può avere un alfabeto diverso rispetto a quello d'ingresso.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un '''automa a pila''' è una 6-upla (Q,Σ,Γ,δ,q'_0_',F), dove:
* Q è l'insieme finito degli stati dell'automa
* Σ è l'alfabeto (insieme finito) dei simboli in ingresso
* Γ è l'alfabeto (insieme finito) dello stack
* δ: Q × Σ'_ε_' × Γ'_ε_' → P(Q × Γ'_ε_') è la funzione di transizione. Σ'_ε_' e Γ'_ε_' stanno a significare che consideriamo l'unione tra gli insiemi Σ e Γ con l'elemento {ε}
* q'_0_' ∈ Q è lo stato iniziale dell'automa
* F ⊆ Q è l'insieme finito degli stati accettanti
>><<
!!!Definizione formale di computazione
Siano dati:
* un automa a pila M=(Q,Σ,Γ,δ,q'_0_',F)
* una stringa di ingresso ''w'' tale che ''w = w'_1_'w'_2_'..w'_m_''' , dove ogni w'_i_' fa parte dell'alfabeto Σ'_ε_'
* una stringa ''s'' tale che ''s = s'_1_'s'_2_'..s'_m_''' , dove ogni s'_i_' appartiene allo stack
Diciamo allora che M accetta ''w'' se esiste una sequenza di stati ''r'_0_'r'_1_'..r'_m_''' in Q che rispettino tre condizioni:
# ''r'_0_' = q'_0_''' e ''s'_0_' = ε'' (la macchina parte dallo stato iniziale e con lo stack vuoto);
# per ogni i = 0, .. , m-1, abbiamo che ''(r'_i+1_',b)'' ∈ ''δ(r'_i_',w'_i+1_',a)'', dove ''s'_i_'=at'' e ''s'_i+1_'=bt'' per qualche ''a'' e''b'' che appartengono a Γ'_ε_' e con ''t''∈ Γ* (lo stato futuro di M dipende dallo stato attuale, dal simbolo in ingresso e dall stack);
# r'_m_' ∈ F (la macchina accetta l'ingresso se l'ultimo stato in cui finisce è tra quelli finali).
!!!Esercizietto
Dare la definizione formale del PDA che riconosce il linguaggio {0'^n^'1'^n^'|n>=0}.
'''Soluzione'''
Qualche paragrafo fa avevamo fatto una descrizione alla buona di come avrebbe dovuto comportarsi un automa a pila per riconoscere il linguaggio. Cerchiamo ora di dare una spiegazione più seria. \\
La lettura dei simboli in ingresso da parte del PDA può essere distinta in due fasi:
# finché il simbolo letto è uno 0, verrà messo in cima allo stack;
# quando il simbolo letto diventa un 1, verrà fatto il pop di uno 0 dallo stack per ogni simbolo 1 letto.
Se la lettura della stringa in ingresso finisce in concomitanza con lo svuotamento completo dello stack, allora la stringa è accettata; altrimenti è rifiutata.
Cominciamo ora con le definizioni formali.\\
Sia dato un automa a pila M=(Q,Σ,Γ,δ,q'_1_',F), dove:
* Q = {q'_1_', q'_2_', q'_3_', q'_4_'}
* Σ = {0,1}
* Γ = {0,$} (dove il simbolo di $ ci servirà per capire se lo stack è vuoto)
* q'_1_' è lo stato iniziale
* F = {q'_1_',q'_4_'} (anche q'_1_' è stato finale perché potremmo passare all'automa una stringa vuota)
* δ è data dalla seguente tabella:
(:table align=center width=60%:)
(:cellnr bgcolor=#d4e1f0 align=center:)Input:
(:cell bgcolor=#d4e1f0 colspan=3 align=center:)0
(:cell bgcolor=#d4e1f0 colspan=3 align=center:)1
(:cell bgcolor=#d4e1f0 colspan=3 align=center:)ε
(:cellnr bgcolor=#f5f9fc align=center:)Stack:
(:cell bgcolor=#f5f9fc align=center:)0
(:cell bgcolor=#f5f9fc align=center:)$
(:cell bgcolor=#f5f9fc align=center:)ε
(:cell bgcolor=#f5f9fc align=center:)0
(:cell bgcolor=#f5f9fc align=center:)$
(:cell bgcolor=#f5f9fc align=center:)ε
(:cell bgcolor=#f5f9fc align=center:)0
(:cell bgcolor=#f5f9fc align=center:)$
(:cell bgcolor=#f5f9fc align=center:)ε
(:cellnr bgcolor=#f5f9fc align=center:)q'_1_'
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:){(q'_2_,$)}
(:cellnr bgcolor=#f5f9fc align=center:)q'_2_'
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:){(q'_2_',0)}
(:cell align=center:){(q'_3_',ε)}
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cellnr bgcolor=#f5f9fc align=center:)q'_3_'
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:){(q'_3_',ε)}
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:){(q'_4_',ε)}
(:cell align=center:)0
(:cellnr bgcolor=#f5f9fc align=center:)q'_4_'
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:tableend:)
Il comportamento di questo PDA si capisce meglio rappresentandolo con un più familiare diagramma degli stati:
%center%Attach:IT-pdaDiag.gif
Come interpretare le frecce? Ad esempio, ''a,b -> c'' va letto come: quando l'automa legge il simbolo ''a'' dall'ingresso, dovrà sostituire il simbolo ''b'' che si trova in cima allo stack con il simbolo ''c''. In pratica ''b'' si riferisce a un pop e ''c'' a un push.\\
Riferendoci al diagramma degli stati, vediamo come si comporta l'automa:
* da q'_1_' a q'_2_': ''ε,ε->$''\\
Prima di leggere qualsiasi simbolo della stringa, pushiamo nello stack vuoto il simbolo $ (presto capiremo perché)
* da q'_2_' a q'_2_': ''0,ε->0''\\
Rimaniamo in q'_2_' finché leggiamo il simbolo 0 dalla stringa in ingresso. Per ognuna di queste letture inseriamo uno 0 in cima allo stack (senza sostituirlo con niente)
* da q'_2_' a q'_3_': ''1,0->ε''\\
Quando ci arriva il primo 1, passiamo dallo stato q'_2_' al q'_3_'. Per quanto riguarda lo stack facciamo un pop del primo 0 e non ci scriviamo niente
* da q'_3_' a q'_3_': ''1,0->ε''\\
Rimaniamo in q'_3_' finché leggiamo il simbolo 1 dalla stringa in ingresso. Per ognuna di queste letture facciamo un pop di uno 0 dallo stack
* da q'_3_' a q'_4_': ''ε,$->ε''\\
Quando finiamo i simboli da leggere in ingresso, se in cima alla lista ritroviamo il simbolo $ possiamo affermare che lo stack si è svuotato, quindi possiamo passare allo stato finale q'_4_'
..to be continued
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
