Rok / Year: 2015
Svazek / Volume: 17
Číslo / Number: 1
Prázdné slovo, stav a determinizace konečného automatu Empty Word, State and Determinization of Finite Automaton Josef Bokr
[email protected] Západočeská univerzita v Plzni, Fakulta aplikovaných věd ZČU v Plzni
Abstrakt: Článek se zabývá působením prázdného slova, definováním stavu systému a omezením i aplikací determinizace nedeterministických systémů.
Abstract: This paper is concerned with an operation of the empty word, defining a state of a system, restricting and an application of determinization of non-deterministic systems.
VOL.17, NO.1, FEBRUARY 2015
Prázdné slovo, stav a determinizace konečného automatu Josef Bokr Západočeská univerzita v Plzni, Fakulta aplikovaných věd ZČU v Plzni e-adresa: bokr @ kiv.zcu.cz
Anotace: Článek se zabývá působením prázdného slova, definováním stavu systému a omezením i aplikací determinizace nedeterministických systémů.
ηϑ = η i 0 η i 2 ...η i ,m −1 ϑ jmϑ j ,m +1 ... ϑ j , m + n −1 , kde ϑ jm = ϑ j 0 ϑ j , m +1 = ϑ j1 ,..., ϑ j , m + n −1 = ϑ j ,n −1 .
Slovo
α = a i 0 a i1 ... a im −1 lze tak také chápat jako zřetězení slov
1
Úvod
délky jedna: ai 0 , ai1 ,... , aim −1 , při-čemž zkratka a ij místo j a a ij nese s sebou nebezpečí ztotožnění slova a ij délky
Záznam prázdného slova obvykle chápeme jako zápis „ničeho“, nebo kumulované přepsání, např. Bible na jedinou a tutéž stranu papíru. V obou případech není prázdné slovo „k přečtení“. Přesto se prázdné slovo zavádí na vstup konečných automatů a očekává se vyvolání, byť virtuálního, stavového přechodu. Pojem stavu se běžně vyskytuje v rozsáhlé literatuře o konečných automatech či logických systémech, avšak čtenář nalezne, pokud vůbec, zpravidla jen jeho intuitivní )* vymezení a musí se obvykle spokojit s konstatováním, že stavový přechod vyvolaný podnětem začíná ve výchozím stavu a končí ve stavu následovníku přechodu. A konečně, byť připouštíme jako experimentálně ověřenou pravdu, že jedny systémy popisujeme tak, jakoby byly deterministické, právě tak jiné popisujeme jen tak, jakoby byly nedeterministické a jindy tytéž systémy popisujeme v různou dobu podle potřeby tak či onak [1], přesto lze determinizovat jen takové nedeterministické systémy, u kterých jsme si jisti, že jejich deterministický popis je adekvátní.
2
(
Prázdným slovem ε nad libovolnou abecedou A rozumíme prázdnou posloupnost (|ε| = 0) ε : ∅ → A. I když je podle definice prázdné posloupnosti ε = ∅, rezervujeme znak ∅ pro prázdný jazyk. Je zajímavé uvést, že prázdné slovo není prázdným pojmem, jak název slova ε napovídá, ale pojmem jedinečným.)* S prázdným slovem lze totiž manipulovat
εα=αε=α a existuje právě jedno prázdné slovo, neboť předpokládámeli existenci různých ε1, ε2 (ε1 ≠ ε2), potom ε1α = αε2 = α = = ε2α =αε2 ⇒ε1 = ε2, což je spor. Mezera ( ) je písmeno, byť zpravidla neuváděné, každé abecedy; např. mezerník na klávesnicích není označen. }: n a (= ) nelze Avšak slovo {n} → { pokládat za slovo prázdné, které je prvkem každé množiny všech slov nad libovolnou abecedou. Poznamenejme, že přirozená čísla z {0,1, ..., m – 1}a písmena z abecedy A implementujeme příslušně jako okamžiky a jako názvy kvantových signálů ať hladinových (obvykle) či impulsových. Označme A* množinu všech slov konečné délky, tedy i vč. slova prázdného. Buď L, L jazyky nad A (L, L ⊆ A*). L L je zřetězení jazyka L s L tak, že každé slovo z L je zřetězené s libovolným slovem z L. Potom
Prázdné slovo
Buď dána konečná abeceda A. Slovem α (konečné délky |α| = m) rozumíme konečnou posloupnost
α : {0,1, ..., m − 1} → A : 0 a a i11 a a i 2 , ... ,
(
)
m − 1 a a i , m −1 = a i1 a i 2 ...a i ,m −1 .
Zřetězením
slov
η = η i 0 η i 2 ...η i ,m −1
a
)
jedna s písmenem a ij a ij ∈ A .
ϑ = ϑ j0
∅ L = L ∅ = ∅, {ε} L = L {ε} = L
ϑ j 2 ... ϑ j , n −1 rozumíme slovo
a iterace L* jazyka L je )* Intuice znamená, že víme něco samo o sobě, nikoliv na základě znalosti něčeho dalšího. V užším slova smyslu pak intuice znamená vágní pocit bez jakékoliv jistoty. Intuice různých lidí se samozřejmě značně liší.
)* Rozsah jedinečného pojmu má mohutnost jedna, zatímco rozsah a obsah prázdného pojmu je příslušně prázdný a sporný.
1
VOL.17, NO.1, FEBRUARY 2015
-
i
L* = U L , i∈N 0
kde N0 je množina všech přirozených čísel, vč. nuly a také i
-
i −1 1
L = L L pro i ≥ 1 , 0 přičemž L = {ε} a L1 = L. Uvažujme akceptor A = 〈 X , S , δ , sp , F 〉,
kde X, S, F je abeceda příslušně vstupní, stavová, finálních stavů (F ⊆ S), δ je přechodová funkce
-
δ : S × X → S : s , x a s ′, s , resp. pro
a s,
ξ = xip xi1 xi 2 ...xi , f −1 (ξ ∈ x *) budiž
δ : S × X* → S :
s p , x ip , x i1 x i 2 ... x i , f −1 a s f ,
sp je počáteční stav a říkáme, že A přijímá vstupní slovo ξ, neboť sf ∈ F. Uvádí se (např. v [2]), že Aε = 〈X, {sp}∪{sz},δ, sp, {sp}〉, kde δ(sp,ε) = sp, δ (sp,ξ) = sz, δ(sz,ξ) = sz, (ξ∈ ∈X*) – obr.1.a), je akceptorem prázdného slova ε. Nevěříme-li totiž, že δ (sp, ε) = sp (obr.1.b)), potom, pochyboval-li pozorovatel o přijetí prázdného slova ε akceptorem Aε, zavede se na vstup Aε neprázdné slovo ξ (ξ ≠ ε), které Aε převede do záchytného stavu sz, ve kterém Aε setrvá. Čili, dříve než se zavedlo na vstup Aε neprázdné slovo ξ, akceptor nepochybně přijímal prázdné slovo ε. Zmíněná doktrína vychází z toho, že neprázdné slovo je opakem slova prázdného, což nelze akceptovat. a)
ξ
sz
-
b)
ξ
sp
ε
sp
=
sp
Obrázek 1. Přechodový diagram akceptoru Aε : a) se záchytným stavem sz, b) bez záchytného stavu
3
Stav
Pojem stavu se ve verbálním popisu činnosti systému přirozeně nepoužívá. Říká se např. že program je v počátečním stavu, avšak myslí se tím inicializace heuristicky zavedených vnitřních proměnných, a nikoliv nastavení počáteční hodnoty proměnné popisující „stav“ programu jako celku. Stav je v podstatě statický, a proto je řízení podle stavu možné a účelné. Uveďme několik vybraných a zajímavých intuitivních vymezení pojmu stav systému ať přímo nebo uvedením jeho vlastností:
-
2
Stavem [3] rozumíme přesně definovanou podmínku nebo vlastnost, kterou lze rozpoznat, jakmile se znovu objeví. Každý systém má přirozeně mnoho stavů. Vnitřní proměnné systému [4] nejsou ani vstupní, ani výstupní a jejich význam spočívá v jejich působení na závislost mezi vstupními a výstupními proměnnými. Uvedená činnost se nazývá stavem systému, a proto je odezva určena podnětem a aktuálním stavem a stav následovník je určen právě tak. Stavem [5] rozumíme signály přicházející do kombinační části systému z části paměťové. Předpokládejme [6], že prehistorie systému popisuje všechny události vztahující se k systému od doby, kdy systém vznikl, až do současnosti, tj. předpokládejme, že prehistorie obsahuje záznam všech podnětů od doby, kdy systém začal fungovat. Předpokládáme-li, že situace uvnitř systému je určena prehistorií, závisí odezva na podnětu a prehistorii. Uvedená závislost je však beznadějně složitá a je tudíž bezprostředně nepoužitelná. Protože je paměť logického systému omezená, nemůže rozlišovat všechny možné prehistorie – nemůže si je totiž pamatovat. Říkáme proto, že dvě prehistorie jsou ekvivalentní, odpovídá-li na obě logický systém shodně. Je zřejmé, že logický systém může během svojí činnosti rozlišovat pouze konečný počet tříd rozkladu na množině všech prehistorií, vymezeném výše uvedenou relací ekvivalence. Třídy zmíněného rozkladu pak jsou vnitřními stavy systému V automatu [7] vystupují zprostředkující prvky fungující jako prvky paměťové . Stav paměti je pak vnitřním stavem automatu. Pouhá znalost [8] okamžitého podnětu nemusí stačit pro předpověď odezvy. Předchozí podněty mohly systém změnit natolik, že došlo ke změně odezvy. Jinými slovy, odezva obecně závisí jak na okamžitém podnětu, tak i na minulém působení podnětů na systém. Nejlépe by ovšem bylo nečinit rozdíl mezi aktuálním a předchozími podněty. Proto říkáme, že aktuální odezva závisí na stavu systému a čistě intuitivně vymezíme okamžitý stav jako takovou část přítomnosti a minulosti systému, která je nutná pro stanovení přítomných a budoucích odezev. Považujeme tedy stav systému za některou (vnitřní) charakteristiku systému, jejíž okamžitá hodnota určuje aktuální odezvu a ovlivňuje její budoucnost. S velkým zjednodušením lze říci, že stav je „úložištěm“ informace nebo pamětí podnětů. Je žádoucí, aby množina vnitřních stavů byla dosti bohatá pro uložení veškeré informace o minulosti systému. Často vzniká nutnost [9] popsat činnost systému, jehož odezvy závisejí nejen na podnětech, ale i na některé minulosti, tj. na signálech, které působily na systém dříve. Stavy tak odpovídají některé zapamatované minulosti, což umožňuje vyloučit čas jako explicitní proměnnou a vyjádřit odezvu v závislosti na stavu podnětu v daném okamžiku.
VOL.17, NO.1, FEBRUARY 2015
-
-
-
-
-
Vektory hodnot [10] vnitřních (stavových) proměnných systému nazýváme stavy systému. Stavy systému mají důležitou zprostředkovací úlohu ve vztazích mezi vstupními a výstupními vektory, vyjadřujícími činnost systému. Soubor hodnot [11] proměnných, které postačují k popisu systému v daném okamžiku, nazýváme stav systému. Chceme-li odstranit z matematického popisu (deterministického systému – pozn. autora) nejednoznačnost relace vstup-výstup, musíme v popisu systému vzít v úvahu další vlastnosti, veličiny, které charakterizují předchozí vývoj procesů v systému nebo okamžitý stav systému. Stav [12] systému vyjadřujeme pomocí veličin nazývaných stavovými veličinami. Základní vlastnost stavu [13] systému v okamžiku τ spočívá v separaci budoucnosti (t >τ) a minulosti (t < < τ) tak, že stav je nosičem veškeré informace o minulosti systému nutné k určení odezvy systému na libovolný podnět působící na systém v okamžiku τ. Pro zapamatování kompletní vstupní historie [14] systému slouží stavová paměť. Odezva systému závisí na stavu systému, neboť vstupní historie se zapamatovala jako stav paměti systému, a může nebo nemusí záviset na aktuálním podnětu. Stav systému v okamžiku τ je informace [15] o podnětech, shromážděná do okamžiku τ taková, že odezva v okamžiku t (t ≥ τ) je určena zmíněnou informací a podnětem v okamžiku τ.
X , X *, Y , δ , λ , ε ,
kde X, Y, je abeceda příslušně vstupní, výstupní, δ, λ jsou funkce δ : X * × X → X * : ξ , x a ξx ,
λ : X * ×X → Y : ξ , x a y a ε je veškerá kumulovaná vstupní prehistorie (ε ∈ X*), a položíme-li X* = S, ε = sp, přičemž S je konečná množina stavů a sp je počáteční stav (sp ∈ S), obdržíme konečno-automatový model daného systému X , S,Y ,δ , λ , s p ,
kde
δ : S × X → S : s, x a s ′ , λ : S × X → Y : s, x a y . Jinými slovy, stav je vstupním slovem a stavová abeceda je konečná množina vstupních slov (s tím, že místo o stavu následovníku s′ je nutné hovořit o jeho aktuální predikci – pozn. autora) Musíme ovšem připustit, že jednak δ (ε, ε) = ε = δ (s0, ε), což znamená přijetí prázdného slova ε systéme a jednak pro ξ ≠ ζ (ξ, ζ ∈ X*) může být δ (ξ, x) = ξx = δ (ξ, x) = ζx ⇒ ξ = ζ )**, což je spor, ale pro si ≠ sj (si, sj ∈ ∈S) může být δ (si, x) = s = = δ (sj, x), což sporné není (obr. 3.)
ξ
Každý dynamický systém si lze totiž představit podle obr. 2., kde M je „paměť“ posloupností podnětů x uchovávaných jako stav s – vstupní historie. Avšak, na rozdíl od paměťových zařízení, nemaže M svůj
si
x ξ=ζ ξx, ζx
ξ≠ζ
s
contra
x
x podnět (x)
M
stav (s)
O
ζ
odezva (y)
x
sj
Obrázek 3. Rozporné pojetí stavu podle [16] Obrázek 2. Blokové schéma dynamického systému. obsah, a proto hovoříme o kumulovaném obsahu M. Je-li s výchozí obsah „paměti“ a přijala-li M podnět x, obsah „paměti“ M se změní na s′.)* Jednotlivé vstupní ovšem nezbytné požadovat, aby množina historie jsou tak rozlišitelné. Obsah „paměti“ M před začátkem experimentování s dynamickým systémem označme sp – počáteční stav či vstupní nečitelná prehistorie systému. Pokusme se proto formalizovat intuitivně zavedený pojem stavu deterministického dynamického logické-ho systému. Podle [14] považujeme-li za model deterministického dynamického logického systému uspořádanou šestici )* Změna je popření neměnnosti či jiné změny.
Obraťme se proto k sofistikované Nerodově větě [8,17,18]. Uvažujme deterministický konečný poloautomat 〈X, S, δ, sp〉 a zaveďme na X* relaci ekvivalence ≡
(≡: ( X *)
2
(
= δ s p ,ξ
pravou
((
:ξ ≡ ζ
)
tak,
že
) )*. Zřejmě ξ ≡ ζ ⇒ ξ ≡ kongruenci
) )
((
≡N
(
)
ξ ≡ ζ ⇔ δ s p ,ξ = N
platí
ζ , přičemž pro ξ ≡N ζ ⇔
) ) pro ϑ ∈ X* - obr.
⇔ δ δ s p , ξ ,ϑ = δ δ s p , ζ ,ϑ
4. Pravá kongruence vymezuje na X* konečný (!) rozklad X * ≡ N = { [ξ ]i }i ( [ξ ] je třída rozkladu )* ⇒ je operátor implikace, ⇔ čteme tehdy a jen tehdy, když, nebo právě tehdy, když.
3
VOL.17, NO.1, FEBRUARY 2015
ξ
0
s′
sp
a
ϑ
s″
ζ
ξϑ
sp
s″
b
b
a
na poloautomat 〈X, S, δ, sp〉, tj. že podle komutativního
δˆ o f = ( f × i X ) o δ ,
f S resp.
[ ]) = δ ( f ([ξ ]) , x ) = δ (s, x ) = s ′ .
= f(ξ x
( [] )
f δˆ ( ζ , x ) =
Všechna
vstupní slova jednotlivých tříd rozkladu X * ≡ N představují jednak veškerou kumulovanou vstupní prehistorii – prázdné slovo ε – a jednak doložitelné vstupní historie – neprázdná slova – systému. Poznamenejme, že pro [ξ] = [ζ] nemůže být
δˆ ( [ξ ] , x ) ≠ δˆ ( [ζ ] , x ) , neboť [ξ] = [ζ] ⇒
⇒ δˆ ( [ξ ] , x ) = [ξx] = δˆ ( [ζ ] , x ) = [ζx].
Příklad 1.: K danému přechodovému diagramu (obr.5.a)) poloautomatu sestrojte přechodový diagram faktorového poloautomatu (obr.5.b)) podle isomorfismu faktorového poloautomatu na daný poloautomat. Zřejmě
{a, b}* ≡ N = {{ε }, {aa *}, {bb*, aa * bb},{aa *b}, )* {aa * baa *}} = { [ε ], [a ], [b, abb], [ab], [aba ]} ↔
[]
↔ {0,1, 2} : ε ↮ 0, [a] ↮ 1, [b,abb] ↮ 2, [ab] ↮
↮3, [aba] a 3.
Pokládáme tedy každou třídu konečného rozkladu na X* za stav systému s tím, že veškerá vstupní kumulovaná prehistorie je stavem počátečním.
b
a [aba] a
Na rozdíl od předchozího pojetí stavu podle [14] pro [ξ] ≠ [ζ] může být δ ( [ξ ] , x ) = [ξx ] = δ ( [ζ ] , x ) =
[ ]
diagramu kompozice funkcí (ix : X ↔ X : x ↮ x) δˆ X * ≅N × X X * ≅N
platí
[ab]
Obrázek 5. Přechodové diagramy poloautomatu a) daného, b) faktorového z příkl. 1.
faktorového poloautomatu X , X * ≡ N , δˆ, [ε ] , kde
δˆ : X * ≡ N × X → X * ≡ N : [ξ ], x a [ξx ]
b
b
4
reprezentovaná slovem ξ) takový, že existuje isomorfismus f: X * ≡ N ↔ S : [ξ ] ↮ s, [ε] ↮ sp
S×X
a
b [b,abb]
a
Obrázek 4. Pravá kongruence.
δ
[a]
3
ζϑ
f × iX
a
2
1 a
[ε]
b
b
= ζx , což není sporné. Pomineme-li nevhodnost výše uvedených objasnění či definic stavu pro identifikaci systému na stavové rozlišovací úrovni, je pozoruhodné, že stav systému se redukuje na obsah paměti systému, tj. na jeho kumulovanou vstupní historii, a samotná „paměť“, resp. konkrétní, individuální systém, zůstává téměř bez povšimnutí. Uveďme proto, že systém existuje tak, že kumulovaně uchovává a mění svoji vstupní historii, tj., že existuje, nalézaje se ve stavu a měně svůj stav. A dále, nachází-li se systém ve stavu, nalézal se dříve jistě ve stavu předchůdci; nachází-li se systém ve stavu, což se bohužel obvykle nezmiňuje a akceptuje-li podnět, pak vždy přejde do stavu následovníku. Nutnou a postačující příčinu změny stavu, resp. stavového přechodu, tedy je příslušně výchozí stav a přijatý podnět. Zamlčíme-li nutnou příčinu stavového přechodu – jeho výchozí stav, může se zdát, že akceptovaný podnět je nejen postačující, ale i nutnou příčinou stavové změny. Existenciální a kauzální vymezení stavu dynamického systému rovněž brání zpochybňování báze následující rekurentní definice stavu zahrnující i stavy nedeterministického logického systému (kap. 4.): - počáteční_stavy jsou stavy, - nachází-li se systém v některém stavu a akceptuje-li podnět délky jedna, je možný bezprostřední následovník rovněž stav. Poznamenejme, že „počáteční_stavy“ je nedělitelné sousloví. Výběr stavové abecedy je obecně značně složitá úloha a její řešení nemusí být jednoznačné. Právě tak nedisponujeme obecnými pravidly, jak podle verbálního popisu činnosti systému nalézt jeho stavy, ani konečný rozklad jeho vstupního jazyka. Proto se uchylujeme k postupnému vymezování stavové abecedy nahodilými zkouškami a event. napravitelnými omyly. Časová náročnost a pracnost výběru stavů i jejich počtu závisí na
4
VOL.17, NO.1, FEBRUARY 2015
intuici a znalostech subjektu identifikují-cího daný logický systém. Příklad 2.: Sledujme rekurentní a) zanoření i b) vynoření pro stav 3 podle obr. 6., kde počáteční stav 0 je bází rekurze: ad a) 3 = δ (1,c) = δ (δ (0,a), c) = δ (0, ac), 3= δ (1,c) = δ (δ (0,b), c) = δ (0, bc), ad b) δ(0,a)=1,δ(1,c)=δ(δ(0,a),c)= δ(0,ac)=3, δ(0,b)=2,δ(2,c)=δ(δ(0,b),c)=δ(0, bc)=3, přičemž δ (3,c) = δ (3, ab) = 3. 1
a
c
c
Následující dva příklady názorně ilustrují, jak je důležité odhadnout, co je stav systému. Příklad 3.: Identifikujte automat na výdej zboží za 25 měnových jednotek (fu) - 〈X, S, δ, sp, {s25}〉 - který přijímá pouze mince v hodnotě 5, 10 a 20 fu, tj. X = rep
s25
20
5
sp
5 10
s10
5 10
20
20
x1 x2
druhý; nachází-li se nad tmavým segmentem, poskytuje signál 0. Sestrojme konečno-automatový model zařízení signalizujícího směr otáčení 〈 X , S , Y , δ , λ〉,
kde X = {0,1} , S = X × Y = {0,1} a Y = {0,1} je abeceda příslušně vstupní (X = {〈x1, x2〉}), stavová a výstupní, (Y = {l, r}) přičemž 0 příp. 1 výstupní abecedy Y značí otáčení či posuv příslušně vlevo, příp. vpravo. Diagram přechodové δ a výstupní λ funkce modelu navrhněme jako planární kompozici (obr.8.c)) vývojových diagramů pro otáčení či posuv vlevo (obr.8.a)), příp. vpravo (obr.9.b)). 2
3
a)
10, 20
s15
r
Obrázek 8.: a) Kotouček, b) pravítko se střídavě průhlednými a neprůhlednými segmenty či ryskami z příkl.4..
b
Obrázek 6. Přechodový diagram z příkl. 2.
10
l
x1 x2
2
s5
b)
r
l
4
c
b
a)
a
3
0
(obr.8.a),b)) s rovnými, střídavě tmavými a průhlednými segmenty či ryskami se dvěma snímači x1, x2 navzájem posunutými o polovinu šířky jednoho segmentu. Při otáčení kotoučku či posuvu pravítka tedy jeden z obou snímačů produkuje signál 1, nachází-li se nad průhledným segmentem, vždy o půl šířky segmentu dříve než
110
01/0
5,10,20
100
01/0 00/0
s20
000
11/1
01/1 111 10/1 11/1
11/0
010
5
b)
11/0
101 00/1
011 10/0 01/1
10/0
10/1
001 00/1
00/0
Obrázek 7. Přechodový diagram automatu z příkl. 3.
Příklad 4.: Rozpoznání směru otáčení či posuvu je možné např. kotoučkem na hřídeli či pravítkem stolu
10110/1
c)
= {5, 10, 20, rep}. Pro stanovení postačujících 25 fu se automat nachází v jednom z pěti stavů: s5, s10, s15, s20, s25, jejichž názvy odpovídají aktuálnímu součtu fu vhozených mincí, tj. S = {sp, s5, s10, s15, s20, s25}. Automat mění svůj stav po vhození další mince a v koncovém stavu s25, vydá žádané zboží (obr. 7.) Přijal-li automat mince, jejichž úhrnná hodnota převyšuje 25 fu, pro jednoduchost, mince v nadbytečné hodnotě nevrací. Po vydání zboží se automat podnětem rep vrací do počátečního stavu sp. Poznamenejme jen, že automat je samočinně fungující zařízení – dynamický systém, zatímco konečný automat je jeho formální model.
10/1
10/1 01/0
11/0 110
11/1
00/1 11/0
10/0 11/0 10/0 100 01/0 00/0 01/0 00/1 11/1 10/0 00/0 000 01/1 11/1 01/1 00/0 111
010
011
00/1 001
01/1
Obrázek 9. Vývojové diagramy signalizace směru otáčení či posuvu a) vlevo, b) vpravo, c) výsledný z příkl. 4..
5
VOL.17, NO.1, FEBRUARY 2015
4
Determinizace
Buď dán nedeterministický akceptor Amed = 〈 X, S, δ, I, F 〉, kde δ je přechodová δ : S × X × S : 〈s, x, s′〉 relace a I je množina počátečních stavů (I ⊆ S). Determinizací [2,15,19] nedeterministického akceptoru rozumíme postup vedoucí k akceptoru deterministickému Adet = 〈X, 2S, δ, I, F 〉,
kde δ je přechodová S S δ : 2 × X → 2 : S , x a S ′ )*
funkce taková, že s ∈S ⇒ s′∈ S′ a F ={S ⎪S ⊆ S, S ∩F ≠ ≠ ∅}.
Příklad 5. Převeďte nedeterministický akceptor z obr. 10.a) na akceptor deterministický – obr. 10.b), resp. obr. 10.c). a)
a
{0}
a
0
{0,1}
b b
a
b a
→2
{i }i6=1
{i}i6=1
:
a)
1
b b
a
ε , hod a
3
c
2
b) b
{0}
b
b
1
a
{0,1,2}
a 2
6
0
a
b
a {} i i =1 , resp.
a ε , což znamená přebroušení všech stěn kostky tak, že tečky na stěnách nejsou viditelné. Jiný problém vznikne při logickém řízení determinizovaného nedeterministického systému. Např. nedeterministický systém podle obr. 11. a) se řídí tak, že se podle stavu 0 produkuje řízení a, které systém převede díky nahodilosti buď do stavu 1, nebo 2. Determinizovaný nedeterministický systém podle obr. 11.b) se řídí tak, že se podle stavu 0 produkuje řízení a, systém přejde do stavu 1, avšak podle stavu 1 by se mělo produkovat řízení buď b, nebo c, což předpokládá nedeterministický a tudíž nerealizovatelný příslušný řídicí automat.
2
a
{0,2}
× {hod } →
6 {} i i =1 , hod
b a
b
c)
b
1
b
b)
δ h.k . det : 2
a
a 0
samotném, pak determinizace daného systému vylučuje nahodilost nezbytně brutálním zásahem do okolí systému či do systému samotného. Např. hrací kostka funguje 6 6 i i =1 × {hod } × {} i i =1 : 0, hod , i , podle δ h.k . : {} 1, hod , i , ..., 6, hod,i〉. Po determinizaci však
0
a 3
Determinizovat však lze jen zdánlivě nedeterministické systémy vzniklé nesprávným odhadem stavové abecedy a přechodové relace. Např. nedeterministický akceptor z příkl. 5. rozpoznává slova (a∨ b)* ab (a∨ b)*, která právě tak rozpoznává determinizovaný akceptor z téhož příkladu (b*aa*b (b∨aa*b)*). Modeluje-li však nedeterministický konečný automat aktivitu nahodilosti z okolí systému nebo v systému
{1,2} 1
c
{3} 2 3 {4}
Obrázek 11. a) Nedeterministický, b) determinizovaný řízený systém.
5 Obrázek 10. Akceptor: a) nedeterministický, b), c) determinizovaný z příkl. 5.
a
4
Závěr
Prázdné slovo je sice adekvátním modelem veškeré kumulované vstupní prehistorie systému, nikoliv však modelem podnětu typu mezery. Rekurentní definice stavu může posloužit při identifikaci systému, i když se nemusíme plně smířit s požadavkem apriorní znalosti počátečního stavu. A konečně, byť je determinizace systému, pokládaného za nedeterministický, elegantní, skrývá v sobě nebezpečí neoprávněného vyloučení nahodilosti z činnosti systému.
)* 2S = {S ⎪ S ⊆ S} je potence množiny S.
6
VOL.17, NO.1, FEBRUARY 2015
Literatura [1] [2] [3] [4] [5]
[6] [7] [8] [9] [10] [11] [12]
Beer Stafford. Cybernetics and Ma-nagement. London, The English Universities Press LTD, 102 New-gate Street, 1962 Hopcroft John E.,Ullman Jeffrey D.Formá-lne jazyky a automaty. Bratislava, ALFA, 1978. Překlad Rovan B., Mikulecký P. Ashby Ross W. Kybernetika. Praha, Orbis, 1961. Překlad Berka Karel Gill Artur. Introduction to the Theory of Finite – State Machines. New York, ..., London, Mc Graw – Hill Book Co. Inc., 1962 Bartee Thomas C., Lebow Irwin L., Read Irving S. Theory and Design of Digital Machines. San Francisco, ..., London, Mc Graw – Hill Book Co. Inc., 1962 Minsky Marvin L. Finite and Infinite Machines. Massachussets, Prentice – Hall Inc. 1967 Siwiňski Jerzy. Uklady przelanczajance w automatyce. Warszawa, Wydawnictwo Naukowo – Techni- czne, 1968 Kalman R.E., Falb P.L., Arbib M.A. Topics in Mathematical System Theory. New York - ... – Sydney, Mc Graw – Hall Books Co., 1969 Baranov S.I. Sintez mikroprogram-mnych avtomatov. Leningrad, Energija, 1979 Frištacký Norbert et al. Logické systémy. Bratislava – Praha, ALFA – SNTL, 1986 Kotek Zdeněk, Vysoký Petr, Zdráhal Zdeněk. Kybernetika. Praha, SNTL, 1990, ISBN 80-0300584-1 Gvozdiak Ladislav, Boršč Michal, Vitko Anton. Základy kybernetiky. Bratislava, ALFA, 1990, ISBN 80-05-00677-2
[13]
[14] [15]
[16] [17] [15]
[16] [17] [18] [19]
7
Šalyto A.A. Switch-technologija. Algoritmizacija i programmirovanie zadač logičeskogo upravlenija. Sankt Peterburk, Nauka 1998, ISBN 5-02024 840-1 Hwang Enoch O. Digital Logic and Microprocessor Design with VHDL. Riverside, La Sierra University, 2005 ISBN 0-534-46593-5 Cassandras Christos G., Lafortune Stéphane. Introduction to Discrete Event Systems. New York, Springer Science + Business Media, LLC, 2008, ISBN_13: 178-0-387-33332-8 Brunovský Pavol, Černý Jan. Základy matematickej teórie systémov. Bratislava, Veda 1980 Chytil Milan. Automaty a gramatiky. Praha, SNTL, 1984 Cassandras Christos G., Lafortune Stéphane. Introduction to Discrete Event Systems. New York, Springer Science + Business Media, LLC, 2008, ISBN_13: 178-0-387-33332-8 Brunovský Pavol, Černý Jan. Základy matematickej teórie systémov. Bratislava, Veda 1980 Chytil Milan. Automaty a gramatiky. Praha, SNTL, 1984 Wonham W.M. Supervisory Control of DiscreteEvent Systems. Toronto, Uni-versity of Toronto, 2010. Dostupné z wonham_scdes2010.pdf Stranbing Howard, Weil Pascal. An Introduction to Finite Automata and their Connection to Logic. In: Modern Applications of Automata Theory, Singapure, World Scientific Publi- shing Co. Pte. Ltd., 2012, ISBN – 10 981-4271-04-7
