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

center

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

center

Esempio parentesi tonde ben formate

center

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