Algoritmi e principi dell'Informatica

Automigli: automi e modelli operazionali

Gli automi rappresentano un classico esempio di modello operazionale; essi permettono di descrivere un sistema mostrando gli stati in cui esso si può trovare e come sia possibile passare da uno stato all’altro. Con il termine automa si intende un modello astratto che mostra l’evoluzione di un sistema come sequenza di configurazioni dei suoi stati, in seguito agli ingressi ricevuti; per questo motivo viene anche definito come macchina a stati discreti.

Automi a stati finiti

Gli automi a stati finiti (AF) sono il modello più usato in campo informatico. Un FSA rappresenta un sistema che può trovarsi in un numero finito di stati diversi. Come conseguenza di qualche ingresso, che può assumere anche esso un insieme finito di possibili valori, l’FSA effettua una transizione da uno stato all’altro.

Un automa a stati finiti è una tripla < Q, I, >:

• Q è un insieme finito di stati
• I è un insieme finito di simboli d’ingresso
• è la funzione di transizione Q x I → Q

Nella rappresentazione grafica: i nodi rappresentano gli stati, cioè nel grafo ci sarà un nodo per ogni elemento di Q, mentre un arco etichettato con i e diretto da q a q’ indica che è definita come (q, i) = q’.

Estendiamo ora la funzione , che rappresenta la transizione da uno stato ad un altro, in modo da rappresentare una sequenza di transizioni; S indica, a partire da uno stato, quale sarà lo stato in cui si troverà l’automa in conseguenza della ricezione di un simbolo in ingresso, introduciamo il simbolo σ per definire lo stato in cui si troverà l’automa, partendo da un dato stato, dopo aver ricevuto più simboli di ingresso in sequenza. Quindi S(x) definisce l’evoluzione dell’automa, partendo dallo stato q, come conseguenza di una sequenza x di qualunque valore in ingresso.

Riconoscitore

Per descrivere sistemi mediante modelli, è spesso utile estendere la definizione di AF con le notazioni di stato iniziale e stato finale, per indicare, rispettivamente, lo stato in cui si trova inizialmente l’AF quando comincia a funzionare e lo stato in cui si dovrebbe trovare l’AF dopo aver terminato le sue operazioni, in modo tale da poter verificare se il suo funzionamento è conforme agli obiettivi.

In questo modo un AF viene impiegato per modellare il riconoscimento di una sequenza finita di ingressi, per stabilire se tale sequenza gode o meno di alcune proprietà. L’automa riconosce/accetta la sequenza di ingresso se l’AF raggiunge il suo stato finale partendo dal suo stato iniziale.

Un riconoscitore a stati finiti è una quintupla < Q, I, , q0, F >, dove Q, I sono quelle classiche dell’AF, q0 è detto stato iniziale e F è detto insieme degli stati finali. Una stringa è riconosciuta da un AF se e solo se δ(q0, x) ∈ F.

Traduttore

Molto spesso bisogna costruire un modello per processi che producono un’uscita come conseguenza di qualche ingresso; gli archi vengono etichettati con una coppia <a, y> oppure a/y, dove a è un carattere in ingresso e y è una stringa di uscita, eventualmente vuota, che deve sostituire il carattere a.

Un trasduttore a stati finiti (TF) è una 7-upla < Q, I, , q0, F, O, >, dove Q, I, , q0, F sono quelle del riconoscitore, O è un insieme finito di simboli di uscita e è la funzione di uscita.

La funzione di uscita può essere estesa a Q x I → O*, in modo da produrre la stringa in uscita come conseguenza della lettura di una sequenza di simboli in ingresso.

Proprietà degli automi a stati finiti

• Sia dato un automa a stati finiti A, dove Q ha cardinalità n (|Q|=n). Il linguaggio riconosciuto da A è non vuoto se e solo se A accetta/riconosce una stringa con lunghezza ≤ n.
• Sia dato un automa a stati finiti A, dove Q ha cardinalità n (|Q|=n). Il linguaggio riconosciuto da A è infinito se e solo se A accetta/riconosce una stringa con lunghezza ≥ n e presenta cicli.

