Automi a pila

Automi a pila

Gli automi a stati (deterministici o non) non possono riconoscere linguaggio non contestuali, in quanto ciò richiederebbe una memoria non limitata.

Esempio: {0^n 1^n | 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.

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:

1. L'alfabeto della pila Γ
2. La definizione della funzione di transizione

a. Il suo dominio, infatti, è composto da:

1. stato corrente Q
2. il prossimo simbolo da leggere su Ʃ, anche quello nullo eventualmente
3. 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 pile per ogni step è:

1. entrare in un nuovo stato

leggendo da input2. scrivere un simbolo sulla pila

Transizioni

Le transizioni di un automa a pila sono nella forma:

Ciò vuol dire che:

un automa è nello stato con elemento in cima alla pila b e riceve come input a

q1

allora, l'automa transita da a leggendo a e sostituisce nella pila b con c

q q1 2

Sull'arco da a ci sarà scritto "a, b→c"

q q1 2

Casi particolari

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

1. a = ε → l'automa può transitare allo stato successivo senza leggere dall'input

2. b = ε → l'automa può transitare di stato senza leggere ed estrarre elementi dalla pila

3. c = ε → l'automa può transitare di stato senza aggiungere elementi alla pila

Verifica pila vuota: $

Bisogna trovare un modo per capire se la pila è vuota.

Soluzione: come prima transizione, si inserisce in maniera non deterministica nella pila il simbolo $, che mi

indica che la pila è vuota. Di conseguenza, vi sarà una transizione sempre non deterministica che, se legge dalla pila $ come ultimo simbolo (=pila vuota), transita allo stato finale. Matrice di transizione:

Stato	Input	Pila	Output	Prossimo Stato
q0	0	Z	0Z	q0
q0	1	Z	1Z	q0
q0	1	0	ε	q1
q1	1	0	ε	q1
q1	ε	Z	ε	qf

Automi a pila 3 La riga "Pila" mi dice cosa devo leggere ed estrarre dalla pila. Il simbolo a destra della parentesi mi dice cosa devo scrivere nella pila. Diagramma degli stati: Problema: la transizione finale, essendo non deterministica e non legata a un specifico linguaggio, crea problemi. Infatti, se dovessi verificare, per esempio, la stringa 00111, il funzionamento sarebbe il seguente: - per i primi due 0 rimango in q0 e aggiungo due 0 nella pila (senza leggere nulla) - per i primi due 1 vado in q0 e rimango in q0, non scrivendo nulla nella pila - leggendo ed estraendo i due 0 presenti con l'ultimo 1 il funzionamento non è quello sperato: infatti, dalla pila si legge $. Ciò comporta una transizione non deterministica e non prevista allo stato qf.

finale. Ciò mi porta ad accettare, erroneamente, la stringa 00111.

Configurazione

La configurazione di un automa a pila AP è una coppia dove:

il primo elemento è una configurazione di un automa a stati finiti

Automi a pila 4