Automa a pila

Lezione precedente: Proprietà di chiusura dei linguaggi regolari

Corso: Materia:Informatica Teorica

Prossima lezione: Macchina di Turing

Introduzione

Nella lezione in cui abbiamo discusso le proprietà formali degli accettori a stati finiti è emerso un aspetto importante: il pumping lemma prima ed il teorema di Myhill - Nerode dopo hanno evidenziato l'esistenza di linguaggi formali per i quali è impossibile costruire un accettore a stati finiti in grado di riconoscerli.

Negli esempi presentati, l'aspetto che ha ostacolato la realizzazione di tali automi è dato dall'incapacità di contare fino ad un numero arbitrariamente grande.

Il problema risiede nel fatto che il modello degli automi a stati finiti è dotato di un quantitativo di memoria limitato, lo stretto necessario per tenere traccia dell'evoluzione stati; questa forma di memoria è indispensabile per il funzionamento dell'automa ma non può essere sfruttata per conservare dati riguardanti i simboli prelevati dal nastro d'ingresso. La capacità di contare fino ad un numero arbitrariamente grande implica la possibilità di memorizzare un numero arbitrariamente grande di informazioni, un requisito che contrasta con la finitezza degli accettori che abbiamo esaminato finora.

Si può pensare di estendere il modello degli automi a stati finiti prevedendo un dispositivo che offra la possibilità di memorizzare una quantità teoricamente illimitata di dati; tale estensione porterebbe alla nascita di un nuovo modello computazionale, composto da due parti: un automa a stati finiti abbinato ad un supporto di memoria.

La semplice aggiunta di un dispositivo non è sufficiente per estendere le prestazioni del modello: è necessario integrarne il funzionamento in modo da creare un tutt'uno omogeneo. Il dispositivo di memoria è un semplice nastro suddiviso in celle, come già accade per i nastri di ingresso ed uscita. Il nastro di memoria conterrebbe sempre almeno un simbolo, detto simbolo iniziale ed una speciale testina in grado di leggere e scrivere dati nelle celle del nastro; tale dispositivo potrebbe muoversi avanti e indietro di una cella per volta.

La scrittura (nella letteratura inglese: push) di un simbolo sul nastro di memoria avverrebbe con un procedimento in due passi:

1. avanzamento della testina alla cella successiva;
2. scrittura del simbolo.

In modo analogo, la lettura (nella letteratura inglese: pop) di un simbolo dal nastro avverrebbe con il seguente procedimento:

1. lettura del simbolo;
2. se il simbolo è diverso dall'indicatore di inizio del nastro allora la testina retrocede di una posizione, altrimenti rimane dov'è.

Se la lettura e la scrittura seguono questa logica allora la testina sarà in grado di leggere solamente l'ultimo simbolo che è stato scritto e dunque la politica di gestione della memoria sarà di tipo LIFO (Last In First Out), tipica della struttura dati comunemente nota come pila.

Proprio per questo motivo gli automi che vengono arricchiti con un dispositivo di memoria dotato delle caratteristiche appena discusse si chiamano automi a pila; essi costituiscono una significativa estensione del modello degli automi a stati finiti in quanto sono in grado di riconoscere linguaggi non regolari.

La presente lezione ha lo scopo di introdurre i tre tipi di automi a pila corrispondenti ai tre tipi di automi a stati finiti già conosciuti: l' automa a pila semplice, l' accettore a pila ed il trasduttore a pila.

Concludiamo la parte introduttiva della lezione offrendo una breve panoramica storica riguardante questa categoria di automi: sebbene il concetto abbia fatto la sua comparsa in un lavoro di Allen Newell del 1957, il primo a presentare l'automa come modello computazionale fu Anthony Oettinger in un articolo del 1961 dedicato allo studio dei metodi automatici per svolgere l'analisi sintattica dei testi.

Due anni dopo il matematico francese Marcel-Paul Schützenberger scrisse un articolo riguardante alcune osservazioni, svolte da lui e da Noam Chomsky, circa le possibili relazioni esistenti tra gli automi a pila ed i linguaggi liberi dal contesto.

Queste due opere rappresentano le fondamenta su cui è stato costruito il formalismo; le sue origini si trovano quindi nell'area della linguistica computazionale che lo ha pensato, almeno inizialmente, come uno strumento utile per arrivare ad un fine.

Automa a pila

Il modello computazionale dell'automa a pila è presente in due varianti: quella deterministica e quella non deterministica; in questa lezione affronteremo lo studio della prima variante, lasciando la seconda ad un momento successivo.

Sebbene l'automa a pila sia un modello formale, e quindi astratto, è possibile pensarlo come una macchina; una sua versione stilizzata è visibile nell'immagine seguente.

senza cornice

La rappresentazione schematica appena proposta contiene tutti gli elementi caratteristici degli automi a pila: un nastro d'ingresso contenente una sequenza di simboli, un nastro di memoria contenente simboli provenienti da un alfabeto diverso da quello di ingresso ed una serie di stati.

Come già visto nel caso dell'automa a stati finiti, anche l'automa a pila funziona sulla base di un ciclo di lavoro prefissato. In particolare si riconoscono quattro fasi:

1. lettura di un simbolo dal nastro d'ingresso;
2. lettura di un simbolo dalla memoria a pila;
3. determinazione dello stato prossimo;
4. scrittura di una stringa di simboli sulla pila.

La lettura del simbolo d'ingresso avviene prelevando il simbolo dal nastro d'ingresso e spostando poi la testina verso destra. In particolari condizioni è possibile non leggere nulla dal nastro d'ingresso: in tal caso si considererà come simbolo d'ingresso $\epsilon$, ossia la stringa vuota. Come vedremo, la differenza tra la versione deterministica e quella non deterministica dell'automa risiede proprio nel modo in cui vengono gestite le transizioni prive di lettura.

La lettura del simbolo che si trova in cima alla pila avviene prelevando il simbolo stesso, cancellandolo dalla pila e spostando la testina indietro di una posizione; fa eccezione la posizione iniziale dove non è possibile arretrare ulteriormente, né cancellare il simbolo di inizio pila.

La scrittura di una stringa di simboli sulla pila avviene avanzando la testina di una posizione alla volta e scrivendo uno dei simboli della stringa sul nastro. È possibile non scrivere nessun simbolo sulla pila: in tal caso il simbolo da scrivere verrà rappresentato da $\epsilon$.

Lo stato prossimo dell'automa viene deciso basandosi su tre fattori: lo stato attuale, il simbolo prelevato dal nastro d'ingresso ed il simbolo prelevato dalla cima della pila.

Definizione di automa a pila

Un automa a pila $P$ è una sestupla ordinata $P=(Q,I,\Gamma ,\delta ,q_{0},Z_{0})$ definita come segue:

• $Q$ è un insieme finito di stati;
• $I$ è un insieme finito di simboli d'ingresso, detto alfabeto d'ingresso;
• $\Gamma$ è un insieme finito di simboli della pila scelti in modo che $\Gamma \cap I=\emptyset$, detto alfabeto della pila;
• $\delta$ è una funzione $\delta :Q\times I\cup \left\{\epsilon \right\}\times \Gamma \rightarrow Q\times \Gamma ^{*}$ detta funzione di transizione;
• $q_{0}\in Q$ è lo stato iniziale;
• $Z_{0}\in \Gamma$ è il simbolo iniziale della pila;

Commento alla definizione

Lo stile della definizione ricalca quello impiegato nella lezione dedicata agli automi a stati finiti; vi sono tuttavia due aspetti che meritano un'attenzione particolare: la stringa vuota nell'insieme di partenza della funzione di transizione e l'operatore di Kleene presente nell'insieme di arrivo della funzione stessa.

La presenza della stringa vuota nell'insieme di partenza della funzione di transizione indica che è possibile determinare lo stato prossimo dell'automa a pila anche senza consumare nessun simbolo d'ingresso: in questi casi la transizione avviene basandosi solamente sullo stato attuale e sul simbolo posto in cima alla pila.

In realtà questo modo di procedere richiede una certa attenzione in quanto può portare ad automi dotati di comportamenti indesiderati: è sufficiente che una coppia di stati sia collegata da almeno due transizioni, una delle quali avvenga senza consumare simboli d'ingresso.

