04_min_DAS.pdf

(166 KB) Pobierz
MINIMALIZACJA AUTOMATìW SKOİCZONYCH
Niech
M
==== bħdzie DAS oraz
,
Q
,
q
,
,
F
q
1 ,
Q
,
(((( ))))
0
2
q .
q
1
2
*
Def. Sþowo
x
rozrŇnia stany q , q , jeĻli
[
]
[
]
[
]
[
]
q
,
x
|
−− i
q
,
q
,
x
|
−−
q
,
1
M
3
2
M
4
oraz
q 4
(jeden ze stanw jest stanem koıcowym, a drugi nie)
,
4 lub
3 ,
q
F
q
Q
\
F
q
Q
\
F
F
3
k ), jeĻli nie
Def. Stany q i q sĢ k-nierozrŇnialne (
q
q
1
2
istnieje sþowo x:
x < , rozrŇniajĢce stany q i q . W
przeciwnym przypadku sĢ k-rozrŇnialne.
k
OkreĻlenie indukcyjne:
0
q oba stany q i q jednoczeĻnie naleŇĢ lub nie
naleŇĢ do F,
q
1
2
k
k − oraz
1
q
q
q
q
1
2
1
2
k
1
−
() ()
q
,
a
q
,
a
dla kaŇdego
a .
1
2
Def. Stany q i q sĢ nierozrŇnialne (
q ), jeĻli nie sĢ
q
1
2
k-rozrŇnialne dla kaŇdego 0
> k .
Def. Stan
q j nazywamy nieosiĢgalnym w M ze stanu q ,
Q
*
jeŇeli nie istnieje sþowo
x
, takie Ňe
[ ]
[
]
q
,
w
|
−−
q
,
i
M
j
1012115813.001.png 1012115813.002.png
Def. Automat DAS nazywamy zredukowanym , jeĻli zbir
stanw Q tego automatu nie zawiera stanw nieosiĢgalnych ze
stanu q i stanw nierozrŇnialnych.
Lemat. Niech
M
==== bħdzie DAS, przy czym
( (( ( ) )) )
,
Q
,
q
,
,
F
0
Q = . Stany q i q sĢ nierozrŇnialne (
n
q ), wtedy i
q
1
2
k − ).
2
tylko wtedy, gdy sĢ ( k-2)-nierozrŇnialne (
q
q
1
2
Wniosek. JeŇeli dwa stany moŇna rozrŇnię, to moŇna je
rozrŇnię przy pomocy sþowa, ktrego dþugoĻę jest mniejsza
niŇ licznoĻę zbioru stanw Q.
1012115813.003.png 1012115813.004.png
ALGORYTM MINIMALIZACJI DAS
WejĻcie: DAS
M
====
(((( ))))
,
Q
,
q
,
,
F
0
WyjĻcie: Zredukowany automat M rwnowaŇny M.
Algorytm:
1. UsunĢę ze zbioru Q wszystkie stany nieosiĢgalne z q .
2. Wyznaczyę klasy rwnowaŇnoĻci relacji
0
, 1 , 2
, ...
tak dþugo aŇ dla pewnego k zbiory klas rwnowaŇnoĻci
bħdĢ rwne (
Q
/ 1
Q
/
).
=
k
k
+
Wtedy przyjmujemy, Ňe relacja jest rwna relacji k .
3. Budujemy automat
M
=
( )
,
Q
,
q
,
,
F
, w ktrym
0
Q
= /
Q
- zbir klas rwnowaŇnoĻci relacji
,
() [ ]
[ ]
q =
p
, jeŇeli
()
q =
,
p
q=
[ ]
q
0
0
qF
= :
[ ] { }
q
F

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin