Automa a stati finiti non deterministico

Lezione precedente: Macchina di Turing

Corso: Materia:Informatica Teorica

Prossima lezione: Automa a pila non deterministico

Introduzione: determinismo, non determinismo e probabilismo

Nella prima lezione del corso è stato introdotto un elementare ma importante modello computazionale: l'automa a stati finiti deterministico. In questo formalismo, l'evoluzione dello stato viene innescata dalla lettura di un simbolo dal nastro d'ingresso; una volta stabiliti lo stato attuale ed il simbolo letto, c'è una transizione univocamente definita che porta allo stato prossimo: è proprio questa univocità a garantire il determinismo del modello.

Sebbene il determinismo offra l'apprezzabile vantaggio della prevedibilità, bisogna ammettere che il suo limite principale è costituito dall'inevitabile rigidità che le sue ipotesi operative comportano. L'impossibilità di memorizzare dati all'infuori degli stati, ad esempio, è il motivo per cui vi sono situazioni in cui il numero di stati dei modelli di questo genere tende ad aumentare vertiginosamente. Questa caratteristica è davvero poco desiderabile, poiché da un punto di vista pratico significa allungare in modo sensibile i tempi di sviluppo. Un buon modo per ovviare a questi inconvenienti consiste nel modificare il modello, agendo sulla componente che più di tutti lo caratterizza: la transizione.

Concettualmente, la transizione serve per consentire al modello di modificare il suo stato, in accordo con gli stimoli ricevuti in ingresso. Se si desidera modificare il comportamento delle transizioni è necessario cambiare il modo in cui quest'ultime associano lo stato prossimo a partire dallo stato attuale e dall'ingresso. Questo obiettivo può essere raggiunto associando allo stato attuale ed al simbolo letto in ingresso un insieme di stati prossimi anziché un solo stato.

Prevedere che una transizione conduca il modello computazionale verso più stati contemporaneamente non implica necessariamente introdurre il non determinismo: il comportamento del modello dipende anche da eventuali vincoli che si possono introdurre per guidare le scelte. A tal proposito esistono almeno due diverse impostazioni, tra le quali si rischia di fare confusione:

• probabilismo: ogni volta che l'automa deve scegliere tra più stati ci sono delle probabilità associate alle transizioni;
• non determinismo: l'automa non sceglie, ma segue virtualmente tutte le alternative.

La distinzione tra l'approccio probabilistico e quello non deterministico è comprensibile pensando alla ripetibilità dei risultati: se un automa probabilistico viene eseguito ripetutamente sulla stessa sequenza di simboli d'ingresso, in generale offrirà risultati differenti; questo comportamento è dovuto al fatto che l'esito della computazione in un automa probabilistico è dato da una variabile aleatoria. Al contrario, un automa non deterministico garantirà sempre il medesimo risultato.

L'automa a stati finiti non determinisitco, introdotto per la prima volta da Michael Oser Rabin e Dana Scott nel 1959, ha lo scopo di rendere più semplice la progettazione degli automi a stati finiti deterministici. Questo obiettivo si raggiunge a partire da due considerazioni che verranno approfondite durante la lezione, ma che possiamo enunciare fin d'ora:

• per ogni automa a stati finiti non determinisitico è possibile sviluppare un automa a stati finiti deterministico che riconosce il medesimo linguaggio;
• di solito l'automa a stati finiti non deterministico dispone di meno stati rispetto alla sua versione deterministica.

Mettendo insieme queste caratteristiche è possibile tracciare un processo di creazione degli automi a stati finiti:

1. si inizia sviluppando un modello non deterministico, fino a raggiungere i risultati voluti;
2. si converte il modello nel suo equivalente deterministico.

Come avremo modo di vedere, nel caso peggiore, a partire da un automa non deterministico dotato di $n$ stati è possibile ricavare un automa equivalente deterministico dotato di $2^{n}$ stati; la semplificazione introdotta dal nuovo modello computazionale è quindi evidente.

Struttura della lezione

Nella prima parte della lezione verrà presentato il concetto di automa a stati finiti non deterministico, trascurando sia il suo ruolo come accettore, sia quello come trasduttore di linguaggi. In questo modo si potranno studiare le caratteristiche salienti del modello, concentrandosi sull'elemento che lo caratterizza maggiormente: la funzione di transizione.

Una volta definita la versione più elementare del modello computazionale, verranno presentate ed analizzate due varianti: l'accettore non deterministico ed il trasduttore non deterministico; questi nuovi formalismi verranno studiati servendosi di alcuni esempi, sviluppati dettagliatamente.

L'ultima parte della lezione sarà dedicata al teorema di equivalenza tra gli automi a stati finiti non deterministici e quelli deterministici; la dimostrazione, parzialmente sviluppata con metodo costruttivo, definirà un metodo per attuare la conversione tra i modelli.