In una situazione di questo genere, una volta raggiunto lo stato di partenza delle transizioni, l'automa si trova di fronte ad un bivio: passare allo stato prossimo consumando un simbolo d'ingresso oppure no? Questo comportamento prende il nome di non determinismo e sarà oggetto di studio ed approfondimento in alcune delle prossime lezioni; in effetti la struttura degli automi a pila contempla il non determinismo, ma questa loro caratteristica può essere tenuta sotto controllo imponendo un semplice vincolo: ogni volta che due stati saranno collegati da una transizione che non consuma simboli in ingresso, quella transizione dovrà essere unica. Come vedremo nella lezione riguardante gli automi a pila non deterministici, la rimozione di questo vincolo avrà conseguenze importanti.

Un discorso a parte lo merita l'operatore star di Kleene che compare nell'insieme di arrivo della funzione di transizione: la sua presenza implica che, in generale, per ogni transizione è possibile aggiungere alla pila anche più di un simbolo, ossia una stringa di simboli. Questo accorgimento è necessario in quanto, per come è stato definito il ciclo di lavoro dell'automa, c'è una fase in cui il simbolo in cima alla pila viene tolto allo scopo di decidere lo stato prossimo dell'automa. A questo punto è possibile fare due cose: o scartare il simbolo letto dalla pila perché non è più necessario oppure rimetterlo al suo posto. Ma che succede quando si desidera sia rimettere a posto il simbolo prelevato sia aggiungere un altro simbolo? Il problema si risolve semplicemente permettendo all'automa di mettere più di un simbolo sulla pila; generalizzando il concetto, viene lasciata la libertà di aggiungere una stringa.

Per comprendere meglio il funzionamento dell'automa sviluppiamo un esempio, derivante dal settore dell'automazione industriale: un impianto di inscatolamento.

Un esempio dal settore dell'automazione

Un'azienda farmaceutica produce, tra le altre cose, uno sciroppo per la tosse; dopo aver imbottigliato il prodotto è necessario racchiudere ogni flacone in un involucro di cartone. A tal proposito l'azienda dispone di una macchina che è in grado di svolgere l'intera operazione, il cui funzionamento è brevemente descritto in seguito.

La macchina che si occupa dell'inscatolamento dei flaconi è dotata di un nastro trasportatore su cui possono viaggiare due tipi di oggetti: le scatole vuote ed i prodotti da confezionare. Il ciclo produttivo funziona come segue:

1. inizialmente il nastro trasporta scatole vuote: la macchina le riconosce e le carica in un magazzino;
2. successivamente il nastro trasporta il prodotto da inscatolare; ogni flacone viene inserito in una scatola.

La macchina può terminare l'esecuzione in tre circostanze:

1. non ci sono flaconi da inscatolare e c'è un avanzo di scatole;
2. non ci sono abbastanza scatole per confezionare tutti i flaconi;
3. il numero di flaconi ed il numero di scatole si equivale.

Vediamo ora come descrivere la macchina impiegando un automa a pila: identificheremo anzitutto

Gli elementi da identificare per descrivere l'automa a stati finiti sono: un insieme finito di stati, un insieme finito di simboli in ingresso ed una funzione di transizione.

Insieme degli stati

1. $q_{0}$: è lo stato iniziale, in cui la macchina riceve le scatole;
2. $q_{1}$: stato di ricezione dei flaconi, in cui la macchina riceve almeno un flacone;
3. $q_{2}$: stato di eccesso di flaconi, in cui la macchina termina l'inscatolamento con un avanzo di involucri;
4. $q_{3}$: stato di eccesso di scatole, in cui la macchina termina l'inscatolamento con un avanzo di flaconi;
5. $q_{4}$: stato di parità, in cui la macchina termina l'inscatolamento senza nessun avanzo.

Si può quindi concludere che $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4}\right\}$.

Alfabeto d'ingresso

La macchina riceve in ingresso due tipi di oggetto: le scatole, che indicheremo con il simbolo $s$ ed i flaconi, che indicheremo con il simbolo $f$. L'alfabeto di ingresso per l'automa a stati finiti soggiacente all'automa a pila sarà quindi $I=\left\{s,f\right\}$.

Alfabeto della pila

La pila viene utilizzata per tenere conto di quante scatole siano state caricate nel magazzino; l'alfabeto della pila conterrà quindi il simbolo $S$ che indica la presenza di una scatola ed il simbolo convenzionale $Z_{0}$, utilizzato per indicare che la pila non contiene elementi. Formalmente: $\Gamma =\left\{S,Z_{0}\right\}$.

Funzione di transizione

Osservando la definizione si può notare che la funzione di transizione assume come argomenti terne ordinate di valori, nelle quali il primo è uno stato, il secondo è un simbolo d'ingresso (o la stringa vuota) ed il terzo è un simbolo della pila. Questo aspetto incide sulla possibilità di rappresentare la funzione di transizione in forma tabellare, perché una rappresentazione completa richiederebbe una tabella in tre dimensioni. Diventa quindi indispensabile rappresentare la funzione di transizione mediante il suo grafo, specificando quindi solamente le terne ordinate che sono associate ad una mossa dell'automa. Dal punto di vista insiemistico il grafo della funzione di transizione è dato di seguito: $G_{\delta }=\left\{((q_{0},s,Z_{0});(q_{0},SZ_{0})),((q_{0},s,S);(q_{0},SS)),((q_{0},f,Z_{0});(q_{2},Z_{0})),((q_{0},f,S);(q_{1},\epsilon )),((q_{1},f,S);(q_{1},\epsilon )),((q_{1},f,Z_{0});(q_{2},Z_{0})),((q_{1},\epsilon ,S);(q_{3},S)),((q_{1},\epsilon ,Z_{0});(q_{4},Z_{0}))\right\}$

Un'altra osservazione riguarda le immagini della funzione che in questo caso non sono più semplicemente stati bensì coppie ordinate di stati e stringhe della pila.

La tabella che prepareremo servirà per rappresentare il grafo e come di consueto sarà composta da tante righe quante sono le transizioni dell'automa; ogni riga sarà caratterizzata da cinque elementi: i primi tre serviranno per definire l'argomento della funzione, gli altri due per definire l'immagine.

Numero transizione	Stato attuale	Simbolo in ingresso	Simbolo della pila	Stato prossimo	Aggiunta alla pila
1	$q_{0}$	$s$	$Z_{0}$	$q_{0}$	$SZ_{0}$
2	$q_{0}$	$s$	$S$	$q_{0}$	$SS$
3	$q_{0}$	$f$	$Z_{0}$	$q_{2}$	$Z_{0}$
4	$q_{0}$	$f$	$S$	$q_{1}$	$\epsilon$
5	$q_{1}$	$f$	$S$	$q_{1}$	$\epsilon$
6	$q_{1}$	$f$	$Z_{0}$	$q_{2}$	$Z_{0}$
7	$q_{1}$	$\epsilon$	$S$	$q_{3}$	$S$
8	$q_{1}$	$\epsilon$	$Z_{0}$	$q_{4}$	$Z_{0}$

Esiste un altro modo per esprimere la funzione di transizione: pur essendo sempre basata sul grafo della funzione stessa, questa rappresentazione tabellare suddivide le transizioni in due colonne anziché cinque; la prima colonna contiene le terne ordinate che indicano gli argomenti della funzione, mentre la seconda contiene le coppie ordinate che specificano l'immagine. Per l'accettore a pila dell'esempio la tabella è riportata di seguito.

Numero transizione	Argomento	Immagine
1	$(q_{0},s,Z_{0})$	$(q_{0},SZ_{0})$
2	$(q_{0},s,S)$	$(q_{0},SS)$
3	$(q_{0},f,Z_{0})$	$(q_{2},Z_{0})$
4	$(q_{0},f,S)$	$(q_{1},\epsilon )$
5	$(q_{1},f,S)$	$(q_{1},\epsilon )$
6	$(q_{1},f,Z_{0})$	$(q_{2},Z_{0})$
7	$(q_{1},\epsilon ,S)$	$(q_{3},S)$
8	$(q_{1},\epsilon ,Z_{0})$	$(q_{4},Z_{0})$

Dato che questo è il primo automa a pila che analizziamo, vale la pena spendere qualche parola sul significato delle transizioni.

La transizione numero 1 descrive la fase iniziale del processo di inscatolamento: il magazzino è vuoto ed arriva la prima scatola. Lo stato del magazzino viene aggiornato mediante l'aggiunta di una scatola.

