AUTOMI A STATI FINITI - Altervistatecnopalm.altervista.org/blog/wp-content/uploads/2014/11/... ·...

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 ?


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.


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…)


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


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



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


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.


diagramma degli stati

chiuso, luce

aperto, buio

spenta accesa


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


Grafo di Mealy

chiuso, luce

aperto, buio

spenta accesa


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.


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



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



s2

s1

O, no

R, no

R, no

O, si

ESERCIZIO: qual è l’uscita dell’automa con la sequenza in ingresso OOORRRORRORO?


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


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


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


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


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


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


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


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


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


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

AUTOMI A STATI FINITI - Altervistatecnopalm.altervista.org/blog/wp-content/uploads/2014/11/... ·...

Documents

Transcript of AUTOMI A STATI FINITI - Altervistatecnopalm.altervista.org/blog/wp-content/uploads/2014/11/... ·...