# Automi a pila (AP)
## Pila
Oggetto di memoria infinita limitata inferiormente dall'elemento $Z_0$
Operazioni su pila:
- Push E: mette L'elemento E in cima alla pila
- Pop: toglie l'elemento in cima alla pila e lo restituisce

Negli automi AP le operazioni sulla pila sono leggermente differenti dalle operazioni di push e pop.

## AP
- definiti nella forma <$Q, I, \Gamma, \delta, q_0, Z_0, F$> (con l'aggiunta di $O,\ \eta$ se AP traduttori), dove:
- $\Gamma$ è l'alfabeto di pila, in generale $\Gamma \ne I$
- $\delta: Q$ x $I\cup\{\varepsilon\}$ x $\Gamma \to Q$ x $\Gamma^*$
- quindi ad ogni mossa devo fare la pop del primo elemento in pila, leggere o meno un elemento dalla stringa in ingresso ed inserire o meno uno o più elementi in cima alla pila. Convenzione per elementi per push:
**Sinistra-basso, detra-alto. Pila cresce verso l'alto.**
- Configurazione: $c = <q, x, \gamma, [z]>$:
- q: stato
- x: stringa ancora da leggere
- $\gamma$: pila
- z: stringa in output
- Relazione di transizione tra stati: $\vdash$.
- $c\ \vdash\ c'$, con $c = <q, i.y, \beta A>$ e $c' = <q, x', \beta\alpha>$ se:
- $\delta(q,i,A)= <q',\alpha> \implies x'=y$
- $\delta(q,\varepsilon,A)= <q',\alpha> \implies x'=i.y$
- Negli APD se c'è una $\varepsilon$ mossa allora non ci possono essere altre mosse che richiedono la stessa pop, quindi $\delta$ in generale non è totale
- Memoria degli AP è distruttiva:
- posso accettare $L=\{a^nb^n|n>0\}$ e $L=\{a^n b^{2n} |n>0\}$ ma non $L=\{a^nb^nc^n|n>0\}$
- APD non chiusi rispetto all'unione (ad esempio tra $L=\{a^nb^n|n>0\}$ e $L=\{a^n b^{2n}|n>0\}$
- APD non chiusi rispetto all'intersezione (intersezione tra $\{a^nb^*c^n|n>0\}$ e $\{a^nb^nc^*|n>0\}$ è $\{a^nb^nc^n|n>0\}$)
- Ho però chiusura rispetto al complemento:
- mi serve rendere $\delta$ totale (tranne che per le $\varepsilon$ mosse) creando degli stati pozzo
- scambio stati finali con stati non finali
- faccio attenzione a non creare loop

## APND
Aggiungono potenza agli AP solo per quanto riguarda l'unione, non si è ancora chiusi per l'intersezione (stesso esempio di prima) e si perde la chiusura della negazione:
- Se x $\in L_1$ e x $\notin L_2$, con $L_1$ e $L_2$ due linguaggi *LP* (riconosciuti da un automa a pila), posso creare un APND che sia l'unione dei due AP che riconoscono $L_1$ e $L_2$, e che quindi accetta x. Ma non posso creare il complemento di questo APND scambiando gli stati di accettazione con gli altri, perché x verrebbe accettata in quanto x $\in L_2^{-1}$.

Non abbiamo visto la dimostrazione per cui non si ha la chiusura rispetto al complemento.

## To add:
- esempi