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 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:

Inoltre consideriamo la pila inizializzata con per marcare il fondo.

Automa riconoscitore

Note

In un automa riconoscitore a pila, la stringa in ingresso è riconosciuta (accettata) se l’automa scandisce completamente , e una volta scandita tutta lo stato dell’organo di controllo è accettazione. Formalmente, un automa riconoscitore a pila è composto da:

• come negli FSA
• alfabeto di pila
• simbolo iniziale di pila
• funzione di transizione con

PDA riconoscitore di

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 . Se la non è accettata la traduzione è indefinita: . Formalmente, un automa traduttore a pila è composto da:

• come nei AP riconoscitori
• come negli FSA traduttori
• funzione di traduzione con

Stato di un AP

Note

Definiamo lo stato di un AP come , con:

• Stato dell’organo di controllo
• Stringa ancora da leggere
• Stringa dei caratteri in pila (per convenzione cresce da sinistra a destra)
• Se l’AP è traduttore, la stringa scritta in output

Transizione tra configurazioni

Note

Definiamo una transizione tra due stati e con l’operatore :

Per comodità, sia , cioè una sequenza di simboli con in cima. Se l’input è consumato, allora lo suddividiamo in . La funzione di trasmissione restituisce , e quindi l’output associato è . Di conseguenza, , e . Se l’input non è consumato, allora la funzione di transizione restituisce , e l’output associato è . Di conseguenza , e .

È necessario che:

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

Definiamo infinite come chiusura riflessiva e transitiva .

In questo modo formalizziamo l’accettazione:

E la traduzione:

Famiglia dei linguaggi riconoscibili dagli AP

Note

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

Pumping lemma per AP

Note