automi a stati finiti

sistema per dire se una stringa è fatta in un certo modo

come per le espressioni regolari:

• stringhe riconosciute
• stringhe non riconosciute

espressioni regolari vs. automi

espressioni regolari

si scrive la forma delle stringhe da cercare

automi

meccanismo che opera passo per passo sui caratteri

espressione e automa: esempio

[ab]c*(abc|dd)

un carattere fra a e b, un numero qualsiasi di c, poi abc oppure dd

automa:

spiegazione…

espressione e automa

[ab]c*(abc|dd)

0 -a->  1  -a-> 2 -b-> 3 -c-> ((4))
  -b-> (c) -d-> 5 -d-------->

cerchietti = stati in cui può trovarsi l'automa

• inizio: stato 0
• primo carattere a o b si va in 1
• con carattere c: si resta in 1
• con a si va in 2
• …

riconoscimento

se alla fine della stringa ci si trova in uno stato con doppio cerchio la stringa è accettata

automi = espressioni regolari

(automa accetta se e solo se espressione collima)

definizione (quasi) formale

automa:

• stati (i pallini)
• collegati fra loro da archi (le frecce)
• con etichette (i caratteri sopra le frecce)

funzionamento…

funzionamento degli automi

• inizio: stato iniziale
• la stringa viene fornita un carattere per volta
• se l'automa è nello stato i
  e riceve il carattere c
  segue la freccia da i che ha il carattere c

accettazione/rifiuto:

• freccia non esiste: stringa rifiutata
• se alla fine in stato finale: stringa accettata

funzionamento: esempio

automa di prima

stringa 'accabc'

[]

fine stringa → stato finale

stringa accettata

esempio con stringa sbagliata

stringa 'aacb'

[]

no uscita da stato → stringa rifiutata

esempio con stringa troppo corta

stringa 'bcab'

[]

ultimo stato non doppio → stringa rifiutata

stringhe rifiutate

due possibili motivi:

1. si arriva a uno stato che non ha archi uscenti etichettati con il prossimo carattere
2. si termina su uno stato non finale

esempio

   0  --ae-> [1]
(bcd) <-bcd- (ae)

accetta le stringhe che:

• sono fatte di caratteri a,b,c,d,e
• finiscono con una vocale fra queste

uguale all'espressione regolare ^[abcde]*[ae]$

arco con più lettere: seguire per una qualsiasi di queste

cappi = archi che portano allo stesso stato

progettazione degli automi

• capire quali stati servono
  (es: ultima lettera vocale / consonante)
• inserire gli archi

stati finali

   0  --ae-> [1]
(bcd) <-bcd- (ae)

non vuol dire che non si può andare oltre

qui: da 1 (finale) si va in 0

stato finale = se si finisce lì la stringa è accettata

automi: note

• frecce con più caratteri: va seguita se ne arriva uno
• una freccia può portare al nodo stesso
• si può andare oltre lo stato finale

macchinetta del caffè

ingresso: monete da 5 e 10 centesimi

eroga con almeno 15 centesimi
non accetta monete successive
niente resto

omesso: ricomincia dall'inizio dopo l'erogazione

+------------+       +--------+       +-----------+
| rilevatore |  -->  | automa |  -->  | erogatore |
|   monete   |       +--------+       |   caffe'  |
+------------+                        +-----------+

automa

          -----10c----->
0 -5c-> 1 -5c-> 2 -5c--> (3)
  -----10c---->   -10c->

stati: indicano i centesimi inseriti

stati finali: abbastanza centesimi per il caffè

nessuno stato successivo a quelli finali:
non accetta successive monete quando bastano

niente resto
più avanti: automa con resto

stato = memoria

esempio:

automa che accetta le stringhe che hanno il terzo carattere uguale al primo

serve "memorizzare" il primo carattere

stato-memoria = stati diversi a seconda del primo carattere

terzo carattere uguale al primo

realizzare l'automa che accetta quasiasi stringa in cui il primo carattere è uguale al terzo

caratteri a, b, c

terzo uguale al primo: soluzione

0 -a-> 1 -*-> 2 -a-> [3] ()*
  -b-> 4 -*-> 5 -b-> [6] ()*
  -c-> 7 -*-> 8 -c-> [9) ()*

* = qualsiasi carattere

in questo caso: uguale ad a,b,c