I teoremi precedenti sono basati sul fatto che un AF può presentare cicli nella sua rappresentazione grafica; se ciò non avviene, il linguaggio accettato è finito.

Pumping Lemma: Sia dato un automa a stati finiti A, esiste allora una costante k per la quale, se una stringa x ∈ L(A) e |x| ≥ k, allora x può essere scritta come x = uvw, dove |v| > 0 e uvⁱw ∈ L(A) per ogni i ≥ 0.

Intuitivamente esso afferma che, poiché se una stringa è lunga almeno quanto il numero di stati dell’automa che l’accetta, viene riconosciuta da una sequenza di transizioni in A che passa per un ciclo, allora tutte le stringhe che si ottengono ripetendo la sottostringa che attraversa il ciclo di A, sono pure accettate da A.

La classe dei linguaggi accettata dagli automi a stati finiti è chiusa rispetto all’intersezione; l’AF che riconosce il linguaggio intersezione è ottenuto simulando il funzionamento parallelo dei due automi A1 e A2, accoppiando i due automi attraverso il prodotto cartesiano tra gli stati e definendo la funzione di transizione solo dove è definita sia in A1 sia in A2 (la transizione deve essere definita in entrambi gli automi).

La classe dei linguaggi accettata dagli automi a stati finiti è chiusa rispetto al complemento; l’idea sfruttata dall’operazione di complemento è quella di invertire gli stati finali con quelli non finali, invertendo cioè l’accettazione con il rifiuto quando viene letta una stringa. Tale filosofia funziona se la stringa in ingresso viene letta completamente dall’automa di partenza; è quindi necessario rendere totale la funzione di transizione di un automa prima di complementarlo, aggiungendo gli “stati pozzo” per evitare che la stringa in ingresso non venga letta completamente fermando la computazione.

La classe dei linguaggi accettata dagli automi a stati finiti è chiusa rispetto all’unione; analogamente a quanto detto per l’intersezione, l’unica differenza è nel fatto che la funzione di transizione è definita solo dove è definita in A1 oppure in A2 (la transizione deve essere definita in almeno uno degli automi).

Automi a pila

Gli automi a pila (AP) sono modelli a stati (come gli AF) arricchiti di una memoria ausiliaria strutturata come pila; la pila è una struttura che può essere letta e scritta e che influenza, con il suo contenuto, le transizioni nella macchina a stati.

Un automa a pila è una 6-upla < Q, I, , , q0, Z0 > dove Z è l’insieme dei simboli della pila e Z0 è il simbolo iniziale della pila.

La lettura della stringa in ingresso effettuata dall’AF può essere realizzata da un dispositivo ideale dotato di una testina di lettura; inizialmente, la testina di lettura è posizionata all’inizio della stringa di ingresso (che si suppone scritta su un nastro). Ad ogni passo la testina legge un nuovo carattere e il dispositivo passa allo stato (q, i), dove q è lo stato precedente ed i il simbolo letto. La funzione di transizione non è però totale; perciò, se (q, i) è indefinita, la macchina si ferma.

La lettura continua fino a quando la stringa in ingresso è stata completamente letta; se, al termine della lettura, la macchina si trova in uno stato finale, la stringa viene accettata, altrimenti viene rifiutata. In un automa a pila la testina di lettura legge il nastro in ingresso da sinistra a destra; a differenza di quanto visto per gli AF, la transizione/mossa dell’automa non è solo una funzione del simbolo letto in ingresso e dello stato presente ma dipende anche dal simbolo presente in cima alla pila, che una volta letto viene rimosso dalla pila.

La mossa consiste nel:

• Muovere la testina di lettura verso destra
• Commutare verso un nuovo stato q’
• Scrivere una stringa (eventualmente vuota) di simboli in cima alla pila, al posto del simbolo rimosso.

A differenza di quanto visto per gli AF, l’automa può anche effettuare una mossa senza leggere alcun simbolo in ingresso, ovvero sono definite le ε-mosse. Se è definita una ε-mossa, allora deve essere indefinita ; senza questa limitazione, l’automa non sarebbe più deterministico.