La transizione numero 2 descrive la continuazione della fase di ricezione delle scatole: si riceve una scatola e nel magazzino ce n'è già almeno una; come in precedenza, lo stato del magazzino viene aggiornato.

La transizione numero 3 descrive una situazione di errore: il magazzino è vuoto e al posto di ricevere una scatola si riceve un flacone; a questo punto la macchina non può operare normalmente ed entra in una situazione di errore del tipo eccesso di flaconi.

La transizione numero 4 indica il passaggio alla fase di inscatolamento: anziché ricevere una scatola si riceve un flacone; l'automa cambia stato e rimuove una scatola dal magazzino.

La transizione numero 5 descrive la parte centrale dell'inscatolamento: ogni flacone ricevuto è abbinato ad una scatola e quest'ultima che viene rimossa dal magazzino.

La transizione numero 6 descrive una delle tre condizioni finali: si riceve un flacone ma il magazzino è vuoto; ci si trova ancora nella situazione eccesso di flaconi.

La transizione numero 7 riguarda un'altra possibile condizione finale: non si ricevono più flaconi ma il magazzino contiene ancora almeno una scatola; l'automa si porta nello stato che riguarda un eccesso di scatole.

La transizione numero 8, infine, si manifesta quando non ci sono più flaconi ed il magazzino è vuoto: una condizione ideale per terminare il lavoro.

Attribuire un senso alle transizioni ci offre la possibilità di dare un significato preciso ai concetti di transizione e di funzione di transizione.

La singola transizione descrive come deve reagire l'automa quando riceve uno specifico stimolo dall'esterno e va dunque interpretata come un'istruzione.

Se una transizione rappresenta una singola istruzione, l'insieme di tutte le transizioni - ossia la funzione di transizione - sarà il programma svolto dall'automa a pila per reagire correttamente ad una gamma di stimoli ricevuti dall'esterno e strutturati secondo una determinata logica.

Ad un livello più alto è possibile attribuire alla funzione di transizione il significato di comportamento dell'automa; tale interpretazione è plausibile dato che la funzione descrive meccanismi che si attivano in corrispondenza a stimoli ambientali ai quali in un certo senso l'automa si adatta.

Descrizione algebrica dell'automa a pila

Grazie agli elementi che abbiamo definito è possibile scrivere la definizione completa dell'automa a pila, elencandone i sei elementi costitutivi:

• $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4}\right\}$;
• $I=\left\{s,f\right\}$;
• $\Gamma =\left\{S,Z_{0}\right\}$;
• $\delta$ è la funzione il cui grafo è l'insieme $G_{\delta }$;
• $q_{0}$ è lo stato iniziale;
• $Z_{0}$ è il simbolo che indica che la pila non contiene elementi.

Naturalmente non può mancare il diagramma degli stati, a partire dal quale è possibile dedurre tutti gli elementi dell'automa.

Diagramma degli stati dell'automa

Confrontando il diagramma degli stati visibile di seguito con quelli presentati per gli automi a stati finiti si può notare una differenza nel modo di etichettare gli archi che rappresentano le transizioni: questo accorgimento è indispensabile per specificare in che modo venga manipolata la pila.

Più precisamente ogni arco ha un'etichetta nella forma $a,B/C$ dove $a\in I$ è il simbolo prelevato dal nastro d'ingresso, $B\in \Gamma$ è il simbolo prelevato dalla cima della pila e $C\in \Gamma ^{*}$ è la stringa di simboli da porre sulla pila.

Accettore a pila

L'automa a pila che è stato introdotto all'inizio della lezione è un modello computazionale che ha senso nell'ambito della modellazione di sistemi reali; nonostante ciò, come già accaduto per gli automi a stati finiti, dal punto di vista dello studio dell'informatica teorica tale modello ha un'utilità più limitata rispetto agli accettori ed ai trasduttori. Il motivo va cercato nell'impossibilità dell'automa a pila di accettare o meno le stringhe di simboli del nastro d'ingresso. In questa parte della lezione ci occuperemo quindi dell'estensione dell'automa a pila conosciuta come accettore.

Prima di presentare un paio esempi applicativi di questo modello computazionale vale la pena di discuterne il funzionamento: visto che l'obiettivo dell'accettore a pila è il riconoscimento delle stringhe è il caso di indagare come tale operazione venga svolta. A tal proposito può essere utile immaginare l'accettore a pila come una macchina, rappresentata schematicamente nell'immagine seguente.

Come l'automa a pila, anche l'accettore opera sulla base di un ciclo di lavoro che si ripete indefinitamente. Il ciclo di lavoro che caratterizza l'accettore è quasi identico a quello dell'automa a pila; fa eccezione un semplice controllo, svolto a fine ciclo, circa l'accettazione o meno della stringa inizialmente presente in ingresso. Nel dettaglio, il ciclo di lavoro è il seguente:

1. lettura di un simbolo dal nastro d'ingresso;
2. lettura di un simbolo dalla memoria a pila;
3. determinazione dello stato prossimo;
4. scrittura di una stringa di simboli sulla pila;
5. segnalazione dell'accettazione.

La segnalazione dell'accettazione avviene solamente dopo aver letto tutta la stringa in ingresso; come vedremo, questo formalismo prevede due diversi meccanismi di accettazione, di cui rimandiamo per ora ogni approfondimento.

Alla luce di queste considerazioni possiamo ora definire le caratteristiche di questo modello computazionale.

Definizione di automa accettore a pila

Formalmente, un automa accettore a pila è una settupla ordinata $P=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F)$, dove:

• $Q$ è un insieme finito di stati;
• $I$ è un insieme finito di simboli detto alfabeto d'ingresso;
• $\Gamma$ è un insieme finito di simboli tale che $\Gamma \cap I=\emptyset$ detto alfabeto della pila;
• $\delta :Q\times I\cup \left\{\epsilon \right\}\times \Gamma \rightarrow Q\times \Gamma ^{*}$ è la funzione di transizione;
• $q_{0}\in Q$ è lo stato iniziale;
• $Z_{0}\in \Gamma$ è il simbolo iniziale della pila;
• $F\subseteq Q$ è l'insieme degli stati di accettazione.

Utilizzando i primi sei elementi proposti dalla definizione è possibile costruire un automa a pila $A=(Q,I,\Gamma ,\delta ,q_{0},Z_{0})$, detto automa soggiacente all'accettore.

Esempi di automi accettori

Ora che abbiamo posto la definizione di accettore a pila è utile presentare un paio di esempi, in modo da poter comprendere meglio le differenze esistenti tra questo nuovo modello computazionale e quelli presentati all'inizio del corso.

Esempio 1: il linguaggio $a^{n}b^{n}$

Questo esempio, oltre ad offrirci la possibilità di esaminare la logica con cui operano gli accettori a pila, ha valore teorico; in precedenza abbiamo infatti dimostrato che gli accettori a stati finiti non sono in grado di riconoscere il linguaggio proposto, mentre vedremo che gli accettori a pila possono.

Prima di fornire una descrizione dettagliata dell'accettore a pila è necessario offrire una definizione più rigorosa del linguaggio che analizzeremo. Si consideri quindi l'alfabeto $I=\left\{a,b\right\}$ ed il linguaggio formale $L=\left\{a^{n}b^{n}|n>0\right\}$. Definiamo gli elementi costitutivi dell'automa accettore a pila che riconosce le stringhe di questo linguaggio.

Insieme degli stati, stato iniziale e stati finali

L'insieme degli stati è composto da tre elementi:

• $q_{0}$: è dedicato al conteggio dei simboli $a$;
• $q_{1}$: è dedicato al confronto fra i simboli $b$ ed i simboli impilati nello stato $q_{0}$;
• $q_{2}$: viene utilizzato per confermare l'accettazione della stringa.

Possiamo quindi formare l'insieme $Q=\left\{q_{0},q_{1},q_{2}\right\}$, lo stato $q_{0}$ è lo stato iniziale dell'automa mentre l'insieme degli stati finali è $F=\left\{q_{2}\right\}$.

Alfabeto d'ingresso

In questo caso l'alfabeto d'ingresso è dato dall'insieme $I=\left\{a,b\right\}$.

Alfabeto della pila

L'alfabeto della pila è composto da due simboli: uno è $Z_{0}$ mentre l'altro è $N$ e viene utilizzato per contare i simboli $a$. Formalmente: $\Gamma =\left\{N,Z_{0}\right\}$.

Funzione di transizione

Come per il caso dell'esempio riguardante l'inscatolamento dei flaconi di sciroppo, la funzione di transizione verrà descritta tramite il grafo. Formalmente possiamo scrivere $G_{delta}=\left\{((q_{0},a,Z_{0});(q_{0},NZ_{0})),((q_{0},a,N);(q_{0},NN),((q_{0},b,N);(q_{1},\epsilon )),((q_{1},b,N);(q_{1},\epsilon )),((q_{1},\epsilon ,Z_{0});(q_{2},Z_{0}))\right\}$.

La tabella sottostante propone una versione più leggibile del grafo della funzione di transizione.

Numero transizione	Argomento	Immagine
1	$(q_{0},a,Z_{0})$	$(q_{0},NZ_{0})$
2	$(q_{0},a,N)$	$(q_{0},NN)$
3	$(q_{0},b,N)$	$(q_{1},\epsilon )$
4	$(q_{1},b,N)$	$(q_{1},\epsilon )$
5	$(q_{1},\epsilon ,Z_{0})$	$(q_{2},Z_{0})$

Anche in questo caso forniamo una descrizione per le transizioni.

La transizione numero 1 serve per contare la prima occorrenza del simbolo $a$, ponendo una $N$ sulla pila.

La transizione numero 2 conta le successive occorrenze del simbolo $a$, inserendo una $N$ sulla pila per ognuna di esse.

La transizione numero 3 rileva la prima occorrenza del simbolo $b$ e toglie una $N$ dalla pila.

La transizione numero 4 rileva le successive occorrenze del simbolo $b$ e toglie una $N$ dalla pila per ognuna di esse.

La transizione numero 5, infine, porta l'accettore nello stato finale; le condizioni affinché questa transizione venga attivata sono due: non si legge alcun simbolo dal nastro d'ingresso e la pila deve contenere solamente il simbolo $Z_{0}$.

Diagramma degli stati

L'immagine sottostante mostra il diagramma degli stati per l'automa a pila che riconosce il linguaggio.

Esaminando il diagramma degli stati si può risalire al principio di funzionamento dell'automa: ogni volta che viene incontrata una $a$ l'accettore aggiunge un simbolo alla pila, finché viene incontrata la prima occorrenza della $b$; da quel momento in poi, ogni volta che viene incontrata una $b$ l'accettore toglie un simbolo dalla pila, finché non si arriverà a svuotare la pila.

Quando la pila sarà vuota e non ci saranno più simboli in ingresso la stringa sarà accettata.

Esempio 2: il linguaggio $wcw^{R}$

Anche in questo caso esaminiamo un linguaggio che non può essere riconosciuto dagli accettori a stati finiti.

Considerando l'alfabeto $I=\left\{a,b,c\right\}$, il linguaggio formale in questione sarà $L=\left\{wcw^{R}|{\text{w è una stringa composta da simboli a e b, eventualmente vuota}}\right\}$.

Il principio di funzionamento dell'automa è il seguente: inizialmente, per ogni simbolo letto dal nastro d'ingresso viene aggiunto un corrispondente simbolo sulla pila. Dopo aver incontrato il simbolo $c$, l'automa confronta ogni simbolo d'ingresso con il simbolo presente sulla pila e, in caso di riscontro positivo, toglie il simbolo dalla pila. Quando la pila è completamente vuota l'automa accetta la stringa. Gli elementi costitutivi dell'accettore a pila che riconosce il linguaggio dato sono elencati di seguito.

Insieme degli stati, stato iniziale e stati finali

L'automa è dotato di cinque stati:

• $q_{0}$: in questo stato si avvia il riempimento della pila;
• $q_{1}$: questo stato è pensato per trattare le occorrenze del simbolo $a$;
• $q_{2}$: questo stato tratta le occorrenze del simbolo $b$;
• $q_{3}$: questo stato rileva la ricezione del simbolo $c$ ed inizia la fase di confronto;
• $q_{4}$: questo stato segnala l'accettazione della stringa.

L'insieme degli stati è $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4}\right\}$. Lo stato $q_{0}$ è lo stato iniziale. Questo automa non dispone di stati finali, pertanto $F=\emptyset$; il fatto che un accettore sia sprovvisto di stati di accettazione sembra strano ma come vedremo ha una sua giustificazione.

Alfabeto d'ingresso

L'alfabeto d'ingresso è $I=\left\{a,b,c\right\}$.

Alfabeto della pila

L'alfabeto della pila contiene tre elementi: il simbolo $Z_{0}$, il simbolo $A$ utilizzato per contare le $a$ ed il simbolo $B$ utilizzato per contare le $b$.

Funzione di transizione

Come di consueto la funzione di transizione verrà descritta attraverso il suo grafo, visibile nella tabella sottostante.

Numero transizione	Argomento	Immagine
1	$(q_{0},a,Z_{0})$	$(q_{1},AZ_{0})$
2	$(q_{0},b,Z_{0})$	$(q_{2},BZ_{0})$
3	$(q_{0},c,Z_{0})$	$(q_{3},Z_{0})$
4	$(q_{1},a,A)$	$(q_{1},AA)$
5	$(q_{1},b,A)$	$(q_{2},BA)$
6	$(q_{1},c,A)$	$(q_{3},A)$
7	$(q_{2},a,B)$	$(q_{1},AB)$
8	$(q_{2},b,B)$	$(q_{2},BB)$
9	$(q_{2},c,B)$	$(q_{3},B)$
10	$(q_{3},a,A)$	$(q_{3},\epsilon )$
11	$(q_{3},b,B)$	$(q_{3},\epsilon )$
12	$(q_{3},\epsilon ,Z_{0})$	$(q_{4},\epsilon )$

Come di consueto proponiamo una succinta descrizione delle transizioni.

Le prime due transizioni servono per mettere il primo elemento sulla pila, mentre la transizione numero tre, che passa direttamente al controllo del simbolo $c$, serve per includere il caso in cui $w=\epsilon$.

Le transizioni numero 4, 5, 7 e 8 descrivono il comportamento dell'automa all'arrivo dei simboli $a$ e $b$, in relazione ai simboli presenti nella pila.

Le transizioni 6 e 9 riguardano il riconoscimento del simbolo $c$ ed il passaggio alla fase di confronto.

Le transizioni numero 10 e numero 11 riguardano il confronto dei simboli ricevuti in ingresso con quelli presenti sulla pila.

Infine la dodicesima transizione serve per indicare l'accettazione della stringa.

Diagramma degli stati

Il diagramma degli stati per l'accettore che stiamo discutendo è visibile qui sotto.

Questo accettore presenta senza dubbio alcune caratteristiche insolite: la prima, molto evidente, è la mancanza di stati di accettazione. La seconda è un po' meno palese ma comunque molto importante e coinvolge la transizione tra gli stati $q_{3}$ e $q_{4}$.

La transizione si effettua senza leggere simboli dal nastro d'ingresso, quando sulla pila è presente solo il simbolo $Z_{0}$; l'aspetto curioso riguarda la mossa prevista dall'automa, cioè un cambiamento di stato e la rimozione del simbolo $Z_{0}$.

Questi comportamenti, per ora controintuitivi, troveranno piena spiegazione quando discuteremo le strategie di accettazione di questa classe di automi.

Configurazione di un accettore a pila

L'obiettivo degli accettori a pila è quello di riconoscere stringhe di simboli opportunamente strutturate; come conseguenza, chi usa questo tipo di automa è interessato ai risultati che esso può produrre.

Uno degli aspetti che caratterizzano l'impiego di questi automi è la necessità di dimostrare che essi siano effettivamente in grado di riconoscere il particolare linguaggio per cui sono stati concepiti.

Le tecniche di dimostrazione associate agli accettori a pila analizzano il comportamento del formalismo durante la computazione; è dunque molto importante saper descrivere lo stato generale dell'accettore durante la procedura di accettazione. A tal proposito è utile introdurre il concetto di configurazione di un automa accettore.

Dato un accettore a pila $P=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F)$ ed una terna ordinata di elementi $c=(q\in Q,x\in I^{*},\gamma \in \Gamma ^{*})$, diciamo che $c$ è una configurazione dell'accettore $P$.