primo carattere a → stato 1
da qui: 2 per forza
se arriva a: stato finale

ma: a in 5 o 8 → rifiuto

cicli su stati finali: va bene qualsiasi cosa arrivi dopo

esercizio

caratteri 0 e 1

accetta sequenza se: valore numerico > 4

es: accetta 101 e 1000
rifiuta 100, rifiuta 11

maggiore di quattro: soluzione

                      (01)
 0 -1-> 1 -1-> 2 -01-> (3)
(0)       -0-> 4 -1-> (5) (01) 
                 -0-> 6 -01-> 7
		             (01)

spiegazione?

spiegazione

                      (01)
 0 -1-> 1 -1-> 2 -01-> (3)
(0)       -0-> 4 -1-> (5) (01) 
                 -0-> 6 -01-> 7
		             (01)

zeri iniziali non cambiano il valore: cappio

diramazione ad albero

stringa che rappresenta valore >4: accetta

caratteri successivi: il valore aumenta
(sempre stato finale)

sequenze ordinate

stringhe di lettere {a,b,c,d}

accettare solo stringhe con lettere in ordine

accetta per esempio aaaaa, accetta bbbcccc e abcd e aaaddd

non accetta aaaba e nemmeno abcda

sequenze ordinate: soluzione

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)

ottenuto come?

progettazione automi: metodo

stato = condizione sulla sequenza arrivata finora

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)

in questo caso:

stato 0 = lettere arrivate finora in ordine, ultima a
stato 1 = lettere arrivate finora in ordine, ultima b
stato 2 = lettere arrivate finora in ordine, ultima c
stato 3 = lettere arrivate finora in ordine, ultima d

dice dove andare

progettazione: stato successivo

stato 2 = lettere arrivate finora in ordine, ultima c

prossimo stato:

• nessuno (stringa rifiutata) se arriva a oppure b;
• stesso stato se arriva c
• stato 3 se arriva d

deriva dalla definizione di stato…

stato attuale e successivo

es: stato 2, arriva d:

• stato 2 = "sequenza precedente ok, ultimo carattere c"
• arriva d
• condizione attuale = "sequenza ok, ultimo d"

quindi: prossimo stato 3

progettazione degli automi: principio

assumendo una certa condizione vera (es. lo stato indica l'ultimo carattere di una sequenza in ordine), si fa in modo tale che all'arrivo del successivo carattere la condizione sia ancora vera

per induzione, la condizione è sempre vera

in generale: condizione = definizione dello stato

progettazione degli automi: in pratica

• si stabiliscono quali condizioni vanno distinte
• per ognuna si realizza uno stato
• sulla base delle condizioni di s e q si stabilisce se

    c
  s → q
  

sintesi con porte logiche

• si modifica l'automa
• si rappresentano ingressi, uscite e stati in binario
• si scrive la funzione di stato successivo
• si scrive la funzione che distingue gli stati accettanti
• si sintetizzano queste funzioni con porte logiche

sintesi: modifica automa

non possono mancare archi uscenti

si introduce un singolo stato non finale p

se da s manca l'arco con c, se ne mette uno che va in p

p ha un cappio per tutti i caratteri

modifica automa: esempio

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)

nuovo stato 4

qui vanno gli archi mancanti:

• da 1 con ingresso a
• da 2 con ingressi a e b
• da 3 con ingressi a, b e c

automa modificato

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)
          |        |        |
          a       a,b      a,b,c
          |        |        |
          |        |        V
          |        +-----> 4 (a,b,c)
          |                 ^
          +-----------------+

funzione di stato successivo

dati: stato e carattere

calcola: stato successivo

sempre definita (automa modificato)

tabella: una riga per ogni stato e carattere

tabella stato successivo

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)
          |        |        |
          a       a,b      a,b,c
          |        |        |
          |        |        V
          |        +-----> 4 (a,b,c)
          |                 ^
          +-----------------+

es: da 1 con ingresso d si va in 3

riga:

tabella complessiva

una riga per ogni stato e ogni carattere

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)
          |        |        |
          a       a,b      a,b,c
          |        |        |
          |        |        V
          |        +-----> 4 (a,b,c)
          |                 ^
          +-----------------+

da 0 con a si va in 0
da 0 con b si va in 1
ecc.

codifica in binario

stati 0,1,2,3,4

servono tre bit

caratteri a,b,c,d

bastano due bit:

• a=00
• b=01
• c=10
• d=11

tabella, in binario

0,1,2,3,4 e a,b,c,d si mettono in binario

sintesi

ogni bit di succ si sintetizza con un circuito

es: si tiene solo il primo bit

sintesi

sintesi primo bit: si tolgono il secondo e il terzo da succ

sintesi primo bit: si tolgono il secondo e il terzo da succ

resta una tabella con una uscita

solito sistema:

• righe con uscita 1 → and degli ingressi
• or di tutti questi

stati finali

accetta=1, rifiuta=0

per ogni stato, dice se è finale

sintesi: righe 1, ecc.

circuito complessivo

         +----+
in ------+ SS |
     +---+    +---+
     |   +----+   |
     |            |
     +---------------+
                  |  |
   +--------------+  |
   |                 |
   |    +-----+      |     +-----+
   +----+ MEM +------+-----+ ACC +----- out
        +-----+            +-----+

SS

i tre circuiti dello stato successivo (visto)

ACC

il circuito che dice se uno stato è finale (visto)

MEM

la memoria di stato

memoria=?

memoria

devo memorizzare tre bit (lo stato)

tre flip-flop

     +----+
-----|    |-----
  +--|>   |
  |  +----+
  |
  |  +----+
-----|    |-----
  +--|>   |
  |  +----+
  |
  |  +----+
-----|    |-----
  +--|>   |
  |  +----+
  |
 clk

clk = clock

dice quando memorizzare lo stato successivo

automi realizzati con programma

versione software

una variabile per lo stato

si guarda un carattere per volta

stato="0"
stringa="acccdd"

for input in stringa:
			# stato 0
  if stato == '0':
    if input == 'a':
      stato='0'
    elif input == 'b':
      stato='1'
  …

if stato!='4':
  print 'stringa accettata'
else:
  print 'stringa rifiutata'

programma complessivo

stato="0"
stringa="acccdd"

for input in stringa:
  print 'stato: ' + stato 
  print 'in: ' + input
			# stato 0
  if stato == '0':
    if input == 'a':
      stato='0'
    elif input == 'b':
      stato='1'
    elif input == 'c':
      stato='2'
    elif input == 'd':
      stato='3'
			# stato 1
  if stato == '1':
    if input == 'a':
      stato='4'
    elif input == 'b':
      stato='1'
    elif input == 'c':
      stato='2'
    elif input == 'd':
      stato='3'
			# stato 2
  if stato == '2':
    if input == 'a':
      stato='4'
    elif input == 'b':
      stato='4'
    elif input == 'c':
      stato='2'
    elif input == 'd':
      stato='3'
			# stato 3
  if stato == '3':
    if input == 'a':
      stato='4'
    elif input == 'b':
      stato='4'
    elif input == 'c':
      stato='4'
    elif input == 'd':
      stato='3'
			# stato 4
  if stato == '4':
    if input == 'a':
      stato='4'
    elif input == 'b':
      stato='4'
    elif input == 'c':
      stato='4'
    elif input == 'd':
      stato='4'

  print "nuovo stato: "+stato
  print '----'

if stato!='4':
  print 'stringa accettata'
else:
  print 'stringa rifiutata'

programma, versione con dizionario

stato="0"
stringa="acccdd"

for input in stringa:
  print 'stato: ' + stato 
  print 'in: ' + input
  stato={
	# stato 0
    '0a': '0',
    '0b': '1',
    '0c': '2',
    '0d': '3',
	# stato 1
    '1a': '4',
    '1b': '1',
    '1c': '2',
    '1d': '3',
	# stato 2
    '2a': '4',
    '2b': '4',
    '2c': '2',
    '2d': '3',
	# stato 3
    '3a': '4',
    '3b': '4',
    '3c': '4',
    '3d': '3',
	# stato 4
    '4a': '4',
    '4b': '4',
    '4c': '4',
    '4d': '4'
  }[stato+input]
  print "nuovo stato: "+stato
  print '----'

if stato!='4':
  print 'stringa accettata'
else:
  print 'stringa rifiutata'

definizione formale di automa

in termini matematici

serve per dimostrazioni, ecc.

• ingressi
• stati

poi: stato iniziale, stati successivi, stati finali

insiemi

I

insieme degli ingressi

S

insieme degli stati

esempi:

• caratteri in ordine: I={a,b,c,d} e S={0,1,2,3}
• valore > quattro: I={0,1} e S={0,1,2,3,4,5,6,7}

stati iniziale e finali

insieme di tutti gli stati: S

stato iniziale:

s₀ è un elemento di S

stati finali (doppio cerchio):

A è un sottoinsieme di S

dal punto di vista matematico:
s∈S e A⊆S

stati: esempi

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)

                      (01)
 0 -1-> 1 -1-> 2 -01-> (3)
(0)       -0-> 4 -1-> (5) (01) 
                 -0-> 6 -01-> 7
		             (01)

stato iniziale = quello da cui si parte

stati finali = quelli con il doppio cerchio

stato successivo

da stato s e ingresso i si passa a un nuovo stato

è una funzione matematica:

N : S × I → S

permette di calcolare lo stato successivo

N(s,i)=s' vuol dire:
se in s arriva i, si va in s'

stato successivo: esempio

          +-----d------------+
+-----d--------------------+ |
| +---c------------+       | |
| |       |        V       V V
(0) -b-> (1) -c-> (2) -d-> (3)
(a)      (b)      (c)      (d)

da 0 con c si va in 2

quindi: N(0,c)=2

e poi:

N(2,d)=3
N(0,a)=0
N(3,a) indefinito
ecc.

funzione e tabella

N : S × I → S
dati s e i fornisce lo stato successivo N(s,i)

anche la tabella:

si guarda la riga con s e i
la terza casella della riga è lo stato successivo

sono di fatto la stessa cosa

automa: definizione completa

un automa è una quintupla ⟨I, S, s₀, N, A⟩

I

un insieme, detto insieme degli ingressi

S

un insieme, detto insieme degli stati

s₀

un elemento di S, detto stato iniziale

A

un sottoinsieme di S, detto insieme degli stati finali

N

una funzione S×I→S, detta funzione di stato successivo

definizioni in termini di insiemi

già quasi tutto definito in termini di:

• insieme
• elemento di un insieme
• sottoinsieme

tranne: funzione di stato successivo

funzione N, definita come insieme

prodotto cartesiano:

S×I×S = insieme di triple ⟨s,i,s'⟩ con s∈S, i∈I e s'∈S

funzione (parzialmente definita):

N:S×I→S = sottoinsieme di S×I×S
tale che due terne non hanno gli stessi primi due elementi

intuitivamente: ⟨s,i,s'⟩ se N(s,i)=s'

serve dopo, per definire gli automi non deterministici

stato dopo una stringa

stringa c₁c₂ … c_n-1c_n

porta allo stato:

N(N(N( … N(N(s₀,c₁),c₂) … ),c_n-1),c_n)

complicato?

stati intermedi

• stato iniziale s₀
• primo carattere c₁, porta a N(s₀,c₁)
• secondo carattere c₂, porta a N(N(s₀,c₁),c₂)
• terzo carattere, ecc.

carattere c_i → applicare N(…,c_i)

N(N(N( … N(N(s₀,c₁),c₂) … ),c_n-1),c_n)

accettazione

N(N(N( … N(N(s₀,c₁),c₂) … ),c_n-1),c_n)

se questo è uno stato finale, la stringa c₁c₂ … c_n-1c_n è accettata

altrimenti è rifiutata

c₁c₂ … c_n-1c_n accettata se e solo se N(N(N( … N(N(s₀,c₁),c₂) … ),c_n-1),c_n) ∈ A

vincolo sulla funzione

N non contiene due triple ⟨s,i,s'⟩ con gli stessi s e i

⟨s,i,s'⟩ ∈ N vuol dire:
da stato s con ingresso i si va a stato s'

no due triple con stessi s e i → stato successivo unico

più triple con stessi s e i → più stati successivi

automi non deterministici

deterministici

s, i → s'

non deterministici

s, i → s', s'', …

stando in uno stato, arriva un carattere: si può andare in più stati successivi

cioè, 'nche senso?

sistemi teorici e reali

reali

dato uno stato, arriva un input: si va in un altro stato

teorici

volendo, si può immaginare di andare in più stati diversi

sempre con un singolo carattere di input

automa non deterministico: esempio

      (a) -ad-> 2
 -ac-> 1 -ac-> 3
0*       \-d->
 -ab-> 4 -d-> 5
         -d-> (6)

---

non determinismo: dove vado?

da 0 con a: vado in 1 o in 4?

