Informatica Teorica

Automi

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.

1. 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
• QxIci Qsi QRappresentazione grafica: i nodi rappresentano gli stati, cioè nel grafo ci sarà un nodo per ogni elementi di i q q’ (q, i) = q’.

Mentre un arco etichettato con e diretto da a indica che è definita come SSEstendiamo ora la funzione , che rappresenta la transizione da uno stato ad un altro, in modo da Ssequenza di transizioni; rappresentare una se indica, a partire da uno stato, quale sarà lo stato in cui Ssi troverà l’automa in conseguenza della ricezione di un simbolo in ingresso, introduciamo il simbolo si per definire lo stato in cui si troverà l’automa, partendo da un dato stato, dopo aver ricevuto più simboli di ingresso in sequenza.

q, Quindi definisce l’evoluzione dell’automa, partendo dallo stato come conseguenza di una sequenza x I.qualunque di valori in ingresso e SIxi195 ieI5 canxeI19,81 lqxl.ee9

Riconoscitore

Per descrivere sistemi mediante modelli, è spesso utile estendere la definizione di AF con le notazioni di stato iniziale finale, e stato 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, , q , F >, dove Q, I e sono quelle classiche ss 0q Q stato iniziale F Q stati finali. dell’AF, è detto e è detto insieme degli EE0 riconosciutax I , x) F.Una stringa è da un AF se e solo se (q EE 0

Traduttore

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

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

La funzione di uscita può essere estesa a , in modo da produrre la stringa in uscita come conseguenza4 della lettura di una sequenza di simboli in ingresso È ixi lq.it419 119,4 4 44 9 4

Sia dato un trasduttore a stati finiti T, la traduzione associata a T è definita0Zr I EF171 8solo 190190 se e4 se

Proprietà

• Sia dato un automa a stati finiti A, dove Q ha cardinalità n ( |Q|=n ). Il linguaggio riconosciuto da A è non x vuoto se e solo se A accetta/riconosce una stringa con lunghezza 1 1911 e n
• Sia dato un automa a stati finiti A, dove Q ha cardinalità n ( |Q|=n ). Il linguaggio riconosciuto da A è x infinito se e solo se A accetta/riconosce una stringa con lunghezza 11n 2ne ecicli

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

Pumping Lemma: k

• Sia dato un automa a stati finiti A, esiste allora una costante per la quale, se ELIA 121 ke i ELx ywx, 1 k yw zallora può essere scritta come dove < |w| < e visox

Intuitivamente esso afferma che, perché, se una stringa è lunga almeno quanto il numero di stati x dell’automa che l’accetta, viene riconosciuta da una sequenza di transizioni in A che passa per ciclo, allora x, xtutte le stringhe che si ottengono da ripetendo la sottostringa di 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 A1, 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).

2. 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, , , q , Z > dove Z è l’insieme dei simboli della pila e è il MMs 0 0 0 simbolo iniziale della pila.

La lettura della stringa in ingresso effettuata dall’AF può essere realizzata da un dispositivo ideale dotato di q una testina di lettura; inizialmente, la testina di lettura è posizionata all’inizio della stringa di ingresso (che 0 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 Si precedente ed il simbolo letto.

La funzione di transizione non è però totale; perciò, se (q, i) è indefinita, la macchina si ferma. S

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 ivisto per gli AF, la transizione/mossa dell’automa non è solo una funzione del simbolo letto in ingresso e q, 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
• Q’Commutare verso un nuovo stato
• 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 - mosseE 819 AEi

Se è definita una - mossa , allora deve essere indefinita ; senza819 A tiE 819E Ai 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.ti

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

• 519AB istx x 413ay ap g 9e Al819AB
• E dat 413 eqi f e

Riconoscitore

Un riconoscitore a pila è una 7-upla < Q, I, , , q , Z F > dove F è l’insieme degli stati di accettazione; µ s 0 0, x x 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 ( q , i, A ) = < q’, > allora esiste un arco orientato che collega q a q’ e che è caratterizzato s o0 a, A/ . dall’etichetta a

Traduttore

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, , , q , Z F, O, > dove O è un insieme finito di me 0 0, y simboli in uscita funzione di uscita.e è laY

Una traduzione è associata a T nel seguente modo02 2 FF E21 1 EZo fe get2 solo toX 9egose asee zioEeqeq.E.kze znessun y9 yper

Proprietà

• Ogni linguaggio accettato da un AF è accettato anche da un AP; quindi gli AP sono almeno potenti quanto gli AF.
• Il linguaggio può essere accettato da un AP ma non può essere accettato da un AF; antonyiquindi 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 x n n stringa composta da simboli fa al più 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 - mosseE (ovvero mosse che non fanno avanzare la testina sul nastro in ingresso).

anbmln.vnL

• Nessun AP è in grado di riconoscere il linguaggio minoppure

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

3. Macchine di Turing

Gli AP sono più potenti degli AF, nel senso che possono risolvere tutti i problemi risolubili 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 blank all’interno di un insieme finito, contenente fra gli altri anche il simbolo ( 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 MT a k-nastri è una 9-upla M = < Q, I, , O, , , q , Z , F > dove µ sp 0 0

• Q è un insieme finito di stati
• I è un alfabeto di ingresso finito
• È un alfabeto di memoria finito µ
• O è un alfabeto di uscita finito
• F Q) è l’insieme degli stati finali ( Eq
• Q) è lo stato iniziale ( E0
• Z è il simbolo iniziale dell’alfabeto di memoria ( ) EM0
• È 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 x y configurazione iniziale con sul nastro di ingresso e termina in una configurazione finale con sul nast