Esistono due tipi particolari di configurazioni: iniziali e finali. Le configurazioni iniziali indicano l'inizio di una computazione e saranno quindi composte dallo stato iniziale, dall'intera stringa di simboli da interpretare e dalla pila vuota: $(q_{0},x,Z_{0})$. Le configurazioni finali possono assumere due forme: $(q,\epsilon ,\gamma )$ oppure $(q,\epsilon ,\epsilon )$; il motivo per cui esistono due diverse tipologie di configurazioni finali verrà chiarito nella sezione successiva.

Transizione in un accettore a pila

Dato un accettore a pila $P=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F)$, possiamo immaginare di raccogliere in un insieme tutte le possibili configurazioni ad esso associate. Su tale insieme è possibile definire una relazione binaria chiamata transizione; in generale, due configurazioni possono essere in relazione di transizione o a causa del consumo di un simbolo dal nastro d'ingresso, oppure senza il consumo del simbolo stesso.

Consideriamo ora due configurazioni $c_{1}=(q_{1},x_{1},p\gamma _{1})$ e $c_{2}=(q_{2},x_{2},\gamma _{2})$. Diremo che le due configurazioni sono in relazione di transizione a causa del consumo di un simbolo d'ingresso quando si verificano le seguenti condizioni:

• $x_{1}=ax_{2}$, dove $a\in I$ rappresenta il simbolo che viene consumato;
• $\gamma _{2}=\beta \gamma _{1}$, dove $\beta \in \Gamma ^{*}$ ;
• $\delta (q_{1},a,p)=(q_{2},\gamma _{2})$.

Diremo invece che le due configurazioni sono in relazione di transizione senza il consumo di un simbolo d'ingresso quando si verificano le seguenti condizioni:

• $x_{2}=x_{1}$;
• $\gamma _{2}=\beta \gamma _{1}$, dove $\beta \in \Gamma ^{*}$ ;
• $\delta (q_{1},\epsilon ,p)=(q_{2},\gamma _{2})$.

Quando le due configurazioni saranno in relazione si scriverà $c_{1}\vdash c_{2}$ oppure $c_{1}\vdash _{P}c_{2}$; la seconda notazione si utilizza per sottolineare che la relazione riguarda specificamente l'automa $P$.

Il significato della relazione binaria appena introdotta è riconducibile a quello normalmente associato all'idea di transizioni: le tre condizioni imposte, infatti, riguardano il consumo di un simbolo dal nastro d'ingresso, un'alterazione del contenuto della pila che può anche non avere atto ($\beta$ potrebbe essere la stringa vuota) ed un cambiamento di stato che avvenga in accordo con il simbolo letto ed il contenuto della pila dato.

In questo contesto la transizione è per definizione una relazione binaria ed è quindi pensata per stabilire un nesso tra due configurazioni consecutive; ha senso estendere la validità di tale operatore, in modo che sia possibile mettere in relazione un numero maggiore (o perfino arbitrario) di configurazioni. Per tale scopo sono state concepite due estensioni: la transizione n-aria e la chiusura riflessiva e transitiva della transizione, brevemente discusse in seguito.

La transizione n-aria è normalmente indicata con la notazione $c_{1}\vdash ^{n}c_{n}$: secondo questa notazione, esistono $n-2$ configurazioni $c_{2},c_{3},...,c_{n-1}$ in modo che tra due configurazioni consecutive esista sempre una relazione di transizione. Formalmente scriveremo: $\exists c_{2},c_{3},...,c_{n-1}|\forall i\in \mathbb {N} ,0<i<n,c_{i}\vdash c_{i+1}$. Il significato della transizione n-aria é molto intuitivo: indica la successione di configurazioni attraversate dall'accettore a pila durante il riconoscimento di una porzione della stringa d'ingresso lunga $n$ simboli.

Un altro modo per estendere la relazione binaria di transizione consiste nell'utilizzo della sua chiusura riflessiva e transitiva, che permette di rappresentare successioni di configurazioni aventi lunghezza arbitraria. Più precisamente, date due configurazioni $c$ e $d$, la scrittura $c\vdash ^{*}d$ indica che esiste una successione finita di configurazioni $c_{1}...c_{n}$ tali che per ogni coppia consecutiva di configurazioni vale la relazione di transizione binaria. Formalmente potremo scrivere: $\exists n\in \mathbb {N} ,\exists c_{1},c_{2},...,c_{n}|\forall i\in \mathbb {N} ,0<i<n,c_{i}\vdash c_{i+1}$; valgono inoltre le relazioni $c\vdash c_{1}$ e $c_{n}\vdash d$.

Computazione in un accettore a pila

La computazione è una successione finita di configurazioni $c_{0},c_{1},...,c_{n}$ tali che $c_{0}\vdash ^{*}c_{n}$.

Il concetto di computazione è particolarmente prezioso per dimostrare le proprietà formali degli accettori a pila in quanto consente di descrivere, attraverso le configurazioni, il modo in cui l'accettore evolve durante la lettura del nastro d'ingresso.

Prendendo come riferimento il testo di Ullman, Hopcroft e Motwani, riportiamo tre proprietà delle computazioni che sono particolarmente utili nelle dimostrazioni riguardanti gli accettori a pila:

1. Consideriamo una computazione $(q_{1},x_{1},\gamma _{1})\vdash ^{*}(q_{2},x_{2},\gamma _{2})$ che sia valida per l'accettore a pila considerato. La computazione che si ottiene da quella data aggiungendo una generica stringa $s\in I^{*}$ alle due stringhe d'ingresso è anch'essa valida;
2. Consideriamo una computazione $(q_{1},x_{1},\gamma _{1})\vdash ^{*}(q_{2},x_{2},\gamma _{2})$ che sia valida per l'accettore a pila considerato. La computazione che si ottiene da quella data aggiungendo una generica stringa $\beta \in \Gamma ^{*}$ alle due pile è anch'essa valida;
3. Consideriamo una computazione $(q_{1},xz,\gamma _{1})\vdash ^{*}(q_{2},yz,\gamma _{2})$ che sia valida per l'accettore a pila considerato. La computazione che si ottiene da quella data togliendo il suffisso $z$ dalle due stringhe d'ingresso è anch'essa valida.

Analizziamo ora le tre proprietà per comprenderne il significato.

La prima proprietà ci offre la possibilità di estendere la stringa d'ingresso di tutte le configurazioni coinvolte in una computazione aggiungendo un'arbitraria stringa $s$; svolgendo questa operazione si otterrà una nuova computazione $(q_{1},x_{1}s,\gamma _{1})\vdash ^{*}(q_{2},x_{2}s,\gamma _{2})$.

La seconda proprietà è molto simile alla prima ma agisce sulla pila anziché sulla stringa. La computazione che si ottiene applicando la proprietà sarà quindi $(q_{1},x_{1},\gamma _{1}\beta )\vdash ^{*}(q_{2},x_{2},\gamma _{2}\beta )$.

La terza proprietà ci dà la possibilità di eliminare da tutte le stringhe d'ingresso delle configurazioni coinvolte in una computazione un suffisso che è comunque presente in tutte le stringhe e che non viene consumato; la computazione che si ottiene in questo caso è $(q_{1},x,\gamma _{1})\vdash ^{*}(q_{2},y,\gamma _{2})$.

Accettazione nei riconoscitori a pila

Negli automi a pila l'accettazione di una stringa può avvenire in due modi:

1. accettazione per stato finale: dopo aver consumato tutti i simboli della stringa d'ingresso, l'accettore si trova in uno stato $q\in F$;
2. accettazione per pila vuota: l'automa a pila termina la lettura dei simboli in ingresso avendo completamente svuotato la pila.

I due diversi meccanismi di accettazione giustificano l'esistenza di due tipologie di configurazioni finali.

Disporre di due diverse strategie per il riconoscimento delle stringhe può essere vantaggioso in quanto offre al progettista la possibilità di scegliere la più adatta alle stringhe da accettare. Affinché questa opportunità possa essere sfruttata liberamente è però necessario dimostrare che le due forme di accettazione sono equivalenti; la presenza di differenze è evidente: basti pensare che negli automi che accettano per pila vuota non ha senso parlare di stati finali, dunque in tal caso $F=\emptyset$.

