03_NAS_NASe.pdf

(282 KB) Pobierz
NIEDETERMINISTYCZNY AUTOMAT SKOİCZONY -
NAS
Def. Niedeterministycznym automatem skoıczonym (NAS) nazywamy
ukþad
(((( ))))
M
====
,
Q
,
Q
,
,
F
0
gdzie
Î jest skoıczonym alfabetem (
)
Î Q jest skoıczonym zbiorem (stanw) (
)
Q
Î
Q
Q
(zbir stanw poczĢtkowych)
0
Î
:
Q
P
(((())))
Q
(funkcja przejĻcia, program),
××××
a
QP
( (( () )) ){ {{ { } }} }
= == = :
X
X
Q
Î zbir potħgowy zbioru Q
Î
F (zbir stanw koıcowych)
Q
~
(((()))) (((())))
Def. Funkcjħ rozszerzamy do funkcji
:
P
Q
P
Q
:
××××
a
~
( (( () )) ) ( (( () )) )
U X
X
,
a
==== ,
q
a
.
q
ó
Nastħpnie funkcjħ ~ rozszerzamy do funkcji
(((()))) (((())))
:
P
Q
××××
P
Q
:
a
ó
(((())))
(((()))) (((())))
X
,
====
X
~
(((())))
ó
ó
X
,
xa
====
X
,
x
,
a
(((())))
ó = zbir stanw, do ktrych moŇe dojĻę automat z funkcjĢ
przejĻcia po wczytaniu þaıcucha x, jeŇeli zaczyna od jakiegoĻ stanu
ze zbioru X.
X ,
x
( (( ( ) )) )
Niech
==== bħdzie NAS. Jħzyk akceptowany
przez automat M: (((()))) (((())))
M
,
Q
,
Q
,
,
F
0
{ {{ { } }} }
ó
====
L
M
x
:
Q
,
x
F
0
KonfiguracjĢ automatu nazywamy uporzĢdkowanĢ parħ
,
[[[[ ]]]]
q,
w
gdzie
q - bieŇĢcy stan maszyny,
Q
- þaıcuch pozostaþy do wczytania.
w
Na konfiguracjach okreĻlamy funkcjħ:
nd
M
|
−− Q
:
Q
×
×
a
sþuŇĢcĢ do Ļledzenia obliczeı automatu nastħpujĢco:
[
[ ]
]
nd
M
q
, −− ,
aw
q
,
w
,
,
q i
,
q
Q
w
a
i
j
gdzie
q
.
()
q
,
a
j
i
Konfiguracja poczĢtkowa:
, gdzie
q ,
Q
[[[[ ]]]]
q,
w
w
Konfiguracja koıcowa:
[ ]
q
,
lub [
q,
av
]
, gdzie
()
q,
a
=
Konfiguracja akceptujĢca:
[ ]
q
,
, gdzie
q
F
Obliczeniem dla þaıcucha
==== jest ciĢg konfiguracji:
w
a
a
a
K
1
2
n
[
]
nd
M
[
]
nd
M
nd
M
[
]
q
,
a
a
a
|
q
,
a
a
|
|
q
q
,
K
−−
K
−−
K
−−
=
0
1
2
n
i
1
2
n
in
,
nd
M
[
]
[ ]
q
,
w
|
−− .
q
,
0
JeŇeli
q , to obliczenie jest akceptujĢce, tzn.
automat M þaıcuch w.
q i
Q
F
0
0
() {
q i istnieje obliczenie
akceptujĢce rozpoczynajĢce siħ w
konfiguracji
L
M
=x
:
istnieje
Q
0
0
[ ]
q,
x
}
Automaty M i N sĢ rwnowaŇne wtedy i tylko wtedy,
gdy akceptujĢ te same jħzyki, tzn.
L = .
()()
L
N
s
s
NAS:
= == = .
(((( ))))
N
,
Q
,
Q
,
,
F
0
(((( ))))
( (( () )) )
~
~
DAS:
==== ,
M
,
P
Q
,
Q
,
,
F
0
gdzie
~
{{{{ }}}}
F
==== F
X
Q
:
X
~
( (( () )) ) ( (( () )) )
~
( (( () )) ) ( (( () )) )
,
U X
:
P
Q
P
Q
X
,
a
==== ,
q
a
××××
a
q
W praktyce jako zbir stanw automatu M wybieramy zbir
()
~
{
Q = stan X jest osiĢgalny w M ze stanu
P
Q
:
Q
}
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
NAS
NAS = NAS z funkcjĢ przejĻcia
:
Q
×
{}( )()
P
Q
.
a
Zatem, niektre instrukcje dopuszczajĢ zmianħ stanu bez
wczytania symbolu z þaıcucha wejĻciowego.
Dla
X jako zbir tych
wszystkich stanw, do ktrych moŇna dojĻę od stanw ze
zbioru X pewnĢ (moŇe zerowĢ) liczbĢ pustych przejĻę.
X okreĻlamy zbir
Q
Q
Definicja indukcyjna:
X
=
X
0
()
X
+ U n
=
X
,
q
n
1
n
q
X
Musi istnieę takie n, Ňe
X
X
.
= n
n
+
Przyjmujemy
X = .
X
n
1012112996.001.png 1012112996.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin