Przekształcenia automatów
skończonych
Teoria automatów i języków
formalnych
Dr in\
. Janusz Majewski
Katedra Informatyki
Konstrukcja automatu skończonego na podstawie
wyra\
enia regularnego (algorytm Thompsona)
Wejście: wyra\
enie regularne r nad alfabetem Ł
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:
" Dla " zbudować A("
" ")
" "
" "
" Dla � zbudować A(�
� �)
� �
� �
�
i 3
f
Konstrukcja automatu skończonego na podstawie
wyra\
enia regularnego (algorytm Thompsona)
" Dla a"Ł zbudować A(a)
a
i 3
f
" Gdy A(s) i A(t) są automatami dla wyra\
eń regularnych s i t , to dla
wyra\
enia s|t zbudować A(s|t)
A(s)
�
�
i f
�
�
A(t)
Konstrukcja automatu skończonego na podstawie
wyra\
enia regularnego (algorytm Thompsona)
" Gdy A(s) i A(t) są automatami dla wyra\
eń regularnych s i t , to dla
wyra\
enia st zbudować A(st)
i f
A(s) A(t)
" Gdy A(s) jest automatami dla wyra\
enia regularnego s, to dla
wyra\
enia s* zbudować A(s*)
�
� �
i A(s) f
�
Przykład: konstrukcja automatu skończonego dla
wyra\
enia regularnego r = (a|b)*abb
r11
Rozkład wyra\
enia (a|b)*abb :
r9 r10
r7 r8 b
r5 r6 b
r4 * a
( r3 )
r1 | r2
a b
Przykład: konstrukcja automatu skończonego dla
wyra\
enia regularnego r = (a|b)*abb
r1 = a r1 = b
a
b
2 3
3
3
4 5
r3 = a|b = r1|r2
a
2 3
� �
3
1 6
� �
b
4 5
Przykład: konstrukcja automatu skończonego dla
wyra\
enia regularnego r = (a|b)*abb
r4 = (r3)
r5 = r4*
�
a
2 3
� �
� �
0 1 6 7
3
� �
b
4 5
�
Przykład: konstrukcja automatu skończonego dla
wyra\
enia regularnego r = (a|b)*abb
r6 = a ; r8 = b ; r10 = b - konstrukcje identyczne jak dla r1 i r2
rx = abb
a b b
7' 8 9 10
3
r = r5rx = (a|b)*abb
Ostatecznie otrzymujemy:
Przykład: konstrukcja automatu skończonego dla
wyra\
enia regularnego r = (a|b)*abb
�
a
2 3
� �
a b b
�
�
10
3
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"Ł rozszerza się definicję funkcji przejścia:
�(S,a) = { r"Q | r"�(s,a), s"S }
Konstrukcja automatu deterministycznego
na podstawie automatu niedeterministycznego
Wejście: A=< Ł, Q, F, q0, � > - automat skończony niedeterministyczny
Wyjście: A =< Ł, Q , F , r0, � > - automat skończony deterministyczny (bez �-przejść)
Metoda: Q �" S a r " Q /* podzbiór zbioru stanów a pojedynczy stan */
r0 := �-CLOSURE({q0}); r0 - nieoznaczony; /* r0  stan początkowy A i równocześnie
podzbiór zbioru stanów Q automatu A */
Q := {r0};
while " X"Q and X  nieoznaczony do /* X = {q1,...,qk} ą" Q*/
begin
oznacz X;
for ka\
de a"Ł do
begin
U := {q"Q | q"�(s,a) '" s"X } /* U = �(X,a) */
Y := �-CLOSURE(U) ;
if Y "Q then
begin
Q := Q *" {Y}; Y  nieoznaczony; /* dołączenie Y do Q 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 (1)
�
a
2 3
� �
a b b
�
�
3
0 1 6 7 8 9 10
�
�
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 */
Przykład (2)
�
a
2 3
� �
a b b
�
�
3
0 1 6 7 8 9 10
�
�
b
4 5
r1  oznaczamy
(a|b)*abb
�
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 }
Przykład (3)
�
a
2 3
� �
a b b
�
�
3
0 1 6 7 8 9 10
�
�
b
4 5
r3  oznaczamy
(a|b)*abb
�
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 }
Przykład (4)
�
a
2 3
� �
a b b
�
�
3
0 1 6 7 8 9 10
�
b �
4 5
(a|b)*abb
�
b
Ostatecznie:
r2
b
Stan a b
b
r0 r1 r2
a
r1 r1 r3
r2 r1 r2 start
a b b
r4
r0 r1 r3
r3 r1 r4
a
r4 r1 r2
a
a
F ={r4}
(a|b)*abb
Uzupełnienie automatu skończonego
Wejście: A = < Ł, Q, F, q0, � > - automat skończony
Wyjście: A = < Ł, Q , F, q0, � > - automat skończony
zupełny
Q := Q *" { err }
for q"Q do
for a"Ł do
if �(q,a) = " then � (q,a) := { err }
else � (q,a) := �(q,a);
for a"Ł do
� (err,a) := { err }
Przykład
a
a b b
start
3
0 1 2
b
a a
a
b
err
Stan pułapki  err nie jest stanem
końcowym akceptującym
b a
Redukcja automatu skończonego
A = < Ł, Q, F, q0, � > - deterministyczny, zupełny automat skończony
x"Ł* - słowo nad alfabetem Ł
q1, q2, q3, q4 " Q  stany automatu A
" x"Ł* 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 )
" q1 i q2 są k nierozró\
nialne, co oznaczamy q1 a"k q2 �! Ź("x " Ł*) takie \
e:
x rozró\
nia q1 i q2 oraz |x| d" k
" q1 i q2 są nierozró\
nialne, co oznaczamy q1 a" q2 �! ("k e" 0) (q1 a"k q2)
+
" q " Q  {q0} jest nieosiągalny �! Ź("x " Ł*) ((q0,x) (q,y) '" y"Ł*)
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 = < Ł, Q, F, q0, � > - deterministyczny automat skończony
Niech R będzie relacją (R ą" Q � Q) zdefiniowaną następująco:
q1 R q2 �! ( "a"Ł ) ( �(q1,a) = q2 )
"
"
"
Trzeba znalez
ć automat A = < Ł, Q , F , q0, � > bez stanów nieosiągalnych, to znaczy trzeba
wyznaczyć
Q = { q"Q | q0 R* 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 | b R c '" c  nieoznaczone w Q };
end;
stop; /* elementy nieoznaczone w Q są nieosiągalne */
Przykład usuwania stanów nieosiągalnych (1)
0
1 0
B C F
0
0
start
1
1 1 1
A
1
0
0
1
D E G
0
Przykład usuwania stanów nieosiągalnych (2)
L = { A }; A ; Q = { A, B, C, D, E, F, G }; L = "
L = { B, D }; B ; Q = { A, B, C, D, E, F, G }; L = { D }
L = { D, C }; D ; Q = { A, B, C, D, E, F, G }; L = { C }
L = { C, E}; C ; Q = { A, B, C, D, E, F, G }; L = { E }
L = { E }; E ; Q = { A, B, C, D, E, F, G }; L = "
nieoznaczone = nieosiągalne
0 0
PRZED:
PO:
1 0 1
B C F B C
0 0
0 0
start start
1
1
A 1 1 1 A 1
1
1
0
0
0
1
1
D E
D E G
0
0
A
ączenie stanów nierozró\
nialnych
A = < Ł, Q, F, q0, � > - automat skończony, bez stanów
nieosiągalnych, deterministyczny, zupełny.
Twierdzenie 1. Niech n = #Q
( a" ) ą" ( a"n-2 ) ą" ( a"n-3 ) ą" ... ą" ( a"1 ) ą" ( a"0 )
a" ą" a" ą" a" ą" ą" a" ą" a"
a" ą" a" ą" a" ą" ą" a" ą" a"
a" ą" a" ą" a" ą" ą" a" ą" a"
przy czym: (a") ą" Q� ą" �Q
ą" �Q; (a"k) ą" Q�
ą" � ą" �
ą" � ą" �
q1 a"0 q2 �! (q1"F '" q2"F) (" (q1 "F '" q2 "F)
a" �! " '" " (" " '" "
a" �! " '" " (" " '" "
a" �! " '" " (" " '" "
q1 a"k q2 �! q1 a"k-1 q2 '" (" ) (�(q1,a) a"k-1 �(q2,a))
a" �! a" '" " a"
a" �! a" '" "a"Ł a"
a" �! a" '" " a"
Twierdzenie 2. Relacja nierozró\
nialności (a") ą" Q� jest zwrotna,
ą" �Q
ą" �
ą" �
symetryczna i 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 = < Ł, Q, F, q0, � > - deterministyczny, zupełny, bez
stanów nieosiągalnych
Wyjście: A = < Ł, 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
3) Q := { [p]a" | p " Q }
4) � ( [p]a" , a ) := [q]a" �! �(p,a) = q
5) q0 := [q0]a"
6) F := { [q]a" | q"F }
Przykład
Przed:
b
Relacja Klasy równowa\
ności Przejścia
(a|b)*abb
2
b
a"0 {4} {0, 1, 2, 3} �(0,a)=1 �(0,b)=2
a"
a"
a"
b
�(1,a)=1 �(1,b)=3 2 a"0 3
a"
a"
a"
a
�(2,a)=1 �(2,b)=2
a b b
start
4
�(3,a)=1 �(3,b)=4 0 1 3
a
a"1 {4} {0, 1, 2} {3} �(0,b)=2 a
a"
a"
a"
a
�(2,b)=2 2 a"1 2
a"
a"
a"
�(1,b)=3
Po:
a"2 {4} {0, 2} {1} {3} �(0,b)=2
a"
a"
a"
�(2,b)=2 2 a"2 2
a"
a"
a"
b a
a"3 {4} {0,2} {1} {3}
a"
a"
a"
akceptujący początkowy
a b b
start
4
0,2 1 3
a
a
b