Questa considerazione permette di contestualizzare il problema dell'accettazione nei riconoscitori a pila: consideriamo un accettore a pila $P=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F)$ che riconosce le stringhe d'ingresso per stato finale; consideriamo poi il linguaggio $L$ riconosciuto da $P$. Supponendo di essere certi che i due meccanismi di accettazione siano equivalenti, esisterà un automa $P_{2}$ in grado di accettare $L$ utilizzando l'accettazione per pila vuota; naturalmente, da un punto di vista strutturale i due automi saranno diversi: $P\neq P_{2}$.

Affrontiamo ora la questione dell'accettazione parlando anzitutto dei linguaggi riconosciuti dagli accettori a pila.

Linguaggio riconosciuto da un accettore a pila

Il concetto di accettazione è di fondamentale importanza in quanto sulla base dei criteri di accettazione si stabilisce il linguaggio riconosciuto dall'accettore.

Questo aspetto diventa particolarmente delicato nel caso degli automi accettori a pila in quanto esistono due diversi criteri di accettazione delle stringhe. Per capire dov'è il problema consideriamo un accettore a pila $P=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F)$ che accetta le stringhe per stato finale; dunque in questo caso $F\neq \emptyset$.

È possibile che durante l'accettazione di una stringa la pila dell'automa si svuoti: in questo caso sarebbero verificate le condizioni di accettazione per pila vuota. Non solo: in generale, gli stati in cui la pila è vuota non sono quelli di accettazione. Queste osservazioni ci portano a concludere che gli accettori a pila strutturati come $P$ siano in grado di riconoscere due linguaggi: uno per stato di accettazione ed uno per pila vuota. In generale, inoltre, i due linguaggi non coincidono e possiamo concludere che per ogni accettore a pila $P$ esistono due linguaggi differenti. Seguendo la notazione del testo di Hopcroft, Ullman e Motwani indicheremo con $L(P)$ il linguaggio riconosciuto dall'automa $P$ per stati finali e con $N(P)$ il linguaggio riconosciuto dall'automa $P$ per pila vuota.

Formalmente potremo scrivere quanto segue:

• $L(P)=\left\{w\in I^{*}|(q_{0},w,Z_{0})\vdash ^{*}(q,\epsilon ,\alpha ),q\in F,\alpha \in \Gamma ^{*}\right\}$;
• $N(P)=\left\{w\in I^{*}|(q_{0},w,Z_{0})\vdash ^{*}(q,\epsilon ,\epsilon )\right\}$.

Il fatto che i due linguaggi riconosciuti dall'accettore siano differenti potrebbe essere un problema se si scoprisse che appartengono a categorie differenti, ad esempio uno regolare e l'altro no; è quindi importante dimostrare che i due linguaggi appartengono alla medesima categoria. Un modo per mostrare l'equivalenza tra le categorie dei due linguaggi consiste nel dimostrare due risultati:

• per ogni linguaggio riconosciuto per pila vuota è possibile costruire un accettore a pila che lo riconosce per stati finali;
• per ogni linguaggio riconosciuto per stati finiti è possibile costruire un accettore a pila che lo riconosce per pila vuota.

Dimostrazione delle proprietà degli accettori a pila

La progettazione di un accettore a pila è un processo che coinvolge una grande quantità di aspetti intuitivi; dato che l'obiettivo dell'accettore è il riconoscimento di stringhe dotate di struttura opportuna è bene che le intuizioni vengano confermate attraverso un processo rigoroso di dimostrazione.

In linea di principio le dimostrazioni legate agli accettori a pila sfruttano due strumenti:

• la funzione di transizione, che come abbiamo visto rappresenta il programma dell'accettore a pila;
• i concetti di configurazione, transizione e computazione che abbiamo analizzato in precedenza, insieme alle loro proprietà.

Dimostrare che un accettore a pila è effettivamente in grado di riconoscere un preciso linguaggio significa sottoporre a verifica il programma svolto dall'automa, una buona alternativa ad estenuanti sessioni di debug. Come vedremo più avanti l'informatica teorica sviluppa una serie di strumenti che possono essere impiegati per la verifica delle proprietà formali del programmi, un aspetto forse troppo sottovalutato nella comunità degli sviluppatori.

Dimostriamo ora che l'accettore a pila pensato per riconoscere il linguaggio $L=\left\{a^{n}b^{n},n>0\right\}$ accetta solo ed esclusivamente stringhe dotate della struttura richiesta

Riconoscimento del linguaggio $a^{n}b^{n}$

Per provare che l'accettore a pila proposto nell'esempio è in grado di riconoscere il linguaggio dato è necessario dimostrare che una stringa $s$ è riconosciuta per stato finale dall'automa a pila dato se e solo se la stringa $s$ è nella forma $a^{n}b^{n}$. Tale dimostrazione va divisa in due parti:

1. se $s$ è nella forma $a^{n}b^{n}$, allora l'automa dato accetta la stringa per stato finale;
2. se l'automa dato accetta la stringa per stato finale, allora $s$ è nella forma $a^{n}b^{n}$.

Prima implicazione - per dimostrare questo caso è sufficiente provare che, data una stringa $s=a^{n}b^{n}$ con $n$ positivo, l'automa termina il riconoscimento della stringa nell'unico stato di accettazione disponibile; un buon modo per raggiungere questo obiettivo è presentare la computazione associata alla stringa data.

$(q_{0},a^{n}b^{n},Z_{0})\vdash ^{*}(q_{0},b^{n},N^{n}Z_{0})\vdash ^{*}(q_{1},\epsilon ,Z_{0})\vdash (q_{2},\epsilon ,Z_{0})$

Tale computazione può essere ricostruita a partire dalla funzione di transizione dell'automa a pila.

Seconda implicazione - In questo caso conviene procedere per induzione, considerando una generica stringa d'ingresso $s=s_{1}s_{2}...s_{2n}$ accettata per stato finale dall'automa a pila e dimostrando che la stringa deve necessariamente avere la struttura richiesta.

Procediamo con ordine, dimostrando anzitutto il passo base.

Dato che per le caratteristiche del linguaggio dato deve essere $n>0$, consideriamo come caso base quello per cui $n=1$. Stando all'impostazione data, dev'essere $s=s_{1}s_{2}$, dove $s_{1}\in I,s_{2}\in I$.

Visto che la stringa è per ipotesi riconosciuta dall'automa, deve esistere una computazione $(q_{0},s_{1}s_{2},Z_{0})\vdash ^{*}(q_{2},\epsilon ,Z_{0})$.

Procediamo a ritroso dalla configurazione finale: consultando la funzione di transizione si scopre che l'unico modo per arrivare in $(q_{2},\epsilon ,Z_{0})$ è passare per $(q_{1},\epsilon ,Z_{0})$.

Retrocedendo ancora di un passo, l'unica possibilità è quella che prevede di elaborare l'ultimo simbolo in ingresso: $(q_{1},s_{2},NZ_{0})$; in questa configurazione, l'unica azione possibile consiste nella rimozione del simbolo $N$ dalla pila, cosa che potrebbe accadere solamente se il simbolo $s_{2}$ fosse una $b$.

Domandiamoci ora quale simbolo della stringa ha posto quel particolare simbolo $N$ sulla pila: dev'essere stato per forza $s_{1}$ che a questo punto deve necessariamente essere una $a$.

Dunque $s=ab$ ed il passo base è dimostrato.

Dimostriamo a questo punto il passo induttivo. Il nostro obiettivo è provare, che se la stringa $w=a^{n}b^{n}$ è accettata dall'automa a pila che stiamo studiando, allora lo sarà anche la stringa $s=a^{n+1}b^{n+1}$. Notiamo anzitutto che $|w|=2n$ e che $|s|=2n+2$; in particolare, grazie a quest'ultima osservazione possiamo scrivere $s=s_{1}s_{2}...s_{2n+2}$, dove $s_{i}\in I$.

Analizziamo ora il comportamento dell'accettore a pila durante la lettura del nastro d'ingresso, soffermandoci su due punti essenziali:

• la lettura del primo carattere provoca la transizione $(q_{0},s_{1}s_{2}...s_{2n+2},Z_{0})\vdash (q_{0},s_{2}...s_{2n+2},NZ_{0})$; questa transizione può avere luogo solamente se $s_{1}=a$;
• al termine della computazione l'accettore si troverà nella configurazione $(q_{2},\epsilon ,Z_{0})$ che è raggiungibile solamente dalla configurazione $(q_{1},\epsilon ,Z_{0})$: $(q_{1},\epsilon ,Z_{0})\vdash (q_{2},\epsilon ,Z_{0})$.