La configurazione di un AP è intuitivamente una fotografia dell’automa in un determinato istante, che mostra lo stato dell’organo di controllo, la porzione di stringa in ingresso che deve essere ancora letta e il contenuto della pila. Formalmente, la configurazione è una tripla c = < q, x, >, dove q è lo stato corrente, x è la porzione non ancora letta della stringa in ingresso e è il contenuto della pila.

Per un dato AP, la relazione binaria di transizione nello spazio di tutte le possibili configurazioni di A è definita da c = < q, x, > c’ = < q’, x’, > se e solo se vale una delle seguenti condizioni:

• (q, i, A) = < q’, , >

Riconoscitore a pila

Un riconoscitore a pila è una 7-upla < Q, I, , , q0, Z0, F > dove F è l’insieme degli stati di accettazione; una stringa è riconosciuta se esiste un cammino coerente con µ nell’automa che porta dallo stato iniziale ad uno stato finale dell’automa leggendo tutta la stringa in ingresso.

Se (q0, i, A) = <q’, > allora esiste un arco orientato che collega q a q’ e che è caratterizzato dall’etichetta a, A/.

Traduttore a pila

Come per gli AF, è possibile estendere gli AP facendo sì che essi possano produrre una stringa in uscita come risultato della scansione e riconoscimento di una stringa in ingresso. Un trasduttore a pila (TP) è una 9-upla T = < Q, I, , , q0, Z0, F, O, > dove O è un insieme finito di simboli in uscita e è la funzione di uscita.

Una traduzione è associata a T nel seguente modo:

• La funzione di uscita può essere estesa in modo da produrre la stringa in uscita come conseguenza della lettura di una sequenza di simboli in ingresso.

Proprietà degli automi a pila

• Ogni linguaggio accettato da un AF è accettato anche da un AP; quindi gli AP sono almeno potenti quanto gli AF.
• Il linguaggio anbn può essere accettato da un AP ma non può essere accettato da un AF; quindi gli AP sono strettamente più potenti degli AF.

Ad ogni mossa, gli AF sono obbligati a leggere un simbolo; ciò significa che un AF con in ingresso una stringa composta da n simboli fa al più n mosse (AF legge fino a quando non termina la stringa oppure fino a quando entra in uno stato per cui non è definita la funzione di transizione per il corrispondente simbolo in ingresso). Preso un AF si può sempre trasformare la sua funzione di trasformazione in modo da renderla totale; si può quindi supporre che un AF legga sempre tutta la stringa in ingresso.

Lo stesso risultato non vale per gli AP; poiché gli AP non devono necessariamente leggere un simbolo ad ogni mossa, può accadere che un AP, in qualche configurazione, entri in una sequenza infinita di ε-mosse (ovvero mosse che non fanno avanzare la testina sul nastro in ingresso).

Proprietà:

• Nessun AP è in grado di riconoscere il linguaggio anbncn o anbn.

Questo implica il fatto che gli AP non sono chiusi rispetto all’unione dei linguaggi.

Macchine di Turing

Gli AP sono più potenti degli AF, nel senso che possono risolvere tutti i problemi risolvibili dagli AF ed anche alcuni problemi che gli AF non riescono a risolvere. Anch’essi però hanno i loro limiti, essenzialmente dovuti alla politica LIFO della pila:

• La pila è una memoria distruttiva, in cui leggere significa eliminare elementi
• La politica LIFO permette di accedere solo all’ultimo elemento inserito e quindi, se si volesse leggere un simbolo che si trova in mezzo alla pila, tale politica di accesso obbliga ad eliminare tutti i simboli impilati sopra ad esso.

Una macchina di Turing (MT) consiste di:

• Un nastro di ingresso
• Un nastro di uscita
• k nastri di memoria
• Un dispositivo di controllo dotato di un numero finito di stati.

Ciascun nastro è una sequenza di celle ed è infinito; ciascuna cella contiene un unico simbolo scelto all’interno di un insieme finito, contenente fra gli altri anche il simbolo blank (b). Ogni nastro viene letto da una testina che può leggere, scrivere, muoversi a destra o a sinistra di una posizione, o rimanere ferma.