si fanno entrambe le scelte

si finisce in 1 e in 4 insieme

---

due stati insieme

vado in 1 e anche in 4

ora arriva d

---

da due stati, dove vado?

sono in 1 e 4

con d posso andare:

• da 1 in 2 e 5
• da 4 in 5 e 6

vado in tutti questi

---

stati dopo due caratteri

arrivo in 2, 5 e 6

uno di questi è finale → stringa accettata

Non pensate a un automa non deterministico come a un sistema reale che si trova in più stati insieme, perché niente del genere può esistere. Pensatelo come a un disegno con cerchietti e freccie in cui alcuni cerchietti sono marcati di nero: su un disegno si possono marcare anche due o tre cerchietti insieme. Il disegno non è un modo di vedere gli automi, è quello che sono: non esiste un meccanismo reale non deterministico, si tratta sempre e comunque di una formalizzazione teorica, un disegno di freccie e cerchietti su cui se ne possono marcare alcuni.

---

ramificazioni, riassunto

(animazione)

esempio: stringa ad

• da 0, con a: si va in 1 o in 4
• arriva d:
  • da 1 si va in 2 o in 5
  • da 4 si va in 5 o in 6

vanno considerate tutte le possibilità

si arriva in 2, 5 e 6
6 finale → stringa ad accettata

---

quindi: cosa scelgo?

non scelgo niente: sono sistemi teorici

si considerano tutte le possibilità

con ad si arriva in 2, 5 o 6

6 finale → stringa accettata

---

percorsi possibili

si parte dallo stato iniziale

le frecce indicano gli spostamenti ammessi

la prima a permette di raggiungere 1 o 4
(nota: non permette di restare in 0)

c'è un percorso per uno stato finale → stringa accettata

---

scelte obbligate o inesistenti

cc porta solo in 3

bc non porta da nessuna parte

in un automa non deterministico possono esserci anche scelte obbligate o inesistenti

non solo scelte multiple

---

accettazione

una stringa porta a più stati

uno di questi finale → stringa accettata

---

definizione formale

automa: uguale, togliendo il vincolo

quintupla ⟨ I, S, s₀, N, A ⟩

tutto uguale, ma N non ha il vincolo sulle terne
è N⊆S×I×S

---

stato di arrivo

stato attuale s → insieme di stati attuali SA

successivo(SA, i) = {s' | ⟨s,i,s'⟩∈N e s∈SA}

---

stato di una stringa

si applica successivo una volta per ogni carattere

stringa c₁c₂…c_n-1c_n:

successivo( successivo( … successivo( successivo({s₀}, c₁), c₂), … c_n-1), c_n)

è un insieme di stati

uno di questi stati in A → stringa accettata

---

vantaggi del non determinismo

si applica a varie cose, oltre agli automi

in generale:

non determinismo = varie scelte possibili a ogni passo

esempio: il problema dei 150 cavalieri

---

scelte e soluzioni

forma generale di molti problemi:

• scegliere dei valori
• verificare se soddisfano una condizione

non determinismo: formalizza la scelta

---

il problema dei 150 cavalieri

in questo caso:

• scegliere le posizione per ogni cavaliere
• verificare che non ci siano rivali vicini
  che non ci siano due cavalieri allo stesso posto
  che ogni cavaliere abbia un posto

---

soluzione non deterministica

• scegli posizione cavaliere 0
• scegli posizione cavaliere 1
• …
• scegli posizione cavaliere 149
• verifica posizioni e rivalità

se esiste una sequenza di scelte che porta a una soluzione, allora esiste una disposizione accettabile

---

programma

su un ipotetico "computer non deterministico"
(che non esiste)

for cavaliere in range(0, 150):
  posizione[cavaliere]=scelta(0, 1, ... , 149)

for c in range(0, 150):
  for d in range(0, 150):
    if rivali[c,d]:
      if posizione[c]==(posizione[d]+1)%150:
        return false;
return true;

come funziona?

---

scelta e verifica

scelta delle posizioni:

for cavaliere in range(0, 149):
  posizione[cavaliere]=scelta(0, 1, ... , 149)

verifica:

for c in range(0, 149):
  for d in range(0, 149):
    …

---

risultato?

scelte arbitrarie delle posizioni

esiste una sequenza di scelte che porta a una soluzione
⇓
la soluzione esiste

