automi a stati finiti - altervistatecnopalm.altervista.org/blog/wp-content/uploads/2014/11/... ·...
TRANSCRIPT
AUTOMI A STATI FINITI
G. Ciaschetti
CONTENUTI
• Definizione di sistema
• Classificazione dei sistemi
• Definizione di modello
• Algebra degli schemi a blocchi
• Sistemi sequenziali
• Automi a stati finiti
• Macchina di Turing
Definizione di sistema
Un sistema è un insieme di elementi che interagiscono tra loro per svolgere una
particolare funzione o raggiungere un determinato obiettivo.
ESEMPI
- il sistema nervoso
- il sistema politico
- un sistema di equazioni
- un sistema di irrigazione
- il sistema di elaborazione
- un robot
NON ESEMPI
- una classe
- i numeri naturali
- le istruzioni del linguaggio C
- i voti di uno studente
OBIETTIVO ?
Definizione di sistema
La teoria dei sistemi, ossia lo studio quantitativo dei sistemi, nasce dalla necessità di
analizzare un sistema per capire quali sono i suoi elementi e quali relazioni
intercorrono tra di essi, per
- comprenderne meglio il funzionamento
- spiegare il verificarsi di fenomeni naturali
- intervenire per modificare la risposta del sistema
- predire la risposta del sistema in futuro
Lo stato di un sistema è l’insieme dei valori che assumono tutti i diversi parametri del
sistema, cioè le grandezze fisiche o matematiche che descrivono “in che situazione” esso
si trova. Queste prendono il nome di variabili di stato.
Definizione di sistema
ESEMPIO: Il computer o sistema di elaborazione
Elementi
- CPU
- memoria RAM
- Hard Disk
- Tastiera
- Monitor
- Bus
- Mouse
- …
Relazione tra gli elementi
- la scheda madre, che con i suoi circuiti mette in
collegamento le varie parti del sistema
- la logica di funzionamento (algebra di Boole, circuiti
sommatori, CU, ciclo fetch/decode/execute, …)
Parametri del sistema
- Velocità CPU
- Occupazione HD
- …
Stati del sistema
- Spento
- Acceso, in attesa
- Acceso, in esecuzione
Obiettivo: archiviare ed elaborare informazioni (giocare, comunicare, ecc…)
Definizione di sistema
Un sistema aperto può essere visto come un dispositivo che trasforma gli ingressi
del sistema (le cause) nelle uscite del sistema (gli effetti).
Sistema(trasformazione)
ESEMPI:
- un computer con stampante trasforma le azioni dell’utente , la corrente elettrica e un foglio bianco in una pagina di un libro;
- una macchinetta del caffè trasforma il caffè in polvere, l’acqua, l’energia elettrica, i
soldi e l’azione di premere un tasto in un prelibato caffè caldo;
- un motore trasforma benzina in energia meccanica.
i u
ESEMPI O: sistema lampada/interruttore
Definizione di sistema
Elementi: interruttore, lampada
Obiettivo: illuminare (una stanza)
Stati: acceso, spento
Ingressi: int. chiuso, int. aperto
Uscite: luce, buio
INTERRUTTORE
STATO aperto chiuso
lampada accesa lampada spenta lampada accesa
lampada spenta lampada spenta lampada accesa
Tabella di transizione di stato
Tabella di trasformazioneINTERRUTTORE
STATO aperto chiuso
lampada accesa buio luce
lampada spenta buio luce
Definizione di sistema
ESEMPI O: sistema lampada/interruttore
INTERRUTTORE
STATO aperto chiuso
lampada accesa lampada spenta lampada accesa
lampada spenta lampada spenta lampada accesa
Tabella di transizione di stato
Tabella di trasformazioneINTERRUTTORE
STATO aperto chiuso
lampada accesa buio luce
lampada spenta buio luce
Diagramma degli stati
chiuso, luce
aperto, buio
spenta accesa
aperto, buio chiuso, luce
Definizione di sistema
Un sistema non è necessariamente un’entità fisica: esistono sistemi astratti che
servono a spiegare fenomeni naturali cercando di identificarne il rapporto
causa/effetto. In questa accezione, un sistema può essere visto come un modo, cioè
l’insieme di regole e/o relazioni tra elementi astratti che trasformano le cause in
effetti.
ESEMPI
- un sistema al totocalcio: come combinare più giocate tra loro
- il sistema per fare soldi: le azioni da intraprendere per ottenere un vantaggio
economico
- il sistema di scaricare la mia donna: senza commento (…)
Classificazione dei sistemi
naturali vs. artificiali: se presenti in natura o costruiti dall’uomo (es. sistema solare, computer)
statici vs. dinamici: se cambiano il loro stato nel tempo oppure no (es. sistema dei continenti, pendolo)
chiusi vs. aperti: se interagiscono o no con l’esterno (es. sistema di telecamere di un museo, sistema digerente)
deterministici vs. stocastici: se è possibile prevedere o meno la risposta del sistema (es. computer, sistema atmosferico)
combinatori vs. sequenziali: se sono dotati di memoria o meno (es. circuitoelettrico, ascensore)
stazionari (o invarianti): se la risposta del sistema non dipende dal particolare istante di tempo (es. pipeline)
continui: se l’evoluzione del sistema dipende dall’istante in cui si trova (es. sistema di lluminazione cittadino)
discreti: se l’evoluzione del sistema avviene “a scatti” (es. orologio digitale)
ESEMPI
- frigorifero (chiuso per chi deve trasportarlo, aperto per la massaia)
- quadro (statico per il visitatore, dinamico per il restauratore)
- sistema stellare (statico per un romantico, dinamico per un astrofisico)
- ascensore (discreto per l’utilizzatore, continuo per il progettista)
Si noti che la classificazione di un sistema in un modo oppure in un altro dipende
dall’osservatore, dal livello di dettaglio e dai fini dell’analisi che si vuole effettuare.
Classificazione dei sistemi
Definizione di modello
Un modello è una rappresentazione di un sistema, e permette di studiare un sistema
tralasciandone gli aspetti non essenziali ai fini della sua analisi.
ESEMPI
SISTEMA
- sistema stradale
- ponte sullo stretto
- sistema preda/predatore
- problema da risolvere
- sistema informativo aziendale
MODELLO
- mappa
- plastico/disegno 3D
- equazione differenziale
- algoritmo
- database
Un modello può essere matematico, fisico, grafico, logico, …
ESEMPIO
Definizione di modello
Un modello è in generale un’astrazione del sistema che esso rappresenta, cioè risulta
semplificato rispetto al sistema stesso. Modelli troppo semplici, però, possono essere
poco rappresentativi, mentre modelli troppo complessi possono risultare
inutilizzabili.
Occorre allora, in fase di modellazione del sistema, trovare un giusto compromesso
tra l’operatività del modello, cioè la sua fruibilità, e la sua aderenza, cioè quanto
precisamente esso rappresenta il sistema.
Inoltre, modelli più semplici sono in generale più robusti, ossia tendono a rimanere
validi anche a seguito di cambiamenti del sistema e del contesto, mentre modelli
troppo complessi possono risultare presto inutilizzabili (es. virus, dinosauri)
Un semplice modello per rappresentare e studiare i sistemi quello degli schemi a
blocchi. Il sistema è visto come un insieme di sottosistemi interconnessi tra loro,
ognuno dei quali è rappresentato mediante un blocco o blackbox (scatola nera):
si specifica, per ogni blocco, quali sono i suoi ingressi e le sue uscite, e non cosa c’è al
suo interno.
Gli elementi utilizzati in questo modello sono:
fi u
blocco di trasferimento u = f(i)
+
nodo sommatorei = i1 + i2
i1
i2
i1+i2
u1
u2
u3
i
diramazionei = u1 = u2 = u3
Algebra degli schemi a blocchi
Algebra degli schemi a blocchi
ESEMPIO: controllo automatico della temperatura
cella frigoriferatemperatura temperatura+
controllotemperatura
regolatemperatura
Sistemi combinatori
Un sistema combinatorio è un sistema che non ha memoria, cioè la risposta del
sistema dipende soltanto dall’ingresso che ad esso si applica, e non dal suo stato.
ESEMPIO: un tubo idraulico (un semplice sistema costituito da un solo elemento, un
tubo, che ha lo scopo di far arrivare ad una estremità il flusso d’acqua che entra
nell’altra estremità) è un sistema combinatorio, in quanto la grandezza quantità di
flusso in uscita dipende solo dalla grandezza quantità di flusso in entrata.
ESEMPIO: un circuito combinatorio formato da porte logiche è un sistema
combinatorio che ottiene una uscita booleana che dipende solo dal valore delle
variabili booleane in ingresso.
Sistemi combinatori
flussoin
ingresso
flussoin
uscita
x
y
z
zyx )(
Sistemi sequenziali
Un sistema sequenziale è un sistema che ha memoria, cioè la risposta del sistema
dipende dall’ingresso che ad esso si applica, e dal suo stato.
ESEMPIO: una vasca da bagno è un sistema sequenziale, in quanto la grandezza
quantità di flusso in uscita dipende dalla grandezza quantità di flusso in entrata, e
dallo stato della vasca, cioè dal livello dell’acqua presente. Maggiore è l’acqua presente
nella vasca, maggiore è la pressione, e dunque maggiore sarà il flusso in uscita, a
parità di flusso in ingresso.
ESEMPIO: un ascensore è un sistema sequenziale la cui uscita (il movimento che fa
l’ascensore), dipende dall’ingresso (il tasto premuto) e dallo stato (la posizione
dell’ascensore).
Sistemi sequenziali
i
u = f(i, s)
i
u = f(i, s)
livello = 0
stato
livello = 5
stato
Sistemi sequenziali
piano 1
stato
tasto 3
input
sali 2 piani
output
piano 4
stato
tasto 3
input
scendi 1 piano
output
Automi a stati finiti
Un automa a stati finiti è un sistema dinamico, sequenziale, invariante e discreto.
Significa che l’azione che l’automa intraprende (uscita) dipende solo da uno o più
segnali d’ingresso e dallo stato dell’automa. C’è un numero finito di possibili stati.
i
u = f(i, s)
sistema sequenziale
continuo
sistema sequenziale
discretoAUTOMA
i u = f(i, s)
Automi a stati finitiESEMPIO: Ascensore
start
pulsante
qualepulsante?
qualepiano?
qualepiano?
qualepiano?
fermo scendi scendi sali fermo scendi sali sali fermo
0 2
1
0 1 2 0 1 2 0 1 2
Automi a stati finitiESEMPIO: Semaforo
timer
start
c’èsegnale?
no
colore?
spegni rossoaccendi verde
accendi giallo
si
rosso verde
spegni verdespegni gialloaccendi rosso
giallo/verde
Automi a stati finiti
Un automa a stati finiti è una quintupla A = {I, U, S, , } definito da:
- Un insieme finito di valori degli ingressi I
- Un insieme finito di valori delle uscite U
- Un insieme finito degli stati S
- Un insieme di regole di transizione di stato, , che specifica lo stato futuro del
sistema noti lo stato attuale e l’ingresso : S x I S
- Un insieme di regole di trasformazione delle uscite, , che fornisce l’uscita
noti lo stato attuale e l’ingresso : S x I U
Automa di Mealy
Se l’uscita di un automa dipende direttamente dall’ingresso, si parla in questo caso di
automa improprio o automa di Mealy. Graficamente, può essere rappresentato
come segue:
Sn+1Sn
I U
= elemento di ritardo
Sn+1Sn
Automa di Moore
Se l’uscita di un automa non dipende direttamente dall’ingresso, si parla in questo
caso di automa proprio o automa di Moore. Graficamente, può essere
rappresentato come segue:
Sn+1
Sn
U
= elemento di ritardo
I
Sn Sn+1
Diagrama degli stati
Le regole di transizione di stato : S x I S e le regole di trasformazione delle uscite
: S x I U di un automa possono essere rappresentate in un diagramma degli
stati, un grafo orientato in cui i nodi corrispondono agli stati, e gli archi
corrispondono alle transizioni da uno stato all’altro del sistema.
ESEMPI O: sistema lampada/interruttore
diagramma degli stati
chiuso, luce
aperto, buio
spenta accesa
aperto, buio chiuso, luce
Grafo di Mealy
Se l’automa è l’automa di Mealy, il corrispondente diagramma degli stati è detto grafo
di Mealy. I nodi del grafo corrispondono agli stati, e le funzioni e sono riportate
sugli archi.
s0 s1
s2
i1, u2
i2, u2
i2, u2
i2, u2
i1, u2
i1, u1
Grafo di Moore
Se l’automa è l’automa di Moore, il corrispondente diagramma degli stati è detto
grafo di Moore. Nei nodi del grafo sono indicati gli stati e le uscite (ricordiamo,
infatti, che in questo automa le uscite sono direttamente collegate agli stati)e la
funzione è riportata sugli archi.
s0/u0s1/u1
i1
i2
i2
i2
i1
i1s2/u2
Diagrama degli stati
ESEMPI O: sistema lampada/interruttore
Grafo di Mealy
chiuso, luce
aperto, buio
spenta accesa
aperto, buio chiuso, luce
Grafo di Moore
chiuso
aperto
spenta/buio
accesa/luce
aperto chiuso
Questo sistema può essere rappresentato con entrambi i tipi di automi, in quanto l’uscita(buio/luce) dipende direttamente dallo stato della lampada (accesa/spenta)
Costruiamo un automa
ESEMPI O: vogliamo costruire un automa che riconosca la parla ORO in una stringa.
Supponiamo che la seconda O riconosciuta sia da considerare come la fine della sequenza, e non anche l’inizio di una nuova sequenza. Ad esempio, se la stringa in ingresso è ORORO verrà riconosciuta una sola parola e non due.
Insieme degli ingressi: I = {O, R}
Insieme delle uscite: U = {si, no}
Insieme degli stati: S = {s0, s1, s2} dove:
s0 : è lo stato di partenza: non è stato ancora riconosciuto nessun carattere della sequenza;
s1 : è lo stato in cui è stato riconosciuto il primo carattere della sequenza;
s2 : è lo stato in cui è stato riconosciuto il secondo carattere della sequenza.
Costruiamo un automa
Rappresentiamo ora le funzioni e con il diagramma di Mealy
s0 stato iniziale
Nello stato s0, se l’automa riceve in ingresso la lettera R, resta nello stesso stato, se invecericeve in ingresso la lettera O, passa nello stato s1.
s1s0
R, no
O, no transizione dallo stato iniziale s0 allo stato s1
Nello stato s1, quando cioè l’automa ha già riconosciuto il primo carattere, se l’automa riceve in ingresso la lettera R passa allo stato s2, se invece riceve in ingresso la lettera O, resta nello stesso stato.
s0
R, no
O, no transizione dallo stato iniziale s1 allo stato s2
Costruiamo un automa
s2
s1
O, no
R, no
Nello stato s2, quando cioè l’automa ha già riconosciuto il primo e il secondo carattere, se esso riceve in ingresso la lettera O torna allo stato s0 con uscita SI. Se invece riceve in ingresso la lettera R, torna allo stato s0 ma con uscita NO.
s0
R, no
O, no transizione dallo stato iniziale s2 allo stato s0
Costruiamo un automa
s2
s1
O, no
R, no
R, no
O, si
ESERCIZIO: qual è l’uscita dell’automa con la sequenza in ingresso OOORRRORRORO?
Costruiamo un automa
Ci chiediamo se è possibile costruire un automa di Moore per lo stesso riconoscitore di stringhe. La risposta è affermativa, ma occorre in questo caso aggiungere un ulteriore stato: lo stato finale corrispondente all’uscita SI.
s0, no s1, no
s2, nos3, si
R
O
O
RR
O
RO
ESERCIZIO: costruire un automa che riconosce la sequenza 1111 in una stringa di bit
Il modello matematico/logico
Se vogliamo effettivamente realizzare un automa, dobbiamo passare dalla suarappresentazione grafica (il grafo del diagramma degli stati) a una suarappresentazione matematico/logica, che ci permetterà di costruire i circuiti.
Facendo riferimento all’esempio precedente, il riconoscitore di sequenze ORO in unastringa, possiamo costruire il seguente modello:
ingressiO
x0
R 1
usciteno
z0
si 1
statis0
s1
s2
--
00
01
1110
y1y2
Il modello matematico/logico
TABELLA DI HUFFMAN
s0
R, no
O, no
s2
s1
O, no
R, no
R, no
O, si
variabilidi stato
y1 y2
0 00 11 1
1 0
variabilidi ingresso
x=0 x=1
01,0
01,000,1--,-
00,0
11,000,0--,-
ingressiO
x0
R 1
usciteno
z0
si 1
statis0
s1
s2
--
00
01
11
10
y1y2
Il modello matematico/logico
SINTESI DI CIRCUITI: Mappe di Karnaugh
variabile di stato y1
01
00 01 11 10
x
y1 y2
variabilidi stato
y1 y2
0 00 11 1
1 0
variabilidi ingresso
x=0 x=1
01,0
01,000,1--,-
00,0
11,000,0--,-
1ii
variabile di stato y2
0
1
00 01 11 10
x
y1 y2
1
i
i11
nnnyyxy 21
1
1
221
1
2 yxyyynnn
variabile di uscita z
0
1
00 01 11 10
x
y1 y2
i
i1
nyxz 1
Il circuito logico
x
y1n
z
y2n
y1n+1
y2n+1
y2n+1
y1n+1
y2n
y1n
ESERCIZIO: costruire il modello matematico e il circuito per l’automa che riconoscela sequenza 1111
La macchina di Turing
Alla base del concetto di sistema automatico di calcolo, usato da tutti i modernicomputer, c’è un modello di macchina astratta proposto nel 1936 dal matematicoinglese Alan Turing.
Si tratta di un automa a stati finiti, che fa riferimento alla normale attività dell’uomoquando deve eseguire dei calcoli: il lavoro è controllato dalla mente umana, mentre unfoglio di carta e una penna sono usati per segnare i dati e le operazioni, cioè vengonousati come supporto di memoria per l’input (dati) e l’output (risultati).
La macchina di Turing (MdT) può essere definita, intuitivamente, come undispositivo in grado di operare su un numero finito di simboli, mediante unasuccessione finita di passi e secondo determinate regole (programma), nonconsiderando (astrazione) i tempi di calcolo e i possibili limiti di spazio di memoria.
La macchina di Turing
La MdT è un dispositivo costituito da:
- Un nastro che rappresenta il supporto di memoria, costituito da un numero infinitodi caselle, ognuna delle quali può contenere un solo simbolo di un dato alfabeto;
- Una testina di lettura/scrittura (TLS) che accede a una singola casella, leggendoneil simbolo contenuto o scrivendoci su un nuovo simbolo;
- Un meccanismo di controllo (automa) che, in base al proprio stato, alle regole e alsimbolo letto, decide di eseguire una delle seguenti operazioni elementari:
1) comandare alla TLS di scrivere unnuovo simbolo
2) spostare a sinistra la TLS di unacasella
3) spostare a destra la TLS di unacasella
4) fermare la macchina
La macchina di Turing
Formalmente, la macchina di Turing è definita da una quintupla
MdT = {S, IU, , , }
dove:
S insieme degli stati, tra cui lo stato iniziale s0 e lo statofinale sF
IU insieme dei simboli di input/output
: S x IU S funzione di transizione di stato: dato uno stato e unsimbolo in input, pone la macchina in un nuovo stato
: S x IU IU funzione di trasformazione delle uscite: dato uno stato eun simbolo di input, determina un simbolo di output
: S x IU {sx, dx, =} funzione di movimento della TLS (sposta a sinistra di unacasella, sposta a destra di una casella, non muovere)
La macchina di Turing
La parte di controllo della MdT può essere rappresentata mediante un diagramma deglistati, utilizzando il grafo di Mealy, riportando sugli archi del grafo anche glispostamenti della TLS, oltre agli ingressi e le uscite.
Tra i simboli dell’insieme IU, c’è un simbolo particolare denotato con # che rappresentail simbolo nullo: è il simbolo che si trova in tutte le caselle del nastro all’inizio.Successivamente, su alcune delle caselle del nastro verranno scritti (dall’esterno) isimboli di input che la macchina di Turing dovrà leggere. Una volta dato l’input, laMdT può cominciare il suo lavoro partendo dallo stato s0 .
Il risultato finale dell’elaborazione è contenuto nelle caselle del nastro, quando la MdTsi trova nello stato finale sF .
La macchina di Turing
Definiamo la nostra MdT:
IU {0, 1, #}
Spostamenti della TLS {=, <}
S {s0, s1, s2, sF} dove
s0 = stato iniziale: la testina si trova sul bit meno significativo del numero binario
s1 = assenza di riporto: la MdT dovrà copiare i restanti bit muovendosi verso sinistra
s2 = presenza di riporto: la MdT cancella il simbolo 1 e scrive 0, oppure cancella il
simbolo 0 e scrive 1, e si muove a sinistra
sF = stato finale: la macchina ha finito il suo compito e si ferma
ESEMPIO: progettare una MdT che calcola il successivo di un numero binario
0 1 1 1 0 1##### # # # # # #
La macchina di Turing
Per definire le funzioni , , , costruiamo il diagramma degli stati (di Mealy)
All’inizio, cioè nello stato s0, se la MdT legge in ingresso il carattere #, passa nello statofinale sF senza scrivere nulla: significa che non è stato dato nessun numero in input. Seinvece legge il simbolo 0, passa nello stato s1 (assenza di riporto), scrive 1 e si muove asinistra. Se, infine, legge il simbolo 1, passa nello stato s2 (presenza di riporto), scrive 0 e simuove a sinistra.
s0
sFs2
0,1,<
1,0,<
1 0 # #
0 1 # #
s1
s0
s0
1 1 # #
s1
0 0 # #
s2
La macchina di Turing
Quando la MdT si trova nello stato s1, se legge in ingresso il carattere #, passa nello statofinale sF senza scrivere nulla: significa che ha terminato il proprio lavoro. Se invece leggeil simbolo 0 o il simbolo 1, resta nello stato s1 (assenza di riporto: deve solo ricopiare irestanti simboli), riscrive il simbolo letto e si muove a sinistra.
s0
sFs2
0,1,<
1,0,< #,#,=
0,0,<1,1,<
s1 1 0 1 #
0 1 1 #
s1
s1
1 0 1 #
s1
0 1 1 #
s1
La macchina di Turing
Quando la MdT si trova nello stato s2, se legge in ingresso il simbolo #, passa nello statos1, scrive 1 e si sposta a sinistra. Se invece legge il simbolo 0, passa nello stato s1, scrive 1 esi sposta a sinistra. Se invece legge il simbolo 1, resta nello stato s2, scrive 0 e si sposta asinistra
s0
sF
0,1,<
1,0,< #,#,=
0,0,<1,1,<
s1
s21,0,<
# # 1 0
0 0 1 #
s2
s2
# 1 1 0
s1
0 1 1 #
s1
0 1 0 #
s2
0 0 0 #
s2
La macchina di TuringA titolo di esempio, riportiamo il comportamento della macchina sull’input 1011
0 1 0 1 1 ### # # # # #
s0
0 1 0 1 0 ### # # # # #
s2
0 1 0 0 0 ### # # # # #
s2
0 1 1 0 0 ### # # # # #
s1
0 1 1 0 0 ### # # # # #
s1
0 1 1 0 0 ### # # # # #
sF
La macchina di Turing
ALGORITMI E MACCHINA DI TURING
Ricordando la definizione e le proprietà di un algoritmo (vedi dispense Le basi dellaprogrammazione della classe III), notiamo che esiste una stretta analogia tra unalgoritmo e la MdT:
1) usa un dispositivo di calcolo2) procede in modo discreto3) deve essere finito4) deve essere deterministico5) non deve essere ambiguo6) deve essere generale7) deve essere completo
ALGORITMO
1) è un dispositivo di calcolo2) passa da uno stato all’altro in modo discreto3) ha un numero finito di stati e di transizioni di
stato, e uno stato finale4) è deterministica5) ogni passo è specificato con esattezza6) è generale7) se opportunamente progettata, è completa
MdT
Un algoritmo è una MdT in grado di risolvere una data classe di problemi
La macchina di Turing
TESI DI CHURCH-TURING
L’insieme delle funzioni computabili, ossia dei problemi risolvibili con un sistema di
calcolo automatico, coincide con l’insieme delle funzioni Turing-computabili, ossia
l’insieme dei problemi per cui è possibile costruire una MdT che li risolve.
La tesi di Church-Turing non è dimostrabile: occorrerebbe prendere tutti i possibiliproblemi per cui è possibile sviluppare un algoritmo che li risolve, e costruire larelativa MdT, il che è impossibile.
La tesi di Church-Turing tuttavia è confutabile, ma nessuno finora è riuscito a farlo: èsempre stato possibile costruire una MdT per la risoluzione di un problemacomputabile.
THE END