Algoritmi e principi dell'Informatica

AUTOMI

Gli automi rappresentano un classico esempio di modello operazionale; essi permettono di descrivere un

stati

sistema mostrando gli in cui esso si può trovare e come sia possibile passare da uno stato all’altro.

automa

Con il termine 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

automi a stati finiti

Gli (AF) sono il modello più usato in campo informatico. Un FSA rappresenta un sistema

che può trovarsi in un numero finito di stati diversi.

ingresso,

Come conseguenza di qualche che può assumere anche esso un insieme finito di possibili valori,

transizione

l’FSA effettua una da uno stato all’altro.

< Q, I, >

Un automa a stati finiti è una tripla E

Q è un insieme finito di stati

◦ I è un insieme finito di simboli d’ingresso

◦ è la funzione di transizione

◦ QxI

ci Q

si Q

Rappresentazione 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 S

S

Estendiamo ora la funzione , che rappresenta la transizione da uno stato ad un altro, in modo da

S

sequenza di transizioni;

rappresentare una se indica, a partire da uno stato, quale sarà lo stato in cui

S

si 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 SI

xi

19

5 ieI

5 canxeI

19,81 lqxl.ee

9

RICONOSCITORE

Per descrivere sitemi 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à.

riconosce/accetta

L’automa la sequenza di ingresso se l’AF raggiunge il suo stato finale partendo dal suo

stato iniziale.

riconoscitore < Q, I, , q , F >, Q, I

Un a stati finiti è una quintupla dove e sono quelle classiche

s

s 0

q Q stato iniziale F Q stati finali.

dell’AF, è detto e è detto insieme degli

E

E

0 riconosciuta

x I , x) F.

Una stringa è da un AF se e solo se (q E

E 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

trasduttore < Q, I, , q , F, O, >, Q, I, , q

Un a stati finiti (TF) è una 7-upla dove sono quelle del

s

ci n

0 0

O funzione di uscita.

riconoscitore, è un insieme finito di simboli di uscita e è la

4

La funzione di uscita può essere estesa a , in modo da produrre la stringa in uscita come conseguenza

4

della lettura di una sequenza di simboli in ingresso È i

xi lq.it

419 1

19,4 4 4

4 9 4

traduzione

Sia dato un trasduttore a stati finiti T, la associata a T è definita

0

Zr I EF

1

71 8

solo 190

190 se e

4 se

PROPRIETÀ Q n

• Sia dato un automa a stati finiti A, dove ha cardinalità ( |Q|=n ). Il linguaggio riconosciuto da A è non

x

vuoto se e solo se A accetta/riconosce una stringa con lunghezza 1 191

1 e n

Q n

• Sia dato un automa a stati finiti A, dove ha cardinalità ( |Q|=n ). Il linguaggio riconosciuto da A è

x

infinito se e solo se A accetta/riconosce una stringa con lunghezza 1

1

n 2n

e e

cicli

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 12

1 k

e i EL

x ywx, 1 k yw z

allora può essere scritta come dove < |w| < e viso

x

Intuitivamente esso afferma che, poiché, 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, x

tutte 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).

complemento;

La classe dei linguaggi accettata dagli automi a stati finiti è chiusa rispetto al 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

automi a pila

Gli (AP) sono modelli a stati (come gli AF) arricchiti di una memoria ausiliaria strutturata come

pila

una pila; la è una struttura che può essere letta e scritta e che influenza, con il suo contenuto, le

transizioni nella macchina a stati.

< Q, I, , , q , Z > Z

Un automa a pila è una 6-upla dove è l’insieme dei simboli della pila e è il

M

Ms 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). i), q

Ad ogni passo la testina legge un nuovo carattere e il dispositivo passa allo stato (q, dove è lo stato

S

i

precedente ed il simbolo letto. i)

La funzione di transizione non è però totale; perciò, se (q, è 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

i

visto 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 - mosse

E 819 A

E

i

Se è definita una - mossa , allora deve essere indefinita ; senza

819 A ti

E 819

E A

i

questa limitazione, l’automa non sarebbe più deterministico.

configurazione

La 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. c = < q, x, >, q x

Formalmente, la configurazione è una tripla dove è lo stato corrente, è la porzione non

ancora letta della stringa in ingresso e è il contenuto della pila.

ti

relazione binaria di transizione

Per un dato AP, la 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 condizioni

HA 8

8 Al

◦ 519

AB is

t

x x 413

ay a

p g 9

e Al

819

AB

◦ E da

t 413 eq

i f e

RICONOSCITORE

riconoscitore < Q, I, , , q , Z F > F

Un a pila è una 7-upla dove è 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.

q , i, A q’, > q q’

Se ( ) = < allora esiste un arco orientato che collega a e che è caratterizzato

s o

0 a, A/ .

dall’etichetta a

TRADUTTORE

Come per gli AF, è possibile estendere gli AP facendo si che essi possano produrre una stringa in uscita

come risultato della scansione e riconoscimento di una stringa in ingresso.

trasduttore = < Q, I, , , q , Z F, O, > O

Un a pila (TP) è una 9-pula T dove è un insieme finito di

me 0 0, y

simboli in uscita funzione di uscita.

e è la

Y

traduzione

Una è associata a T nel seguente modo

0

2 2 FF E

21 1 E

Zo f

e get

2 solo to

X 9

ego

se a

se

e zio

E

eq

eq.E.kz

e z

nessun y

9 y

per

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;

antony

i

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

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 - mosse

E

(ovvero mosse che non fanno avanzare la testina sul nastro in ingresso).

anbmln.vn

L

• Nessun AP è in grado di riconoscere il linguaggio min

oppure

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.

macchina di Turing

Una (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.

passo di computazione

Un 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.

macchina di Turing k-nastri M = < Q, I, , O, , , q , Z , F >

Una MT a è una 9-upla 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 (

◦ E

q Q)

è lo stato iniziale (

◦ E

0

Z è il simbolo iniziale dell’alfabeto di memoria ( )

◦ EM

0 è 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

x y

Una stringa viene tradotta in una stringa 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 nastro di

uscita.

PROPRIETÀ

• 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).

4. AUTOMI NON DETERMINISTICI

deterministici,

Tutti i modelli considerati finora sono 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. non deterministica

In alcuni casi una modellizzazione 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

Q x I -> (Q).

di transizione è data da :

ci p

delle parti

(Q) rappresenta l’insieme di Q, i cui elementi sono quindi insiemi di stati.

p

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. il

È il

Allora è definita da U

19 Ela

E

E 5 x

q

g design

x

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, in simboli f

5 190 n

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 &egra