come per gli automi:
esiste percorso per stato finale ⇒ stringa accettata

---

in pratica

i sistemi non deterministici non esistono nella realtà

si simulano con sistemi deterministici

vantaggio del non determinismo:

il nondeterminismo permette di codificare alcuni problemi complessi in modo semplice

li codifica, non li risolve

---

nondeterminismo: riassunto

• il non determinismo è un meccanismo teorico che permette di esprimere diversi problemi in modo facile,
  ma
• gli elaboratori reali sono deterministici, per cui i sistemi non deterministici vanno convertiti in deterministici in qualche modo.

---

espressioni regolari e automi

applicazione degli automi non deterministici

nel verificare una stringa, si possono presentare scelte

nota:

si sta parlando del modo che usano i programmi per vedere se una stringa collima con un'espressione regolare

es: come l'interprete Python esegue re.match() e re.finditer()

---

espressioni regolari con scelte

• espressione regolare r.*doc
  = r seguita da caratteri qualsiasi e poi doc
• stringa ridotto.doc

la stringa contiene due d: ridotto.doc

la prima d è parte di .*

la seconda è l'inizio di doc

ridotto.doc
↑-------↑↑↑
r  .*   doc

---

esecuzione

leggo i caratteri uno per volta:

• primo carattere r ⇒ r.*doc
• carattere i ⇒ r.*doc
• carattere d ⇒ r.*doc
  ma anche r.*doc
• carattere o: stessa cosa
• carattere t: solo ora so che siamo ancora in .*
• …

---

scelte

ridotto.doc e r.*doc

solo con rid, due possibilità:

• r=r
  id inizio di .*
  oppure
• r=r
  i=.*
  d=inizio di doc

nemmeno con la o riesco a scegliere

---

riconoscimento in Python

si sceglie una delle due possibilità
ma ci si ricorda dell'altra

se va male, si prova l'altra

algoritmo semplicistico

---

algoritmo astuto

si pone una scelta:

• d è parte di .*
• .*=i e d è la prima lettera di doc

si verifica se almeno una scelta porta al successo

in questo caso: la seconda scelta

---

espressione → automa

esistono scelte: automa non deterministico

in 1 con carattere d:

• si resta in 1
• si va in 2

stesso stato e carattere, ma due successori:
automa non deterministico

---

conversione automatica

conversione manuale

esiste metodo per farlo automaticamente

in questo caso produce:

archi ε = ci si può spostare senza caratteri

---

archi ε

quando si arriva in 1

prima che arrivi il prossimo carattere:

• si può restare in 1
• oppure andare subito in 2

è una scelta non deterministica

---

due scelte

non deterministiche:

• stato con due archi con lo stesso carattere
  si può seguire l'uno o l'altro
• stato con arco ε
  quando si arriva allo stato ci si può restare
  ma anche seguire subito l'arco

anche entrambe le scelte in uno stato
arco ε e archi uscenti con carattere

---

espressione → automa

modo automatico:

• si parte dalle sottoespressioni più semplici
• le si compone via via…
• fino a ottenere l'automa della formula intera

esempio…

---

esempio

((bd|c)a?)+

vogliamo l'automa

partiamo da quello che riconosce b da solo:

uno simile per a, per c e per d

poi: si compongono…

---

composizione: concatenazione

fatti: automi per b e per d

automa per bd:

volendo: eliminare arco ε
fondere i due stati in mezzo

---

composizione: alternativa

abbiamo l'automa per bd
e quello per c

automa per bd|c:

sono i due messi in parallelo
collegati con archi ε

---

composizione: opzionalità

l'automa di a è come quello di b:

a? è a opzionale:

arco ε da iniziale a finale

---

a questo punto

automi di bd|c e di a? noti

si concatenano e si ottiene quello di (bd|c)a?

ora: ripetizione non nulla di tutto
sarebbe il +

---

ripetizione non nulla

dato: automa di (bd|c)a?

automa di ((bd|c)a?)+:

questo è l'automa di tutta l'espressione

---

perché i due stati aggiuntivi?

perchè gli stati 0 e 11?

non si poteva iniziare con 1 e finire con 10?

per le ripetizioni non nulle servono i due stati aggiuntivi
altrimenti, l'automa di (a+b+)? accetterebbe aaa:

• esempio errato
• esempio corretto

---

ripetizione generale

A* è uguale a (A+)?

automi di + e ?: visti sopra