A seguito di queste considerazioni, la computazione che accetta la stringa $s$ è la seguente:

$(q_{0},s_{1}s_{2}...s_{2n+2},Z_{0})\vdash (q_{0},s_{2}...s_{2n+2},NZ_{0})\vdash ^{*}(q_{1},\epsilon ,Z_{0})\vdash (q_{2},\epsilon ,Z_{0})$

Per arrivare alla configurazione $(q_{1},\epsilon ,Z_{0})$ l'unica possibilità è avere una configurazione di provenienza $(q_{1},b,NZ_{0})$ dove il simbolo $b$ rappresenta l'ultimo carattere della stringa, che nel nostro caso è $s_{2n+2}$. Possiamo concludere che $(q_{1},s_{2n+2},NZ_{0})\vdash (q_{1},\epsilon ,Z_{0})$. Affinché la transizione venga effettivamente svolta è necessario che $s_{2n+2}=b$. Inserendo queste osservazioni nella computazione precedente otteniamo quanto segue:

$(q_{0},s_{1}s_{2}...s_{2n+2},Z_{0})\vdash (q_{0},s_{2}...s_{2n+2},NZ_{0})\vdash ^{*}(q_{1},s_{2n+2},NZ_{0})\vdash (q_{1},\epsilon ,Z_{0})\vdash (q_{2},\epsilon ,Z_{0})$

Concentriamoci ora sulla parte della computazione che sfrutta la chiusura riflessiva e transitiva della relazione di transizione:

$(q_{0},s_{2}...s_{2n+2},NZ_{0})\vdash ^{*}(q_{1},s_{2n+2},NZ_{0})$

Si può notare che il simbolo $s_{2n+2}$ è presente in tutte le configurazioni della computazione e pertanto, per la prima proprietà delle computazioni, può essere rimosso. Otteniamo quindi:

$(q_{0},s_{2}...s_{2n+1},NZ_{0})\vdash ^{*}(q_{1},\epsilon ,NZ_{0})$

A questo punto vale la pena di riflettere sulla stringa $s_{2}...s_{2n+1}$: la sua lunghezza è $2n$ ed è strutturata in modo da lasciare inalterato il contenuto della pila; per come è strutturato l'accettore, questo può succedere solamente aggiungendo $n$ volte il simbolo $N$ sulla pila per poi rimuoverlo per $n$ volte. La stringa lunga $2n$ può solo essere $a^{n}b^{n}$; a questo punto sappiamo che il primo simbolo della stringa $s$ è $a$, che l'ultimo simbolo è $b$ e che la parte centrale della stringa è $a^{n}b^{n}$; concatenando le parti si ottiene $s=a\cdot a^{n}b^{n}\cdot b=a^{n+1}b^{n+1}$.

Il risultato è quindi dimostrato.

Trasduttore a pila

L'ultima estensione dell'automa a pila che introdurremo sarà il trasduttore; per analogia con il caso dei trasduttori a stati finiti possiamo pensarlo come un dispositivo in grado di trasformare le stringhe ricevute in ingresso, appartenenti ad un linguaggio, in stringhe in uscita appartenenti ad un linguaggio differente.

La necessità di definire un trasduttore a pila risiede nel fatto che questa categoria di modelli computazionali è in grado di riconoscere un insieme di linguaggi più ampio rispetto al caso degli automi a stati finiti; disponendo di una gamma di linguaggi più vasta è una buona idea avere la possibilità di tradurli.

Immaginando il modello computazionale come una macchina, il trasduttore a pila potrebbe assomigliare allo schema seguente.

Come si può notare il dispositivo è composto da quattro elementi:

• un'unità di controllo;
• un nastro di ingresso;
• un nastro della pila;
• un nastro di uscita.

L'unità di controllo dispone di tre testine, una per ogni nastro; in particolare:

• la testina d'ingresso può leggere e può muoversi solo verso sinistra;
• la testina della pila può leggere, scrivere e muoversi nelle due direzioni;
• la testina di uscita può scrivere e può muoversi solo verso sinistra.

Questi dispositivi vengono gestiti dall'unità di controllo secondo uno schema prefissato che costituisce il ciclo di lavoro del trasduttore a pila. Vediamo quali sono le fasi che lo caratterizzano:

1. lettura di un simbolo dal nastro d'ingresso;
2. lettura di un simbolo dalla memoria a pila;
3. determinazione dello stato prossimo;
4. scrittura di una stringa di simboli sulla pila;
5. scrittura di una stringa di simboli sul nastro di uscita;
6. segnalazione dell'accettazione.

L'unica novità è qui rappresentata dalla scrittura sul nastro d'uscita: si tratta di un'operazione in cui l'unità di controllo scrive in una delle caselle del nastro d'uscita un carattere della stringa da stampare, quindi sposta la testina di uscita alla casella successiva e ripete queste operazioni fino al termine della stringa da produrre.

Un aspetto che merita di essere sottolineato è la significatività della stringa presente sul nastro d'uscita: affinché i simboli riportati siano validi è necessario che l'automa termini la computazione in uno stato di accettazione; negli altri casi il contenuto del nastro d'uscita non va preso in considerazione.

Dopo questa generica descrizione è possibile offrire una definizione più formale del trasduttore a pila.

Definizione di trasduttore a pila

Un automa trasduttore a pila è una 9-upla ordinata di elementi $T=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F,O,\eta )$ dotati del seguente significato:

• $Q$ è un insieme finito di stati;
• $I$ è un insieme finito di simboli che rappresenta l'alfabeto d'ingresso;
• $\Gamma$ è un insieme finito di simboli che rappresenta l'alfabeto della pila, tale che $\Gamma \cap I=\emptyset$;
• $\delta :Q\times I\cup \left\{\epsilon \right\}\times \Gamma \rightarrow Q\times \Gamma ^{*}$ è la funzione di transizione;
• $q_{0}$ è lo stato iniziale;
• $F\subseteq Q$ è l'insieme degli stati finali;
• $O$ è un insieme finito di simboli che rappresenta l'alfabeto d'uscita;
• $\eta :Q\times I\cup \left\{\epsilon \right\}\times \Gamma \rightarrow O^{*}$ è la funzione di uscita.

È importante precisare che le funzioni di transizione e di uscita non solo hanno il medesimo insieme di partenza ma sono in realtà definite per gli stessi valori degli argomenti. L'accettore a stati finiti $A=(Q,I,\Gamma ,\delta ,q_{0},Z_{0},F)$ che si ottiene a partire dagli elementi del trasduttore si chiama accettore soggiacente a $T$.

Dopo aver proposto la definizione formale di trasduttore a pila, presentiamo un esempio che impiega tale modello computazionale per la traduzione di linguaggi.

Esempio: traduzione tra linguaggi formali

Consideriamo gli alfabeti $I=\left\{a,b\right\}$ e $O=\left\{f,g\right\}$; a partire da essi è possibile generare i due linguaggi $L_{1}=\left\{a^{n}b^{n},n>0\right\}$ e $L_{2}=\left\{f^{2n}g^{3n},n>0\right\}$. Vogliamo fare in modo di tradurre ogni stringa $s_{1}\in L_{1}$ in una stringa $s_{2}\in L_{2}$; dato che i linguaggi scelti non sono regolari non è possibile svolgere questo compito impiegando un trasduttore a stati finiti, quindi costruiremo un trasduttore a pila.

I primi sette elementi del trasduttore che vogliamo costruire sono gli stessi che abbiamo presentato nell'esempio riguardante l'automa che riconosce il linguaggio $L_{1}$; per questo motivo vale la pena di concentrarsi esclusivamente sulla funzione di uscita.

La funzione di uscita

Come abbiamo sottolineato la funzione di uscita è definita esattamente sugli stessi argomenti della funzione di transizione, quindi un modo efficace per rappresentarla è la consueta tabella che riporta il grafo della funzione stessa. La traduzione richiesta ha le seguenti due caratteristiche:

• per ogni simbolo $a\in I$ vengono prodotti due simboli $f\in O$;
• per ogni simbolo $b\in I$ vengono prodotti tre simboli $g\in O$.