Automa a stati finiti non deterministico

Nelle occasioni in cui abbiamo introdotto nuovi modelli computazionali è stata sempre seguita la convenzione di partire dalla rappresentazione di un dispositivo fisico che si comporti in modo paragonabile al modello da analizzare.

Nel caso degli automi a stati finiti non deterministici, il dispositivo fisico è identico al caso deterministico: un'unità di controllo, un nastro suddiviso in celle e una testina di lettura. La differenza, in questo caso, risiede nel principio di funzionamento dell'unità di controllo, che ci apprestiamo ad analizzare dettagliatamente.

Condizioni iniziali e ciclo di lavoro

Inizialmente l'unità di controllo si trova nello stato di partenza e la testina di lettura viene posizionata sopra la cella più a sinistra del nastro. A questo punto viene avviato il ciclo di lavoro, che si sviluppa come segue:

1. viene letto un simbolo dal nastro d'ingresso;
2. in base allo stato attuale e al simbolo letto, si determina un insieme di stati prossimi;
3. se l'insieme degli stati prossimi è l'insieme vuoto, si interrompe l'esecuzione nello stato attuale.
4. immaginiamo di avere una macchina identica per ognuno degli stati prossimi, facendo in modo che il suo stato coincida con uno di quelli definiti al punto 2.

Le macchine vengono avviate in parallelo ed il ciclo prosegue, per tutte, dal punto 1.

Il punto più delicato del ciclo di lavoro è sicuramente l'ultimo, che si può parafrasare in questo modo: quando ad uno stesso simbolo corrispondono più transizioni, l'automa non deterministico le segue tutte in parallelo. Dall'analisi del ciclo di lavoro possiamo anche dedurre che non tutti gli automi che vengono azionati in parallelo terminano la loro computazione: è infatti possibile che, in un determinato stato, la ricezione di particolari simboli d'ingresso non inneschi alcuna transizione. In questa situazione, già riscontrata negli automi a stati finiti, la funzione di transizione è parziale. È importante, in questo contesto, dare un senso al concetto di terminazione di una computazione: per il presente modello, la computazione viene completata quando non ci sono più simboli da leggere dal nastro d'ingresso. Ciò significa che la computazione non termina quando, pur essendoci ancora simboli da leggere, l'automa non è più in grado di cambiare il proprio stato.

Nel contesto attuale, il non determinismo è rappresentato da due aspetti:

• a partire da uno stato, un unico simbolo d'ingresso può attivare più di una transizione;
• a partire da uno stato, un simbolo d'ingresso può non attivare alcuna transizione.

Accanto a questi aspetti, gli automi a stati finiti non deterministici hanno la possibilità di effettuare transizioni senza leggere simboli dal nastro d'ingresso; i cambiamenti di stato che avvengono senza leggere simboli dal nastro d'ingresso si chiamano $\epsilon$-mosse.

Definizione di automa a stati finiti non deterministico

Un automa a stati finiti non deterministico è una terna ordinata di valori $N=(Q,I,\delta )$ definiti come segue:

• $Q$ è un insieme finito di stati;
• $I$ è un insieme finito di simboli detto alfabeto d'ingresso;
• $\delta :Q\times I\cup \left\{\epsilon \right\}\rightarrow {\mathcal {P}}(Q)$ è la funzione di transizione.

La definizione di funzione di transizione merita un commento più specifico. Anzitutto si nota che gli elementi dell'insieme di partenza sono coppie ordinate in cui il primo elemento è sempre uno stato, mentre il secondo può essere o un simbolo dell'alfabeto d'ingresso, oppure la stringa vuota. In questo modo si tiene conto della possibilità di non leggere nulla dal nastro d'ingresso. L'insieme d'arrivo è indicato con la dicitura ${\mathcal {P}}(Q)$, che indica l'insieme delle parti dell'insieme degli stati; come conseguenza gli elementi dell'insieme d'arrivo sono sottoinsiemi dell'insieme degli stati: in questo modo un solo simbolo d'ingresso può innescare contemporaneamente più transizioni.

Sebbene questo modello sia molto utile per introdurre il non determinismo, la sua utilità pratica è molto limitata poiché non dispone né della possibilità di riconoscere stringhe di simboli in ingresso, né tantomeno della possibilità di compiere traduzioni. Proprio per questi motivi il modello computazionale viene esteso, con lo scopo di aumentarne il potere espressivo, per generare l'accettore non deterministico ed il trasduttore non deterministico.

Automa accettore non deterministico

Automa trasduttore non deterministico

Equivalenza tra automi a stati finiti deterministici e non deterministici

Dimostrazione

Lezione precedente: Automa a pila

Corso: Materia:Informatica Teorica

Prossima lezione: Grammatiche