Automi a pila

Automi a pila

Gli automi a stati (deterministici o non) non possono riconoscere linguaggi non contestuali, in quanto ciò richiederebbe una memoria non limitata. Es: { 0ⁿ1ⁿ | n > 0 }

Fissato n, allora il linguaggio genera una stringa riconoscibile da un automa a stati finiti. Tuttavia, con n variabile, il linguaggio è un insieme e non è possibile rappresentare (con un diagramma degli stati) un numero di stati non definito a priori.

Automa a pila

Esempio di automa con memoria non limitata. L’automa, dunque, ha un nuovo componente: la pila (stack). Sulla pila, intuitivamente, un automa a pila svolge le seguenti operazioni (oltre a svolgere tutte quelle degli automi a stati finiti):

• Scrivere un simbolo sulla pila
• Leggere un simbolo dalla pila

L’automa a pila è LIFO (Last In First Out), visto che si può agire solo sull’ultimo elemento sopra la pila. Il vantaggio: la pila può contenere una quantità di informazione (un numero di elementi) non limitata e non determinata a priori.

Quindi, l’automa a pila può riconoscere sia i linguaggi contestuali (operando come automi a stati finiti) sia linguaggi non contestuali (utilizzando la pila).

Esempio di prima

Automi a pila 1

Definizione formale

Definizione non deterministica per codominio. Due sono le differenze con la definizione degli automi a stati finiti:

• L’alfabeto della pila Γ
• La definizione della funzione di transizione
  • Il suo dominio, infatti, è composto da:
    • Stato corrente Q
    • Il prossimo simbolo da leggere su Σ, anche quello nullo eventualmente
    • Il simbolo della pila Γ considerato, anche quello nullo eventualmente

Automi a pila 2

Come per gli automi a stati finiti, se si legge il simbolo vuoto, ci può essere una transizione di stato senza leggere input. Il funzionamento ideale dell’automa a pila per ogni step è:

1. Entrare in un nuovo stato leggendo da input
2. Scrivere un simbolo sulla pila

Transizioni

Le transizioni di un automa a pila sono nella forma:

Ciò vuol dire che: un automa è nello stato q con elemento in cima alla pila b e riceve come input a, allora l’automa transita da q₁ a q₂ leggendo a e sostituisce nella pila b con c. Sull’arco da q₁ a q₂ ci sarà scritto “a, b→c”.

Casi particolari

Sia a sia b sia c possono assumere il valore vuoto ε.

• a = ε → l’automa può transitare allo stato successivo senza leggere dall’input