La tabella che descrive il grafo della funzione di uscita per il trasduttore che ci interessa è riportata di seguito.

Numero transizione	Argomento	Immagine
1	$(q_{0},a,Z_{0})$	$ff$
2	$(q_{0},a,N)$	$ff$
3	$(q_{0},b,N)$	$ggg$
4	$(q_{1},b,N)$	$ggg$
5	$(q_{1},\epsilon ,Z_{0})$	$\epsilon$

Diagramma degli stati

Dato che il trasduttore ha la possibilità di scrivere sul nastro di uscita durante le transizioni, il diagramma degli stati deve necessariamente riflettere questa caratteristica. In effetti, ogni arco del diagramma sarà etichettato tramite la dicitura $a,B/c,D$, dove:

• $a\in I$ è il simbolo letto dal nastro d'ingresso;
• $B\in \Gamma$ è il simbolo letto dalla cima della pila;
• $c\in O^{*}$ è la stringa di simboli dell'alfabeto d'uscita che viene copiata sul nastro d'uscita;
• $D\in \Gamma ^{*}$ è la stringa di simboli della pila che vengono copiati sul nastro della pila.

L'immagine sottostante mostra il diagramma degli stati per il trasduttore a pila che abbiamo progettato.

Configurazioni, transizioni e computazioni nei trasduttori a pila

Rispetto all'accettore a pila il trasduttore dispone di un dispositivo in più, il nastro di uscita; la sua presenza altera la struttura della configurazione, concetto introdotto per descrivere lo stato del dispositivo.

Definiamo quindi configurazione per un trasduttore a pila una quadrupla ordinata di elementi $(q,x,\alpha ,y)$, dove $q\in Q,x\in I^{*},\alpha \in \Gamma ^{*},y\in O^{*}$.

Le modifiche apportate alla configurazione influenzano il concetto di transizione, che va a sua volta esteso; si consideri pertanto due configurazioni $c_{1}=(q_{1},x_{1},\alpha \gamma _{1},y_{1})$ e $c_{2}=(q_{2},x_{2},\gamma _{2},y_{2})$.

Anche nel caso dei trasduttori la transizione può avvenire con consumo di un simbolo d'ingresso oppure senza; questa considerazione porta a definire la relazione di transizione in due modi differenti. Più precisamente diciamo che le due configurazioni $c_{1}$ e $c_{2}$ sono in relazione di transizione con consumo di un simbolo d'ingresso quando si verificano le seguenti condizioni:

• $x_{1}=ax_{2}$, dove $a\in I$ rappresenta il simbolo che viene consumato;
• $\gamma _{2}=\beta \gamma _{1}$, dove $\beta \in \Gamma ^{*}$ ;
• $\delta (q_{1},a,\alpha )=(q_{2},\gamma _{2})$;
• $y_{2}=y_{1}\cdot y$, dove $y\in O^{*}$ e $y=\eta (q_{1},a,\alpha )$.

Diciamo che le due configurazioni $c_{1}$ e $c_{2}$ sono in relazione di transizione senza il consumo di un simbolo d'ingresso quando si verificano le seguenti condizioni:

• $x_{2}=x_{1}$;
• $\gamma _{2}=\beta \gamma _{1}$, dove $\beta \in \Gamma ^{*}$ ;
• $\delta (q_{1},\epsilon ,p)=(q_{2},\gamma _{2})$.
• $y_{2}=y_{1}\cdot y$, dove $y\in O^{*}$ e $y=\eta (q_{1},\epsilon ,\alpha )$.

Per quanto riguarda le computazioni la situazione è più semplice: a parte la necessità di impiegare le transizioni che abbiamo appena ridefinito, le loro proprietà rimangono inalterate.

Traduzione in un trasduttore a pila

I trasduttori a pila vengono impiegati per trasformare stringhe di simboli dell'alfabeto d'ingresso in stringhe di simboli dell'alfabeto d'uscita. Questa caratteristica non è ben testimoniata dalla funzione d'uscita in quanto essa opera su un solo simbolo d'ingresso e non su una stringa.

Per colmare questa lacuna, nell'ambito dei trasduttori a pila viene introdotto il concetto di traduzione; indicando con $x\in I^{*}$ la stringa da tradurre e con $y\in O^{*}$ la stringa tradotta, la traduzione è una funzione convenzionalmente indicata con il simbolo $\tau$ è definita come segue:

$\tau :I^{*}\rightarrow O^{*}$

$\tau (x)=y$ quando $x$ è una stringa accettata dal trasduttore.

Il fatto che la stringa d'ingresso debba essere accettata dal trasduttore rappresenta un piccolo ostacolo per la corretta definizione della funzione, poiché come sappiamo esistono due diversi criteri di accettazione. Proprio per questo motivo verranno proposte due diverse definizioni, pensate per i due criteri di accettazione.

Consideriamo un trasduttore a pila che accetti le stringhe per stato finale e indichiamo con $(q_{0},x,Z_{0},\epsilon )$ e $(q\in F,\epsilon ,\gamma \in \Gamma ^{*},y)$ due configurazioni associate al trasduttore in questione. La funzione di traduzione è allora definita come segue:

$\tau (x)=y$ quando $(q_{0},x,Z_{0},\epsilon )\vdash ^{*}(q,\epsilon ,\gamma ,y)$

Consideriamo invece un trasduttore a pila che accetti le stringhe per pila vuota e indichiamo con $(q_{0},x,Z_{0},\epsilon )$ e $(q,\epsilon ,\epsilon ,y)$ due configurazioni associate al trasduttore in questione. La funzione di traduzione è allora definita come segue:

$\tau (x)=y$ quando $(q_{0},x,Z_{0},\epsilon )\vdash ^{*}(q,\epsilon ,\epsilon ,y)$

Riflessioni conclusive

Sebbene durante la lezione siano stati presentati e discussi pochi esempi relativi ai modelli computazionali esposti, quanto visto è senza dubbio sufficiente per evidenziare un importante aspetto comune a tutti: il fatto che durante l'esecuzione ogni modello attraversa una fase in cui pone elementi sulla pila (che potremmo definire memorizzazione) ed un'altra in cui li rimuove (che potremmo definire recupero).

Questa caratteristica si riflette sulla struttura delle stringhe di simboli d'ingresso elaborabili dai formalismi considerati ed è possibile delinearne una fisionomia generale, composta da cinque parti: un prefisso, una fase di memorizzazione, un intermezzo, una fase di recupero ed un suffisso; inoltre il prefisso, l'intermezzo ed il suffisso possono anche essere stringhe vuote. Applicando questa considerazione ai due esempi presentati è facile rendersi conto che l'automa che riconosce il linguaggio $a^{n}b^{n}$ ha solamente le fasi di memorizzazione e di recupero, mentre l'automa che riconosce il linguaggio $wcw^{R}$ ha anche un intermezzo, costituito dal simbolo $c$.

L'intuizione riguardante la struttura delle stringhe riconoscibili dagli accettori a pila apre le porte ad una revisione del pumping lemma mirata alla nuova categoria di linguaggi; una sua presentazione a questo punto sarebbe prematura: come abbiamo più volte specificato, infatti, i modelli presentati costituiscono la variante deterministica, mentre quella non deterministica, che consente di riconoscere una classe di linguaggi più ampia, verrà discussa più avanti. Per questo motivo rimanderemo lo studio del rapporto esistente tra automi a pila e linguaggi formali ad un momento successivo, dopo la presentazione della variante non deterministica.

L'identificazione di una struttura per le stringhe riconosciute dagli automi a pila rappresenta anche un punto debole per questa classe di modelli computazionali: bisogna infatti considerare che la fase di recupero è distruttiva, nel senso che rimuove dalla pila gli elementi ivi memorizzati, perdendo definitivamente l'informazione che essi rappresentavano; se tale informazione dovesse servire dopo la fase di recupero, non sarebbe più accessibile.

Inizia quindi a farsi largo l'idea che gli automi a pila non siano i riconoscitori di linguaggi formali più potenti e che debba esistere qualche formalismo in grado di colmare tale lacuna. Tale modello computazionale sarà l'oggetto della prossima lezione: parleremo della Macchina di Turing.

Lezione precedente: Minimizzazione degli stati di un automa

Corso: Materia:Informatica Teorica

Prossima lezione: Macchina di Turing