4.3. Przekształcenia automatów skończonych
Konstrukcja automatu skończonego (niedeterministycznego) na podstawie wyrażenia
regularnego (algorytm Thompsona).
Wejście: wyrażenie regularne r nad alfabetem T
Wyjście : automat skończony akceptujący język L(r) (język opisany wyrażeniem
regularnym r)
Metoda: wyodrębnić z wyrażenia regularnego r elementy podstawowe. Dla elementów
podstawowych skonstruować odpowiadające im automaty, a następnie połączyć je według
poniższych zasad:
1. Dla µ zbudować A(µ)
µ
i 3
f
2. Dla a"T zbudować A(a)
a
i 3
f
3. Gdy A(s) i A(t) są automatami dla wyrażeń regularnych s i t , to
(a) dla wyrażenia s|t zbuduj A(s|t)
A(s)
µ
µ
if
µ
µ
A(t)
(b) dla wyrażenia st zbuduj A(st)
i f
A(s) A(t)
(c) dla wyrażenia s* zbuduj A(s*)
µ
µ µ
i A(s) f
µ
 (d) dla wyrażenia (s) wykorzystaj A(s) bez zmian
Przykład : konstrukcja automatu skończonego dla wyrażenia regularnego r = (a|b)*abb
Rozkład wyrażenia (a|b)*abb :
r11
r9 r10
r7 r8 b
r5 r6 b
r4 * a
( r3 )
r1 | r2
a b
r1 = a:
a
2 3
3
r2 = b:
b
3
4 5
r3 = a|b = r1|r2 :
a
2 3
µ µ
3
1 6
µ µ
b
4 5
r4 = (r3)
r5 = r4* :
µ
a
2 3
µ µ
µ µ
0 1 6 7
3
µ µ
b
4 5
µ
r6 = a ; r8 = b ; r9 = b - konstrukcje identyczne jak dla r1 i r2
rx = abb :
a b b
7' 8 9 10
3
r= r5rx = (a|b)*abb
Więc ostatecznie otrzymujemy:
µ
a
2 3
µ µ
a b b
µ
µ
3
10
0 1 6 7 8 9
µ
µ
b
4 5
(a|b)*abb
µ
Konstrukcja automatu deterministycznego na podstawie automatu niedeterministycznego
Dla każdego automatu skończonego istnieje deterministyczny automat skończony akceptujący
ten sam język.
Dla q"Q definiuje siÄ™ zbiór µ-CLOSURE(q) zawierajÄ…cy te stany r"Q, do których można
dojść z q przechodzÄ…c tylko przez µ-przejÅ›cia, przy czym również q " µ-CLOSURE(q).
Dla SÄ…"Q definiuje siÄ™ zbiór µ-CLOSURE(S) zawierajÄ…cy te stany r"Q, do których można
dojść ze stanów S przechodzÄ…c tylko przez µ-przejÅ›cia, przy czym również
S Ä…" µ-CLOSURE(S).
Dla Są"Q, dla a"T rozszerza się definicję funkcji przejścia:
´(S,a) = { r"Q | r"´(s,a), s"S }
Istota algorytmu:
WejÅ›cie: A=< T, Q, F, q0, ´ > - automat skoÅ„czony niedeterministyczny
WyjÅ›cie: A =< T, Q , F , r0, ´ > - automat skoÅ„czony deterministyczny (bez µ-przejść)
Metoda: Q‡"S r " Q
podzbiór zbioru stanów pojedynczy stan automatu
automatu niederminist. determnistycznego
r0 := µ-CLOSURE({q0}); r0 - nieoznaczony; /* r0  stan poczÄ…tkowy A */
/* r0  równocześnie podzbiór zbioru stanów Q automatu A */
Q := {r0};
while " X"Q and X  nieoznaczony do /* X = {q1,...,qn} Ä…" Q*/
begin
oznacz X;
for każde a"T do
begin
U := {q"Q | q"´(s,a) '" s"X } /* U = ´(X,a) */
Y := µ-CLOSURE(U) ;
if Y "Q then
begin
Q := Q *" {Y}; /* dołączenie Y do Q
Y  nieoznaczony jako nieoznaczonego */
end;
´ (X,a) := Y; /* ustalenie funkcji przejÅ›cia automatu A */
end;
end;
F := { r " Q | r )" F `" " } /* tutaj r traktowane jako (r‚"Q) podzbiór stanów automatu A */
Przykład:
µ
a
2 3
µ µ
a b b
µ
µ
3
10
0 1 6 7 8 9
µ
µ
b
4 5
(a|b)*abb
µ
r0=µ-CLOSURE({0}) = { 0,1,2,4,7 } = r0 ; Q ={ r0 }
_________________________________________________________
r0  oznaczamy
Ua = ´(r0,a) = {3,8}
r1 = µ-CLOSURE({3,8}) = { 1,2,3,4,6,7,8 }= r1 ; ´ (r0,a) = r1
Ub = ´(r0,b) = {5}
r2 = µ-CLOSURE({5}) = { 1,2,4,5,6,7 }= r2 ; ´ (r0,b) = r2
Q = { r0 , r1 , r2 } /* stan podkreślony jest oznaczony */
_________________________________________________________
r1  oznaczamy
Ua = ´(r1,a) = {3,8}
µ-CLOSURE({3,8}) = { 1,2,3,4,6,7,8 }= r1 ; ´ (r1,a) = r1
Ub = ´(r1,b) = {5,9}
µ-CLOSURE({5,9}) = { 1,2,4,5,6,7,9 }= r3 ; ´ (r1,b) = r3
Q = { r0 , r1 , r2 , r3 }
_________________________________________________________
r2  oznaczamy
Ua = ´(r2,a) = {3,8}
µ-CLOSURE({3,8}) = r1 ; ´ (r2,a) = r1
Ub = ´(r2,b) = {5}
µ-CLOSURE({5}) = r2 ; ´ (r2,b) = r2
Q = { r0 , r1 , r2 , r3 }
_________________________________________________________
r3  oznaczamy
Ua = ´(r3,a) = {3,8}
µ-CLOSURE({3,8}) = r1 ; ´ (r3,a) = r1
Ub = ´(r3,b) = {5,10}
µ-CLOSURE({5,10}) = { 1,2,4,5,6,7,10 } = r4 ; ´ (r3,b) = r4
Q = { r0 , r1 , r2 , r3 , r4 }
_________________________________________________________
r4  oznaczamy
Ua = ´(r4,a) = {3,8}
µ-CLOSURE({3,8}) = r1 ; ´ (r4,a) = r1
Ub = ´(r4,b) = {5}
µ-CLOSURE({5,10}) = r2 ; ´ (r3,b) = r2
Q = { r0 , r1 , r2 , r3 , r4 }
_________________________________________________________
Ostatecznie:
´ :
b
Stan a b
r0 r1 r2
r2
b
r1 r1 r3
b
r2 r1 r2
a
r3 r1 r4
r4 r1 r2
a b b
start
r4
r0 r1 r3
F ={r4}
a
a
a
(a|b)*abb
Uzupełnienie automatu skończonego
WejÅ›cie: A = < T, Q, F, q0, ´ > - automat skoÅ„czony
WyjÅ›cie: A = < T, Q , F, q0, ´ > - automat skoÅ„czony zupeÅ‚ny
Q := Q *" { err }
for q"Q do
for a"T do
if ´(s,a) = " then ´ (q,a) : ={ err }
else ´ (q,a) := ´(q,a);
for a"T do
´ ( err,a ) := { err }
Przykład:
a
a b b
start
3
0 12
b
a a
a
err
b a
Stan pułapki  err nie jest stanem końcowym
Redukcja automatu skończonego
A = < T, Q, F, q0, ´ > - deterministyczny, zupeÅ‚ny automat skoÅ„czony
x"T* - słowo nad alfabetem T
q1,q2 "Q
(i) x"T* rozróżnia stany q1 i q2 Ô!
*
(1) (q1,x) (q3, µ)
A
*
(2) (q2,x) (q4, µ)
A
(3) (q3 " F '" q4 " F ) (" (q3 " F '" q4 " F )
(ii) q1 i q2 sÄ… k nierozróżnialne, co oznaczamy q1 a"k q2 Ô! Ź("x " T*) takie że:
(1) x rozróżnia q1 i q2
(2) |x| d" k
(iii) q1 i q2 sÄ… nierozróżnialne, co oznaczamy q1 a" q2 Ô! ("k e" 0) (q1 a"k q2)
+
(iv) q " Q  {q0} jest nieosiÄ…galny Ô! Ź("x " T*) ((q0,x) (q,y) '" y"T*)
A
Automat skoÅ„czony ( deterministyczny, zupeÅ‚ny ) nazywamy zredukowanym Ô!
(1) Ź(" q"Q) (q jest nieosiągalny)
(2) ("q1,q2"Q) (q1 i q2 nie są nierozróżnialne)
Usuwanie stanów nieosiągalnych
A = < T, Q, F, q0, ´ > - deterministyczny
Niech R bÄ™dzie relacjÄ… (RÄ…"Q×Q) zdefiniowanÄ… nastÄ™pujÄ…co:
q1Rq2 Ô! ("a"T) ( ´(q1,a) = q2 )
Trzeba znalez
ć automat A = < T, Q , F , q0, ´ > bez stanów nieosiÄ…galnych, to znaczy trzeba
wyznaczyć
Q = { q"Q | q0R*q }
Zakładamy, że elementy Q są nieoznaczone.
L := {q0};
while L `" " do
begin
b := pierwszy element z L;
oznacz b w Q;
L := L  {b};
L := L *" {c"Q | bRc '" c  nieoznaczone w Q };
end;
stop; /* elementy nieoznaczone w Q sÄ… nieosiÄ…galne */
Przykład:
0
1 0
B C F
0
0
start
1
1 1 1
A
1
0
0
1
D E G
0
L = { A }; A ; { A, B, C, D, E, F, G }; L = "
L = { B, D }; B ; { A, B, C, D, E, F, G }; L = { D }
L = { D, C }; C ; { A, B, C, D, E, F, G }; L = { C }
L = { C, E}; D ; { A, B, C, D, E, F, G }; L = { E }
L = { E }; E ; { A, B, C, D, E, F, G }; L = "
nieoznaczone = nieosiÄ…galne
0
1
B C
0
0
start
1
A 1
1
0
1
D E
0
A
ączenie stanów nierozróżnialnych
A = < T, Q, F, q0, ´ > - automat skoÅ„czony, bez stanów nieosiÄ…galnych, deterministyczny,
zupełny.
Tw1. Niech n = #Q
( a" ) Ä…" ( a"n-2 ) Ä…" ( a"n-3 ) Ä…" ... Ä…" ( a"1 ) Ä…" ( a"0 )
przy czym:
q1 a"0 q2 Ô! (q1"F '" q2"F) (" (q1 "F '" q2 "F)
q1 a"k q2 Ô! q1 a"k-1 q2 '" ("a"T ) (´(q1,a) a"k-1 ´(q2,a))
Tw2. Relacja nierozróżnialności (a") jest zwrotna, symetryczna, przechodnia, jest więc
relacją równoważności.
Algorytm łączenia stanów nierozróżnialnych polega na wyznaczeniu relacji
nierozróżnialnoÅ›ci (a") Ä…" Q×Q, a nastÄ™pnie przypisaniu każdej klasie równoważnoÅ›ci relacji
(a") stanu tworzonego automatu zredukowanego. RelacjÄ™ (a") wyznaczamy zgodnie z tw1.
poczynając od (a"0) i dokonując kolejnych podziałów Q na klasy równoważności.
Algorytm łączenia stanów nierozróżnialnych:
WejÅ›cie : A = < T, Q, F, q0, ´ > - deterministyczny, zupeÅ‚ny, bez stanów nieosiÄ…galnych
WyjÅ›cie : A = < T, Q , F , q0 , ´ > - automat posiadajÄ…cy najmniejszÄ… liczbÄ™ stanów spoÅ›ród
wszystkich automatów deterministycznych i zupełnych akceptujących język L(A)
(1) Podzielić Q na klasy równoważności dla relacji ( a"0) , ( a"1) , ... . Postępować tak długo, aż
podziały : dla ( a"k) i dla ( a"k+1) będą identyczne. Jako podział względem relacji (a")
przyjąć ten dla ( a"k)
(2) Oznaczamy [q]a" klasę równoważności relacji (a") w Q, do której należy q"Q
Q := { [p]a" : p " Q }
(3) ´ ( [p]a" , a ) := [q]a" Ô! ´(p,a) = q
(4) q0 := [q0]a"
(5) F := { [q]a" | q"F }
Przykład:
b
(a|b)*abb
2
b
b
a
a b b
start
4
0 13
a
a
a
Relacja Klasa równoważności Przejścia
{4} { 0,1,2,3 }
´(0,a)=1 ´(0,b)=2
´(1,a)=1 ´(1,b)=3 2a"03
a"0
´(2,a)=1 ´(2,b)=2
´(3,a)=1 ´(3,b)=4
{4} { 0,1,2, } {3}
´(0,b)=2
a"1
´(2,b)=2 2a"03
´(1,b)=3
{4} { 0,2, } {1} {3}
´(0,b)=2
a"2
´(2,b)=2
{4} { 0,2 } {1} {3}
a"3
końcowy początkowy
Wynik końcowy:
a
b
a b b
start
4
0,2 13
a
a
b