Trasduttori a Stati Finiti

Trasduttori a Stati Finiti
Un Trasduttore a Stati Finiti Deterministici è definito dalla 7-pla
< ∑, K, δ, Z, S, O, η >
∑ - Alfabeto di Ingresso (Alfabeto terminale)
K- Insieme degli stati
δ -funzione (parziale) di transizione
δ :Kx ∑ →K
Z - Insieme (non vuoto) di Stati finali
Z⊆K
S - Stato iniziale
S∈K
O- Alfabeto di uscita
η- funzione di uscita
η: K x ∑ → O*
Esempio di trasduttore
Ex: Calcolo del complemento a 2 di un numero binario
1.
Si legge la stringa in ingresso dal bit meno significativo a quello
più significativo
2.
Si ricopiano i bit in uscita fino al primo 1 (compreso)
3.
Da questo punto in poi si ricopia in uscita la negazione di ogni cifra
0/0
→ q0
1/1
0/1
q1
1/0
1110100
0001011 +
1
-----------0001100
Corrispondenza tra trasduttori e macchine di Mealy
•
•
•
•
•
•
L’ultimo esempio può essere visto anche come una rete sequenziale di
Mealy (le uscite sono associate agli archi)
Nella definizione di trasduttore abbiamo in realtà definito la funzione
di uscita come una funzione che dà una stringa, non un solo simbolo
Questo permette al trasduttore di tradurre una parola in una parola più
lunga o più corta (la stringa in uscita può essere anche vuota)
Limitandoci ad un solo simbolo, in effetti la definizione di trasduttore
data corrisponde a quella di macchina di Mealy
Associando invece un’uscita agli stati di un’automa possiamo ottenere
una macchina di Moore.
Ad esempio, un qualsiasi automa in cui si associa l’uscita uno agli stati
finali e zero agli altri stati è una macchina di Moore che dà in uscita un
valore uno appena la stringa letta in ingresso risulta essere una stringa
del linguaggio accettato dall’automa.
0
S
•
•
1
1
1
0
1
0
•
0
Automa che riconosce il
linguaggio delle strighe di parità
dispari
Se associo l’uscita 1 allo stato
finale e l’usicta zero agli altri stati,
ottengo una macchina di Moore
che è capace di riconoscere se la
stringa seriale in ingresso ha un
numero dispari di uno.
Può sostituire il classico parity tree
di xor in un trattamento seriale di
stringhe.
In generale, estendendo un meccanismo riconoscitore di un linguaggi con
delle funzioni di uscita (legate agli stati o alle transizioni) ottengo un
formalismo capace di descrivere algoritmi.
Automi a stati finiti non deterministici
Un Automa a Stati Finiti non Deterministico è definito dalla 5-pla
< ∑, K, δ, Z, S>
∑ - Alfabeto di Ingresso (Alfabeto terminale)
K- Insieme degli stati
δ -funzione (parziale) di transizione
δ :Kx ∑ →2K
Z - Insieme (non vuoto) di Stati finali
Z⊆K
S - Stato iniziale
S∈K
Alternativamente, si può definire δ come una relazione di transizione δ ⊆ K x ∑ x K:
δ(q, a) = {q’, q”, q’”} nella prima definizione, equivale a
{(q, a ,q’), (q, a,q”), (q, a, q’”) ⊆ δ nella seconda definizione.
Automi a stati finiti non deterministici
Dal punto di vista grammaticale si ha non determinismo quando
esistono produzioni con la stessa parte sinistra che iniziano col
medesimo simbolo terminale
A→tB
A→tC
a
Ex:
S→aA|bB
A→aA|a
B→bB|b
S
a
a
A
b
a
b
S
A
A
B
A ,#
B
#
B ,#
b
B
b
S a a a a |⎯ A a a a |⎯ A# a a |⎯ A# a |⎯ A#
SI
S a a b a |⎯ A a b a |⎯ A# b a
NO
#
Albero di computazione
non accettante
non accettante
#a a
(S, a a a a)
A
Aaaa
Aa
Aaa
#
accettante
#a
non accettante
Un automa deterministico a fronte di una conoscenza di quale transizione
seguire sarebbe capace di effettuare il percorso accettante
Caso della grammatica regolare a sinistra
Dal punto di vista grammaticale si ha non determinismo quando
esistono produzioni con la stessa parte destra
A→Ba|Ea|a|b
E→Ba
B→Rb|b
R→ A b
a
#
A
b
b
a
A
a
b
R
B
A,E
#
A
A,B
E
A
R
B
b
E
R
b
a
a
B
#baabbaa |⎯ ABaabbaa |⎯ AEabbaa |⎯ Abbaa |⎯ Rbaa |⎯ Baa |⎯ AEa |⎯ A
Trasformazione di un NDFA in un DFA
a,b
a,b
S
S
A
A,B A,B
A
A
a
b
c
A
B
C
D
D
D
C
a
a
B
a
b
a
S
AB
C
c
D
c
b
b
a
a
AC
A
c
c
b
b
E’ facile convincersi che i due automi riconoscono lo stesso linguaggio.
Quello a destra è deterministico. Nell’automa a sinistra dando una stringa
w si può in genere arrivare, con computazioni distinte, ad un insieme di stati
W e non solo ad uno stato signolo; nell’automa di destra la stessa stringa w
fa arrivare in uno stato, etichettato con l’insieme W.
D
Algoritmo di trasformazione di un NDFA in un DFA
1.
Q’← {S}
/*Q’ conterrà gli stati del DFA risultante*/
/*gli stati di Q’ corrisponderanno a insiemi di stati dell’ NDFA dato*/
2. Repeat
2.1 if ∃ X ∈ Q’ e un simbolo s non ancora esaminato che parte da X
etichettato con s then
2.1.1 Y= ∪qi∈ X δ ( qi , s)
2.1.2 if Y ∉ Q’ then Q’ = Q’ ∪ { Y}
2.1.3 crea un arco da X a Y con etichetta s
else Flag ← True
until Flag
3. L’ insieme degli stati finali del DFA Z’= {X ∈ Q’ | X contiene qi ∈ Z }
/*uno stato di Q’ rappresenta l’insieme degli stati a cui si arriva, nelll’automa
ND di partenza, con una data stringa w: se in questo insime c’e’ almeno uno
stato finale, la stringa è riconosciuta*/
a
S
A
B
C
D
a A,B A,B
a
AB
b
A
A
C
S
a
c
c
D
D
a
b
c
b
b
AC
D
S AB A AC D
Q’ =
A
b
Altre fonti di non determinismo le ε - Regole
Un automa non deterministico con ε - regole è caratterizzato dalla funzione di
transizione:
δ : K x (∑ ∪ ε ) → 2K
In luogo di
δ : K x ∑ → 2K
Dal punto di vista del linguaggio ciò equivale a considerare produzioni del tipo
U → R con
U,R ∈ VN
Cioè si passa dallo stato U allo stato R senza scandire alcun simbolo
Le ε - regole rappresentano uno strumento per costruire automi complessi a partire da
automi semplici.
Esempio di composizione
a,b
a,b
q01
b
q11
b
b
L2 = { b, ab}* {a, ε}
a
q02
b
L1 = { a, b}* b b { a, b}*
q21
q12
a,b
a,b
ε
L1 ∪ L2
b
q01
q0
q11
b
b
a
ε
q02
q12
b
a,b
a,b
q01
b
q11
b
b
ε
q21
a
q02
b
q12
L1 . L 2
q21
ε - chiusura
La ε -chiusura di uno stato qi consiste nell’insieme degli stati raggiungibili dallo
stato qi con ε -transizioni, Viene definita ricorsivamente dalla seguente
procedura:
1.
qi ∈ ε -chiusura (qi )
2.
Sia qj un elemento della ε -chiusura (qi )
se qK ∈ δ (ε, qj ) allora qK ∈ ε -chiusura (qi )
3.
qj è nella ε -chiusura (qi ) solo se può essere ottenuta da
qi da un numero finito di applicazioni di operazioni in 2.
ε
q1
ε
q2
q0
a
q3
ε -chiusura (q0 ) = {q0 , q1, q2}
ε -chiusura (q1 ) = {q1 }
ε-chiusura (q2 )= {q2}
ε -chiusura (q3 )= {q3}