---

espressione → automa non deterministico

si procede sempre nello stesso modo:

• si parte dagli automi dei singoli caratteri
• si compongono nel modo visto

si ottiene un automa non deterministico

ora: convertirlo in deterministico

---

conversione da non deterministico a deterministico

vale in generale

in particolare, anche per:

espressione regolare → automa non deterministico → deterministico

---

differenza deterministico e non

deterministico

in ogni momento, un solo stato

non deterministico

in ogni momento, anche più stati possibili

esempio…

---

stati di un automa non deterministico

dopo d è in 1 e 2

più stati insieme nello stesso momento

anche dopo

---

insiemi di stati possibili

• si inizia in 0
• r porta in 1
• i mantiene in 1
• d porta in 1 o in 2
  stati {1,2}
• o porta 1→1 e 2→3
  stati {1,3}
• …

---

principio della conversione

deterministico: in ogni momento un solo stato

non deterministico: più stati in ogni momento
(dato che ci sono le scelte)

idea: insieme_stati → stato

---

insieme di stati: regola

l'automa non deterministico si trova in ogni momento in un insieme di stati

per ogni insieme di stati, si crea uno stato nell'automa deterministico

---

stati

più precisamente:

se successore può portare a un insieme di stati S, allora l'automa deterministico deve avere uno stato per S

frecce?

---

le frecce dell'automa deterministico

esempio:

• se lo stato è {1, 2}
• se in 1 il carattere a porta a 4;
• se in 2 il carattere a porta a 5, 8, 9;
• allora a porta da {1,2} a {4, 5, 8, 9}.

---

simulazione

ogni stato dell'automa deterministico simula un insieme di stati dell'automa non deterministico

le frecce sono di conseguenza

---

stati finali

esiste un percorso verso uno stato finale
⇓
stringa accettata

quindi

gli stati finali dell'automa deterministico sono quelli che corrispondono a insiemi che contengono almeno uno stato finale dell'automa non deterministico

basta un solo stato finale a rendere finale l'intero insieme

---

tornando all'esempio

in quali insiemi di stati può trovarsi?

---

insiemi di stati

da {0} solo in {1}

ma da 1 in 1 o in 2

quindi: stato {1,2}

ancora…

---

insiemi di stati

da {1,2} dove si va?

• con d: 1→1, 1→2, 2→niente
  insieme {1,2}
• con o: 1→1, 2→3
  insieme {1,3}
• altro: 1→1, 2→niente
  insieme {1}

serve lo stato {1,3}

---

da stato {1,3}

stessa cosa: c porta a {1,4}

d porta in {1,2}

tutti gli altri in 1

---

stato {1,4}

d porta in 1 e in 2

tutti gli altri in 1

---

automa complessivo

-d = qualsiasi carattere tranne d

---

automa in funzione

stringa ridotto.doc

• rido → {1,3}
• t → {1}
• to. → {1}
• doc → {1,4}

stringa accettata

---

automa in funzione, sul disegno

---

automi con output

quelli visti finora finivano con:

• stringa accettata
• stringa rifiutata

ma si possono mettere anche più uscite

---

schema realizzativo

per automi accetta/rifiuta:

uscita funzione dello stato

due reti ACC → due uscite

---

automi con uscite

sul disegno:

stato → stato/uscita

in ogni stato si mette la sua uscita

---

stato con uscita: esempio

riconosce abc e xyz

• abc → uscita p
• xyz → uscita s
• nessuna delle due: uscita n

non serve più mettere uno stato accettante

---

realizzazione dell'automa

come nel caso normale

anche l'uscita va codificata in binario:
es: n=00, p=01, s=10

tabella stato → uscita
(stato: tre bit; uscita: due bit)

si trasforma in due circuiti con il sistema solito

---

macchinetta del caffè con resto

uscite possibili:

• non abbastanza monete, niente caffè
• monete esatte, caffè
• monete in accesso, caffè + resto

---

macchinetta del caffè: automa

uscite: 0, caffè, resto

manca: ricomincia dall'inizio dopo l'erogazione

---

sintesi automa del caffè

ingressi: 5c=0, 10c=1

stati: 000, …, 100

uscite: 0=00, c=01, r=10

tabella stato successivo:

stato	ingresso	successivo
000	0	001
000	1	010
001	0	010
…

uscite: 011→01, 100→10, altri 00