Automi a pila

Note

A differenza di un FSA, dove la memoria dello stato del calcolo è finita, un automa a pila (AP o PDA, Push-Down Automaton) dispone di una memoria a impilamento con funzionamento Last In First Out (LIFO), cioè:

• La pila può crescere all’infinito
• Si può accedere alla sola cella in cima, e leggere la cima della pila lo cancella

Un automa a pila compie una mossa in funzione di:

• Simbolo letto dalla cima della pila
• Stato corrente nel FSA che costituisce l’organo di controllo
• Opzionalmente, simbolo letto dal nastro di ingresso

Un automa a pila passa alla configurazione successiva:

• Cambiando stato nell’organo di controllo
• Sostituendo al simbolo in cima alla pila una stringa $\alpha$ di simboli (anche nulla)
• Spostando (opzionalmente la testina di lettura)
• Se l’automa è traduttore, scrivendo una stringa (anche nulla)

Per convenzione si etichettano gli archi con formato:

$$⟨\text{lettera input},\text{cima della pila letta/scritta in fondo alla pila},\text{lettera in output}⟩$$

Inoltre consideriamo la pila inizializzata con $Z_0$ per marcare il fondo.

Automa riconoscitore

Note

In un automa riconoscitore a pila, la stringa $x$ in ingresso è riconosciuta (accettata) se l’automa scandisce completamente $x$, e una volta scandita tutta lo stato dell’organo di controllo è accettazione. Formalmente, un automa riconoscitore a pila $(Q,I,\Gamma ,\delta ,q_0,Z_0,F)$ è composto da:

• $Q,I,q_0,F$ come negli FSA
• $\Gamma$ alfabeto di pila
• $Z_0\in \Gamma$ simbolo iniziale di pila
• $\delta$ funzione di transizione con $\delta :Q\times (I\cup \{\epsilon \})\times \Gamma \to Q\times {\Gamma }^{\ast }$

PDA riconoscitore di $\{a^n{b}^n\mid n>0\}$

Esempio parentesi tonde ben formate

Automa traduttore

Note

In un automa traduttore, se la stringa è accettata, il nastro di scrittura contiene la sua traduzione al termine del calcolo $\tau (x)$. Se la $x$ non è accettata la traduzione è indefinita: $\tau (x)=\perp$. Formalmente, un automa traduttore a pila $(Q,I,\Gamma ,\delta ,q_0,Z_0,F,O,\eta )$ è composto da:

• $Q,I,\Gamma ,\delta ,q_0,Z_0,F$ come nei AP riconoscitori
• $O$ come negli FSA traduttori
• $\eta$ funzione di traduzione con $\eta :Q\times (I\cup \{\epsilon \})\times \Gamma \to O^{\ast }$

Stato di un AP

Note

Definiamo lo stato di un AP come $c=⟨q,x,\gamma ,z⟩$, con:

• Stato dell’organo di controllo $q\in Q$
• Stringa ancora da leggere $x\in I^{\ast }$
• Stringa dei caratteri in pila $\gamma \in {\Gamma }^{\ast }$ (per convenzione cresce da sinistra a destra)
• Se l’AP è traduttore, la stringa scritta in output $z\in O^{\ast }$

Transizione tra configurazioni

Note

Definiamo una transizione tra due stati $c$ e $c^{\prime }$ con l’operatore $⊢$:

$$c⊢c^{\prime }:⟨q,x,\gamma ,z⟩⊢⟨q^{\prime },x^{\prime },{\gamma }^{\prime },z^{\prime }⟩$$

Per comodità, sia $\gamma =\beta .A$, cioè una sequenza di simboli con $A$ in cima. Se l’input è consumato, allora lo suddividiamo in $x=i.y$. La funzione di trasmissione $\delta (q,i,A)$ restituisce $⟨q^{\prime },\alpha ⟩$, e quindi l’output associato è $\eta (q,i,A)=w$. Di conseguenza, $x^{\prime }=y$, ${\gamma }^{\prime }=\beta \alpha$ e $z^{\prime }=z.w$. Se l’input non è consumato, allora la funzione di transizione $\delta (q,\epsilon ,A)$ restituisce $⟨q^{\prime },\alpha ⟩$, e l’output associato è $\eta (q,\epsilon ,A)=w$. Di conseguenza $x^{\prime }=x$, ${\gamma }^{\prime }=\beta \alpha$ e $z^{\prime }=z.w$.

È necessario che:

$$\forall q,A\delta (q,\epsilon ,A)\ne \perp ⟹\forall i\delta (q,i,A)=\perp$$

In caso contrario l’automa a pila è non deterministico.

Definiamo infinite $\stackrel{\ast }{⊢}$ come chiusura riflessiva e transitiva $⊢$.

In questo modo formalizziamo l’accettazione:

$$x\in L⟺c_0=⟨q_0,x,Z_0⟩\stackrel{\ast }{⊢}{c}_f=⟨q,\epsilon ,\gamma ⟩q\in F$$

E la traduzione:

$$x\in L\wedge [z=\tau (x)]⟺c_0=⟨q_0,x,Z_0,\epsilon ⟩\stackrel{\ast }{⊢}{c}_f=⟨q,\epsilon ,\gamma ,z⟩q\in F$$

Famiglia dei linguaggi riconoscibili dagli AP

Note

Definiamo la famiglia dei linguaggi riconosciuti dagli AP deterministici come $L_{AP}$. Si ha che $L_{AP}$ non è chiusa rispetto all’unione e all’intersezione, ma è chiusa rispetto al complemento.

Pumping lemma per AP

Note

$$\exists k\ge 1x=pvcws\in L_{AP}|x|\ge k,|vcw|\le k,|vc|\ge 1⟺\forall n\in \mathbb{N}p{v}^{n}c{w}^{n}s\in L_{AP}$$