Home

Federica EU

1/17

Valeria Vittorini » 3.Il modello di Automa

Fondamenti di Informatica

Il modello di Automa

Sommario

Definizione di Automa (a numero di stati finito)
Modello Concettuale
Tabella di stato
Diagramma di stato
Classi di Automi
Esempi

Il modello di automa

E’ un modello matematico
Fornisce una prima astrazione di macchina “dotata di memoria” che esegue algoritmi
Introduce il concetto fondamentale di “STATO”
E’ un modello utilizzato anche nella progettazione di linguaggi di programmazione e nella progettazione di circuiti elettronici (macchina sequenziale)

Definizione formale: modello matematico

Un automa a numero di stati finito (ASF) è una quintupla:

<Q, I, U, t, w>

Dove:

Q: insieme finito di stati interni q: q ε Q
I: insieme finito di simboli di ingresso i: i ε I
U: insieme finito di simboli in uscita u: u ε U
t: funzione di transizione t: QxI → Q
w: funzione di uscita w: QxI → U

Rappresentazione grafica

E’ possibile rappresentare graficamente un ASF mediante un grafo detto diagramma degli stati
Stato: rappresentato da un nodo (cerchio)
Transizione: rappresentata da un arco orientato (freccia)
Ciascun arco viene etichettato con l’ingresso che causa la transizione e la conseguente uscita, separati da un simbolo (/)
Se l’uscita non è specificata, può essere indicata con il simbolo “-”

Rappresentazione tabellare

E’ possibile rappresentare un ASF anche mediante una tabella detta Tabella delle transizioni di stato
La tabella specifica per ogni coppia (stato, simbolo di input) in quale stato transita l’automa

Classi di automi

Esistono diverse classi di ASF, tra cui:

Automi deterministici: per ogni coppia stato-simbolo in ingresso è data una ed una sola transizione allo stato successivo
Automi non deterministici: per ogni coppia stato-simbolo in ingresso possono esservi più stati di destinazione

Gli Automi deterministici possono essere senza output, o con output (Automi di Mealy, Automi di Moore).

Automi di Mealy e di Moore

La differenza fondamentale tra un ASF di Mealy e un ASF di Moore è la seguente:

Nel modello di Mealy le uscite sono funzione sia degli stati che degli ingressi: W: QxI → U
Nel modello di Moore le uscite sono funzioni solo degli stati: W: Q → U

E’ stato dimostrato che i due modelli sono equivalenti e che è possibile trasformare una automa di Mealy in uno di Moore che esibisce lo stesso comportamento terminale.

Esempio 1

Progettiamo un ASF deterministico che riconosca le sequenze in input sull’insieme di simboli I ={0,1} in cui le occorrenze del simbolo 1 sia pari:

1) Bisogna definire l’algoritmo che risolve il problema:

Se il simbolo “letto” è 0 il numero di occorrenze del simbolo 1 resta invariato.
Se il simbolo “letto” è 1 se il numero di occorrenze attuali è pari diviene dispari e viceversa se il numero di occorrenze attuali è dispari diviene pari. Per definizione un numero di occorrenze 0 è considerato pari.

2) Bisogna realizzare l’automa:

L’automa ha due stati: Pari (P) e Dispari (D). Si supponga che lo stato iniziale sia P.
La sequenza viene elaborata un simbolo alla volta (da destra verso sinistra).
Se il simbolo “letto” è 0 l’automa “transita” nello stesso stato in cui già si trova.
Se il simbolo “letto” è 1 se l’automa si trova nello stato P transita nello stato D e viceversa.

Esempio 1

L’automa richiesto è qui rappresentato graficamente e mediante la sua tabella di transizione degli stati.

Esempio 2

Progettiamo un ASF deterministico “complementatore”: l’automa dato un numero decimale n di N cifre “calcola” il suo complemento C (C=10^N-n):

1) Bisogna definire l’algoritmo che risolve il problema:

Tutte le cifre di coda pari a 0 restano invariate
La prima cifra da destra diversa da 0 viene sostituita con il suo complemento a 10
Tutte le altre cifre vengono sostituite con il loro complemento a 9

Esempio: n=60940 (N=5) quindi C=100000-60940

0 viene lasciato inalterato
4 viene sostituito con 6
9 viene sostituito con 0, 0 viene sostituito con 9, 6 viene sostituito con 3

Risultato: 39060

Esempio 2

2) Bisogna “realizzare” l’automa:

Supponiamo che una sequenza in ingresso sia sempre iniziata dal simbolo * e terminata dal simbolo !. Supponiamo inoltre che contenga almeno una cifra diversa da zero (cioè che non rappresenti il numero 0). Nell’esempio di prima la sequenza è: !60940*
L’insieme dei simboli in ingresso è in uscita è: {*,!,0,1,2,3,4,5,6,7,8,9}
L’automa ha tre stati: Coda, Testa e Riposo
Lo stato iniziale è Riposo. Quando viene letto il simbolo * l’automa passa nello stato Coda. L’uscita è *.
L’automa resta nello stato Coda finché non viene letta una cifra diversa da 0. Fino a quel momento per ogni ingresso l’uscita è 0. Appena viene letta una cifra diversa da 0 l’uscita è la cifra che rappresenta il suo complemento a 10 e l’automa transita nello stato Testa.
L’automa resta nello stato Testa finché non viene letto il simbolo ! che causa il transito nello stato Riposo. L’uscita è !.
N.B. L’automa ha come comportamento terminale una sequenza a sua volta iniziata da * e terminata da !.

Esempio 2

L’automa richiesto è qui rappresentato graficamente.

Macchina di Von Neumann: schema di esecuzione di un algoritmo per la moltiplicazione di numeri interi

Modello concettuale di automa

La macchina risponde ad una sequenza (stringa) di simboli di ingresso con una sequenza (stringa) di simboli in uscita che è funzione dello stato iniziale q0 della macchina

Ricapitolando

Un ASF è una “macchina elaboratrice” con:

un insieme finito di stati (possibili configurazioni interne);
input, sequenza (finita) di simboli;
output, sequenza (finita) di simboli.

Computazione:

si parte da uno stato iniziale;
si consuma un simbolo di input;
sulla base di input e stato corrente si produce un simbolo di output e/o ci si muove su un nuovo stato;
si procede finché non si raggiunge uno stato finale.