Un passo di computazione di una MT consiste nelle seguenti operazioni. In dipendenza dallo stato corrente del controllo e dai simboli che si trovano sotto ciascuna testina, la macchina effettua le operazioni:

• Cambia lo stato del dispositivo di controllo
• Stampa nuovi simboli (sovrascrivendo i simboli esistenti) nelle celle sotto le testine dei nastri di mem
• Muove una o tutte le testine, indipendentemente l’una dall’altra, di una cella a destra (R) o a sinistra (L) o le lascia ferme (S)
• La testina del nastro di uscita non può muoversi verso sinistra (non può tornare indietro)

In alternativa, la macchina non effettua alcuna operazione e si ferma definitivamente.

Una macchina di Turing k-nastri M = < Q, I, , O, , , q0, Z0, F > è una 9-upla dove:

• Q è un insieme finito di stati
• I è un alfabeto di ingresso finito
• è un alfabeto di memoria finito
• O è un alfabeto di uscita finito
• F è l’insieme degli stati finali (F ⊆ Q)
• q0 è lo stato iniziale (q0 ∈ Q)
• Z0 è il simbolo iniziale dell’alfabeto di memoria (Z0 ∈ )
• è la funzione di transizione
• è la funzione di uscita.

Riconoscitore

Il linguaggio riconosciuto da una MT è composto da tutte e sole le stringhe che, coerentemente alla funzione di transizione, permettono di andare dallo stato iniziale a uno stato finale. Si noti che per le MT, poiché nel nastro in ingresso è possibile muoversi in entrambe le direzioni, non è richiesto che al termine della computazione la testina si trovi al termine della stringa di ingresso.

Traduttore

Una stringa x viene tradotta in una stringa y da una MT, se esiste un cammino che parte da una configurazione iniziale con x sul nastro di ingresso e termina in una configurazione finale con y sul nastro di uscita.

Proprietà delle macchine di Turing

• La MT multinastro e le MT a nastro singolo sono formalismi equivalenti, ossia accettano la stessa classe di linguaggi e realizzano la stessa classe di traduzioni.
• Ogni MT è equivalente ad un’opportuna MT dotata solo di due stati non finali e di uno stato finale (eventualmente dotata di un numero maggiore di simboli).
• Ogni MT è equivalente ad un’opportuna MT avente un alfabeto con due soli simboli (eventualmente dotata di un numero maggiore di stati).

Automi non deterministici

Tutti i modelli considerati finora sono deterministici, nel senso che, una volta fissato lo stato e l’ingresso, la loro evoluzione è univocamente determinata; in altri termini, la relazione di transizione ha un solo valore. Spesso si verifica però che il sistema che si deve modellare non può essere descritto in modo deterministico, in quanto l’osservatore possiede una conoscenza del suo comportamento che non è sufficientemente accurata da consentirgli di prevederne l’esatta evoluzione, come conseguenza dello stato presente e dell’ingresso dato.

In alcuni casi una modellizzazione non deterministica viene preferita a una deterministica, in quanto in grado di fornire una descrizione più astratta di un certo fenomeno reale.

Automi a stati finiti non deterministici

Un automa non deterministico a stati finiti (AFN) è definito come un AF con la sola differenza che la funzione di transizione è data da Q x I -> P(Q), dove P(Q) rappresenta l’insieme delle parti di Q, i cui elementi sono quindi insiemi di stati.

Un AFN può presentare diverse sequenze di transizioni per ogni dato stato e per ogni data sequenza in ingresso; la funzione di transizione di un AFN, dato uno stato e un ingresso, porta, invece che in un solo stato, in un insieme di stati. Nel caso di riconoscitori, una stringa è accettata da un AFN se e solo se almeno una delle possibili sequenze di transizioni conduce ad uno stato finale.

Gli automi non deterministici a stati finiti non sono più potenti dei loro corrispondenti deterministici; per ogni AFN, può essere costruito un AF che accetti il medesimo linguaggio.

Automi a pila non deterministici

Gli automi a pila sono modelli intrinsecamente non deterministici: infatti, nella definizione di un AP si era dovuto aggiungere il vincolo che, se per determinate condizioni è definita una mossa, allora non può essere definita nessuna altra transizione.