Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta
´ RSK ˇ ´ PRACE ´ BAKALA A
Jiˇr´ı Vytasil Univerz´ aln´ı diskr´ etn´ı simul´ ator Kabinet software a v´ yuky informatiky
Vedouc´ı bakal´aˇrsk´e pr´ace: RNDr. Martin Pergel, Ph.D. Studijn´ı program: Informatika Studijn´ı obor: Spr´ava poˇc´ıtaˇcov´ ych syst´em˚ u
Praha 2012
R´ad bych podˇekoval m´emu vedouc´ımu bakal´aˇrsk´e pr´ace, panu RNDr. Martinovi Pergelovi, Ph.D., za ochotu, cenn´e rady a vstˇr´ıcnost, kter´e mi projevoval v pr˚ ubˇehu psan´ı programu a t´eto pr´ace. D´ale bych r´ad podˇekoval sv´ ym koleg˚ um, se kter´ ymi jsem mohl konzultovat technologie a postupy. Nakonec bych r´ad podˇekoval sv´e rodinˇe za jejich podporu.
Prohlaˇsuji, ˇze jsem tuto bakal´aˇrskou pr´aci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u, literatury a dalˇs´ıch odborn´ ych zdroj˚ u. Beru na vˇedom´ı, ˇze se na moji pr´aci vztahuj´ı pr´ava a povinnosti vypl´ yvaj´ıc´ı ze z´akona ˇc. 121/2000 Sb., autorsk´eho z´akona v platn´em znˇen´ı, zejm´ena skuteˇcnost, ˇze Univerzita Karlova v Praze m´a pr´avo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı t´eto pr´ace jako ˇskoln´ıho d´ıla podle §60 odst. 1 autorsk´eho z´akona.
V Praze dne 31. 7. 2012
Podpis autora
N´azev pr´ace: Univerz´aln´ı diskr´etn´ı simul´ator Autor: Jiˇr´ı Vytasil Katedra: Kabinet software a v´ yuky informatiky Vedouc´ı bakal´aˇrsk´e pr´ace: RNDr. Martin Pergel, Ph.D., Kabinet software a v´ yuky informatiky Abstrakt: V t´eto pr´ace je rozebr´an n´avrh a implementace programu umoˇzn ˇuj´ıc´ıho prov´adˇet diskr´etn´ı simulace. D´ale je v programu implementov´ana vizualizace pr˚ ubˇehu diskr´etn´ı simulace. D˚ uraz je kladen pˇredevˇs´ım na univerzalitu. Kromˇe programu a jeho popisu jsou zde informace o diskr´etn´ı simulaci, kter´e umoˇzn´ı jednoduˇsˇs´ı pochopen´ı ˇcinnosti programu. Pro popis diskr´etn´ı simulace pouˇz´ıv´ame koneˇcn´e automaty a regul´arn´ı gramatiky. Zm´ınˇen´e ˇca´sti zde v´ıce popisujeme, abychom jednoduˇseji pochopili popis diskr´etn´ı simulace. Syst´em d´ale umoˇzn ˇuje u ´pravu vstupn´ıch soubor˚ u pro jednoduˇsˇs´ı pr´aci programu. Kl´ıˇcov´a slova: diskr´etn´ı simulace, koneˇcn´ y automat, regul´arn´ı gramatika
Title: Universal discrete simulator Author: Jiˇr´ı Vytasil Department: Department of Software and Computer Science Education Supervisor: RNDr. Martin Pergel, Ph.D., Department of Software and Computer Science Education Abstract: In this thesis we analyzed the design and implementation of the program allows you to perform discrete-event simulation. Further in the program we implemented visualization of discrete-event simulation. Emphasis is placed mainly on universality. In addition to the program and its description includes information of discrete-event simulation, which allows easier understanding of program operation. For a description of discrete-event simulation using finite-state automata and regular grammars. These parts are described more in order to more easily understand the description of the discrete-event simulation. The system also allows adjustment of input files for easier operation of the program. Keywords: deskrete event simulation, finite-state automaton, regular grammar
Obsah ´ Uvod
2
1 Simulace 1.1 Syst´em, model, modelov´an´ı . . . . . . 1.2 Definice simulace . . . . . . . . . . . . 1.3 Spojit´a simulace . . . . . . . . . . . . . 1.4 Diskr´etn´ı simulace . . . . . . . . . . . 1.4.1 Komponenty diskr´etn´ı simulace
. . . . .
3 3 3 4 4 5
2 Koneˇ cn´ y automat a gramatika 2.1 Koneˇcn´ y automat . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Gramatika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Pˇrevod regul´arn´ı gramatiky na koneˇcn´ y automat . . . . . . . . . .
6 6 10 11
3 Anal´ yza projektu 3.1 Programovac´ı jazyk . . . . . . . . . 3.2 Rozhodovac´ı konflikty . . . . . . . 3.2.1 Z´aklad jazyka . . . . . . . . 3.2.2 Automat . . . . . . . . . . . 3.2.3 Nedeterminismus automatu 3.2.4 V´ıce pˇrechodov´ ych funkc´ı . 3.2.5 Gramatika . . . . . . . . . . 3.2.6 Vizualizace . . . . . . . . .
. . . . . . . .
12 12 12 12 13 13 13 14 14
. . . .
15 15 16 20 21
5 Uˇ zivatelsk´ a dokumentace 5.1 Automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Gramatika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Ovl´ad´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22 22 28 33
Z´ avˇ er
36
Seznam pouˇ zit´ e literatury
37
Seznam tabulek
38
Pˇ r´ılohy
39
4 Implementace 4.1 Popis jednotliv´ ych souˇca´st´ı . 4.2 Koneˇcn´ y automat . . . . . . 4.3 Regul´arn´ı gramatika . . . . 4.4 Vizualizace . . . . . . . . .
. . . .
. . . .
1
. . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
. . . . .
. . . . . . . .
. . . .
´ Uvod C´ılem bakal´aˇrsk´e pr´ace je vytvoˇren´ı programu umoˇzn ˇuj´ıc´ıho prov´adˇet diskr´etn´ı simulace r˚ uzn´ ych jev˚ u. Pˇredmˇetem bakal´aˇrsk´e pr´ace je tak´e jazyk, kter´ y popisuje jednotliv´e u ´ˇcastn´ıky diskr´etn´ı simulace, a vhodn´a vizualizace diskr´etn´ı simulace. Zvolili jsme si toto t´ema, protoˇze jsme chtˇeli vytvoˇrit srozumiteln´ y program pro diskr´etn´ı simulace. V programu je kladen d˚ uraz pˇredevˇs´ım na univerzalitu. Univerzalitu jsme zaruˇcili pˇri pouˇzit´ı koneˇcn´eho automatu a regul´arn´ı gramatiky jako z´aklad jazyka. V´ıce o univerzalitˇe v 3.2.1. Vyuˇzit´ım koneˇcn´eho automatu a regul´arn´ı gramatiky jsme pouˇzili jiˇz zn´am´e prostˇredky, takˇze je popis diskr´etn´ı simulace jednoduˇsˇs´ı na pochopen´ı. Vytvoˇrili jsme program, kter´ y se d´a vyuˇz´ıt pro vizualizaci diskr´etn´ı simulace. D´a se ale tak´e vyuˇz´ıt pouze jej´ı ˇca´st reprezentuj´ıc´ı pr´aci diskr´etn´ı simulace, kter´a se d´a zavolat i z jin´e aplikace.
2
1. Simulace 1.1
Syst´ em, model, modelov´ an´ı
Syst´ em Syst´em je abstraktn´ı objekt, kter´ y byl vytvoˇren syst´emov´ ym pˇr´ıstupem. [4] Definice syst´emu od L. von Bertalanffyho: Syst´em je komplex prvk˚ u nach´azej´ıc´ıch se ve vz´ajemn´e interakci. V t´eto definici jsou zachyceny dvˇe z´akladn´ı vlastnosti kaˇzd´eho syst´emu. Tˇemi jsou jeho struktura a chov´an´ı. Struktura syst´emu ja d´ana element´arn´ımi prvky a vazbami mezi nimi. Pokud je syst´em tvoˇren r˚ uzn´ ymi prvky, mluv´ıme o strukturovan´em syst´emu. Jednotliv´e prvky jsou pak nestrukturovan´e syst´emy. Kaˇzd´ y prvek m´a obvykle ˇradu vlastnost´ı, oznaˇcovan´ ych jako atribut prvku. Chov´an´ı syst´emu je forma z´avislosti v´ ystupu syst´emu na vstupech.
Model Term´ın model je pouˇzit pro analogii mezi dvˇema syst´emy. Prvn´ı syst´em, kter´ y odpov´ıd´a zkouman´emu objektu, je modelovan´y syst´em. Druh´ y syst´em, kter´ y definujeme, je modeluj´ıc´ı syst´em. [1, 4] Vztah obou syst´em˚ u je d´an t´ım, ˇze kaˇzd´emu prvku P modelovan´eho stst´emu je pˇriˇrazen prvek Q modeluj´ıc´ıho syst´emu. Kaˇzd´emu atributu g prvku P je pˇriˇrazen atribut h prvku Q a pro hodnoty atribut˚ u g a h je d´ana nˇejak´a relace. [1, 4]
Modelov´ an´ı Vytv´aˇren´ı analogie mezi modely se naz´ yv´a modelov´an´ı. Modelovan´ y syst´em b´ yv´a oznaˇcov´an jako origin´al a m´ısto pojmu modeluj´ıc´ı syst´em se pouˇz´ıv´a term´ın model. [4]
1.2
Definice simulace
Dahl: Simulace je v´ yzkumn´a technika, jej´ıˇz podstatou podstata spoˇc´ıv´a v tom, ˇze zkouman´ y dynamick´ y syst´em nahrad´ıme jeho simul´atorem (modelem) a s n´ım prov´ad´ıme pokusy (experimenty) s c´ılem z´ıskat informaci o p˚ uvodn´ım zkouman´em syst´emu. Shannon: Simulace je proces tvorby modelu re´aln´eho syst´emu a prov´adˇen´ı experiment˚ u s t´ımto modelem za u ´ˇcelem dosaˇzen´ı lepˇs´ıho pochopen´ı chov´an´ı studovan´eho syst´emu ˇci za u ´ˇcelem posouzen´ı r˚ uzn´ ych variant ˇcinnosti syst´emu. 3
Naylor: Simulace je numerick´a metoda, kter´a spoˇc´ıv´a v experimentov´an´ı s matematick´ ymi modely re´aln´ ych syst´em˚ u na ˇc´ıslicov´ ych poˇc´ıtaˇc´ıch. Cendel´ın: Simulace je technika pro v´ yzkum dynamick´ ych syst´em˚ u, jej´ıˇz podstata spoˇc´ıv´a v tom, ˇze zkouman´ y syst´em nahrad´ıme jeho simulaˇcn´ım modelem a s t´ımto modelem prov´ad´ıme experimenty proto, abychom z´ıskali informace o p˚ uvodn´ım zkouman´em syst´emu. Origin´al (zkouman´ y syst´em) se v simulaci naz´ yv´a simulovan´y syst´em a simulaˇcn´ı model se naz´ yv´a simuluj´ıc´ı syst´em nebo tak´e simul´ ator.
1.3
Spojit´ a simulace
Spojit´a simulace je zaloˇzena na zmˇen´ach rovnomˇernˇe vzd´alen´ ych v ˇcase. Nejsou zde privilegovan´e okamˇziky. Na simulaci nahl´ıˇz´ıme v pravideln´ ych intervalech, at’ uˇz se dˇeje nˇeco zaj´ımev´eho, ˇci nikoliv.
1.4
Diskr´ etn´ı simulace
V diskr´etn´ı simulaci se zmˇeny dˇej´ı nespojitˇe v ˇcase. Model, nad kter´ ym diskr´etn´ı simulac prob´ıh´a, pak obsahuje chronologicky navazuj´ıc´ı dˇeje.
Procesy Proces je posloupnost logicky na sebe navazuj´ıc´ıch ud´alost´ı. Stavy proces˚ u V souvislosti s pl´anov´an´ım proces˚ u rozliˇsujeme ˇctyˇri stavy proces˚ u [1]: 1. Stav aktivn´ı. Proces je pr´avˇe prov´adˇen, tj. je pr´avˇe realizov´an v´ ypoˇcet odpov´ıdaj´ıc´ı nˇekter´e jeho ud´alosti. V aktivn´ım stavu m˚ uˇze b´ yt v dan´em okamˇziku v´ ypoˇctu nejv´ yˇse jeden proces. 2. Stav ukonˇ cen´ y. Proces je v tomto stavu, pokud je ukonˇcena jeho operaˇcn´ı ˇca´st. Takov´ y proces jiˇz nem˚ uˇze b´ yt ani aktivov´an, ani napl´anov´an k prov´adˇen´ı. 3. Stav pˇ ripraven´ y neboli suspendovan´ y. Proces je napl´anov´an k prov´adˇen´ı v nˇejak´em konkr´en´ım okamˇziku simul´arn´ıho ˇcasu. 4. Stav pasivn´ı. Proces nen´ı ukonˇcen´ y, ale nen´ı ani napl´anov´an k prov´adˇen´ı. K jeho vyvol´an´ı m˚ uˇze doj´ıt tehdy, bude-li napl´anov´an prostˇrednictv´ım nˇejak´eho jin´eho procesu. Jak´ ykoliv vytvoˇren´ y proces se v kaˇzd´em okamˇziku vyskytuje pr´avˇe v jednom z uveden´ ych stav˚ u. 4
1.4.1
Komponenty diskr´ etn´ı simulace
Mezi komponenty diskr´etn´ı simulace patˇr´ı: ˇcas, kalend´aˇr ud´alost´ı, gener´ator n´ahodn´ ych ˇc´ısel, statistiky a koneˇcn´e podm´ınky. Pˇredstavme si ˇcasovou pˇr´ımku pro ˇcas, kter´ y ub´ıh´a uvnitˇr simulace. Na t´eto pˇr´ımce m´ame spoustu bod˚ u odpov´ıdaj´ıc´ıch ud´alostem. Uvnitˇr simulace potˇrebujeme tyto ud´alosti proj´ıt a zpracovat v poˇrad´ı, jak leˇz´ı na pˇr´ımce. Pˇred spuˇstˇen´ım simulace jsme napl´anovali nˇekolik ud´alost´ı. Dalˇs´ı vznikly jako d˚ usledek pˇredeˇsl´ ych ud´alost´ı. Kalend´aˇr ud´alost´ı je ˇr´ıd´ıc´ı struktura simulaˇcn´ıho programu, kter´a zahrnuje pˇredevˇs´ım programov´e prostˇredky pro pl´anov´an´ı ud´alost´ı. Posloupnost ud´alost´ı v simulaˇcn´ım modelu nen´ı pˇrirozenˇe d´ana pˇredem. Proto je z´akladn´ım u ´kolem simulaˇcn´ıho programu tuto posloupnost vytv´aˇret a pr˚ ubˇeˇznˇe aktualizovat. A je to pr´avˇe kalend´aˇr ud´alost´ı, jenˇz mus´ı plnˇen´ı tohoto u ´kolu zajiˇst’ovat. [1] Z´ akladn´ı funkce kalend´ aˇ re ud´ alost´ı Vyˇzadujeme, aby kalend´aˇr zabezpeˇcoval ˇctyˇri z´akladn´ı funkce [5]: 1. zjistit, zda je dan´a ud´alost napl´anov´ana ˇci nikoliv, a v pˇr´ıpadˇe, ˇze napl´anov´ana je, zjistit hodnotou jej´ıho aktivn´ıho ˇcasu 2. vybrat proces s minim´aln´ı hodnotou aktivaˇcn´ıho ˇcasu, a pokud je takov´ ych proces˚ u se stejnou hodnotou v´ıce, vybrat ten s nejvyˇsˇs´ı prioritou 3. napl´anovat moment´alnˇe nenapl´anovanou ud´alost (proces) 4. zruˇsit pl´an moment´alnˇe napl´anovan´e ud´alosti (procesu) Simulace potˇrebuje generovat pseudon´ahodn´e veliˇciny, kter´e z´avis´ı na modelu. Toto je splnˇeno jedn´ım, nebo v´ıce pseudon´ahodn´ymi gener´atory. Pseudon´ahodn´a ˇc´ısla se vyuˇz´ıvaj´ı k napodoben´ı re´aln´ ych podm´ınek. Program neimplementuje pseudon´ahodn´ y gener´ator. V´ ystupem simulace jsou statistick´a data z´ıskan´a pˇri simulaci, kter´a mus´ıme d´ale zpracovat, abychom z´ıskali v´ ysledn´e informace. Program negeneruje statistiky. Pro simulaci je d˚ uleˇzit´e, aby mohla nˇekdy skonˇcit. Proto je nutn´e zav´est koncov´e podm´ınky, kdy simulace skonˇc´ı. Napˇr. v ˇcase t nebo po proveden´ı n ud´alost´ı.
5
2. Koneˇ cn´ y automat a gramatika 2.1
Koneˇ cn´ y automat
Definice • Abeceda je libovoln´a koneˇcn´a nepr´azdn´a mnoˇzina prvk˚ u oznaˇcovan´a p´ısmenem Σ. Prvky abecedy se naz´ yvaj´ı symboly nebo t´eˇz znaky abecedy. [12] u dan´e abecedy Σ. Posloup• Slovo v je libovoln´a koneˇcn´a posloupnost symbol˚ nost a1 , a2 , ..., an , kde ai (pro i = 1, 2, ..., n) ∈ Σ, je moˇzno zapsat zkr´acenˇe a1 a2 ...an , pokud t´ım nem˚ uˇze nastat nedorozumˇen´ı. [9] • Σ∗ = mnoˇzina vˇsech slov v abecedˇe Σ. • Σ+ = mnoˇzina vˇsech nepr´azdn´ ych slov v abecedˇe Σ. • Σ∗ = Σ+ ∪ {λ} • D´elka slova je poˇcet znak˚ u, kter´e slovo tvoˇr´ı. y symbol a znaˇc´ı se znakem ε. • Pr´azdn´e slovo neobsahuje ˇza´dn´ • Prefix oznaˇcuje zaˇca´tek slova, sufix konec slova. • Podslovo je pak jak´akoliv ˇca´st slova. • Pr´azdn´e slovo ε je souˇcasnˇe prefixem, sufixem i podslovem. • Jsou-li u, v, w, x slova nad abecedou Σ a u = vwx, pak je slovo w podslovem slova u. Kdyˇz je v = ε, pak je w prefixem, kdyz je x = ε, pak je w sufixem. [9]
Form´ aln´ı jazyk Definice. Form´aln´ı jazyk nad abecedou Σ je libovoln´ a mnoˇzina slov nad touto ∗ abecedou, tedy podmnoˇzinou Σ . Jazyk se obvykle znaˇc´ı p´ısmenem L (s indexy). [12] Koneˇ cn´ y a nekoneˇ cn´ y jazyk Koneˇcn´ y jazyk je jazyk obsahuj´ıc´ı koneˇcnˇe mnoho slov. Lze je zadat v´ yˇctem prvk˚ u. Nekoneˇcn´ y jazyk je jazyk obsahuj´ıc´ı nekoneˇcnˇe slov. Lze je zadat jen s pomoc´ı omezuj´ıc´ı podm´ınky charakterizuj´ıc´ı slova, kter´a jazyk obsahuje.
6
Deterministick´ y a nedeterministick´ y koneˇ cn´ y automat Definice. Deterministick´y koneˇcn´y automat je definov´an jako uspoˇr´ adan´ a pˇetice (Q, Σ, δ, q0 , F ), kde [11] : • Q je koneˇcn´a nepr´azdn´ a mnoˇzina stav˚ u. • Σ je koneˇcn´a nepr´azdn´ a mnoˇzina vstupn´ıch symbol˚ u, tzv. vstupn´ı abeceda. • δ je pˇrechodov´a funkce, δ : Q × Σ → Q. • q0 je poˇc´ateˇcn´ı neboli inici´aln´ı stav, q0 ∈ Q. • F je mnoˇzina koncov´ych neboli pˇrij´ımac´ıch stav˚ u, F ⊆ Q. Definice. Nedeterministick´y koneˇcn´y automat je definov´an jako uspoˇr´ adan´ a pˇetice (Q, Σ, δ, S, F ), kde [11] : • Q je koneˇcn´a nepr´azdn´ a mnoˇzina stav˚ u. a mnoˇzina vstupn´ıch symbol˚ u, tzv. vstupn´ı abeceda. • Σ je koneˇcn´a nepr´azdn´ • δ je pˇrechodov´a funkce, δ : Q × Σ → P (Q). • S je mnoˇzina poˇc´ateˇcn´ıch (inici´aln´ıch) stav˚ u, S ⊆ Q. u, F ⊆ Q. • F je mnoˇzina koncov´ych neboli pˇrij´ımac´ıch stav˚
Reprezentace koneˇ cn´ eho automatu Existuje nˇekolik reprezentac´ı koneˇcn´eho automatu. Zde uvedeme 4 zp˚ usoby, kter´e jsou pops´any v [8, 9, 10, 11]. V´ yˇ cet prvk˚ u Kaˇzd´ y mnoˇzinov´ y ˇclen dan´e pˇetice je urˇcen v´ yˇctem prvk˚ u, kter´e obsahuje. U pˇrechodov´e funkce jsou uvedena vˇsechna pravidla, jimiˇz se ˇr´ıd´ı. Pˇr´ıklad: Koneˇcn´ y automat pˇrij´ımac´ı slova zaˇc´ınaj´ıc´ı aab a konˇc´ıc´ı aab. M = ({q0 , q1 , q2 , q3 , q4 , q5 , q6 , q7 }, {a, b}, δ, q0 , {g6 }) kde pˇrechodov´a funkce vypad´a: 2.1 δ(q0 , a) = q1 δ(q1 , a) = q2 δ(q2 , a) = q7 δ(q3 , a) = q4
δ(q0 , b) = q7 δ(q1 , b) = q7 δ(q2 , b) = q3 δ(q3 , b) = q3
δ(q4 , a) = q5 δ(q5 , a) = q5 δ(q6 , a) = q4 δ(q7 , a) = q7
δ(q4 , b) = q3 δ(q5 , b) = q6 δ(q5 , b) = q3 δ(q7 , b) = q7
Tabulka 2.1: Pˇrechodovou funkci reprezentujeme v´ yˇctem vˇsech pˇrechod˚ u.
7
Tabulka Dalˇs´ı reprezentace je pomoc´ı tabulky. Z´ahlav´ı sloupc˚ u tvoˇr´ı symboly vstupn´ı abecedy a z´ahlav´ı ˇra´dk˚ u stavy automatu. Oznaˇcen´ı stav˚ u: • Poˇc´ateˇcn´ı stavy symbolem →. • Pˇrij´ımac´ı stavy symbolem ←. • Stavy, kter´e jsou souˇcasnˇe poˇca´taˇcn´ı i pˇrij´ımac´ı, symbolem. ↔. Pˇr´ıklad: (Totoˇzn´ y s pˇr´ıkladem u v´ yˇctu prvk˚ u.)
→
←
a q1 q2 q7 q4 q5 q5 q4 q7
q0 q1 q2 q3 q4 q5 q6 q7
b q7 q7 q3 q3 q3 q6 q3 q7
Tabulka 2.2: Koneˇcn´ y automat reprezentovan´ y tabulkou.
Stavov´ y diagram Stavov´ y diagram je tvoˇren mnoˇzinou vrchol˚ u pˇredstavuj´ıc´ı stavy automatu a orientovan´ ymi hranami mezi tˇemito vrcholy. Hrany jsou ohodnoceny symboly ze vstupn´ı abecedy. Pokud vede ze stavu qi do qj hrana se symbolem a, pak koneˇcn´ y automat ze stavu qi po pˇreˇcten´ı symbolu a pˇrejde do stavu qj . Poˇca´teˇcn´ı stavy jsou oznaˇceny → smˇeˇruj´ıc´ı do stavu. Pˇrij´ımac´ı bud’ dvojit´ ym kruhem, nebo → smˇeˇruj´ıc´ı ze stavu. Pˇr´ıklad: Obr´azek 2.1. Stavov´ y strom Stavov´ y strom je tvoˇren mnoˇzinou vrchol˚ u pˇredstavuj´ıc´ı stavy automatu a hranami mezi tˇemito vrcholy. Hrany jsou ohodnoceny symboly ze vstupn´ı abecedy. Z kaˇzd´eho vrcholu, kter´ y nen´ı listem, vych´az´ı pr´avˇe tolik hran, kolik m´a pˇr´ısluˇsn´ y stav n´asledn´ık˚ u. Pokud nˇejak´ y stav odpov´ıd´a v´ıce vrchol˚ um, pak hrany vych´azj´ı jen z jednoho z nich. Poˇca´teˇcn´ım stavem je koˇren stavov´eho stromu. Pˇrij´ımac´ı stavy jsou oznaˇceny bud’ dvojit´ ym kruhem, nebo → vedouc´ı z vrcholu. Pˇr´ıklad: Obr´azek 2.2. 8
Obr´azek 2.1: Stavov´ y diagram
Obr´azek 2.2: Stavov´ y strom
9
2.2
Gramatika
Regul´ arn´ı gramatika Form´aln´ı gramatikou naz´ yv´ame ˇctveˇrici (VN , VT , S, P ) [13] : • VN je koneˇcn´a mnoˇzina netermin´aln´ıch symbol˚ u • VT je koneˇcn´a mnoˇzina termin´aln´ıch symbol˚ u • S ∈ VN je poˇc´ateˇcn´ı netermin´aln´ı symbol • P je koneˇcn´a mnoˇzina pˇrepisovac´ıch pravidel Mnoˇziny VN a VT jsou disjunktn´ı, tj. VN ∩ VT = ∅. V je tzv. celkov´a abeceda, tj. V = VN ∪ VT . Regul´arn´ı gramatika dovoluje pouze pravidla ve tvaru X → wY, X → w, kde X, Y ∈ VN , w ∈ VT∗ .
Pˇ repisovac´ı syst´ emy Pˇrepisovac´ım syst´emem naz´ yv´ame dvojici R = (V, P ), kde [11] • V je koneˇcn´a abeceda • P je koneˇcn´a mnoˇzina pˇrepisovac´ıch pravidel Pˇrepisovac´ı pravodlo je uspoˇr´adan´a dvojice slov (α, β), kde α je slovo, kter´e obsahuje alespoˇ n jeden netermin´aln´ı symbol. Pravidlo (α, β) se obvykle zapisuje ve tvaru α → β. Pravidla se stejnou levou stranou lze zapsat i takto: α → β1 , α → β2 , ..., α → βn lze zapsat jako α → β1 |β2 |...|βn ˇ ık´ame, ˇze w se pˇr´ımo pˇrep´ıˇse na z (p´ıˇseme w ⇒ z), jestliˇze: R´ ∃u, v, x, y ∈ V ∗ w = xuy, z = xvya(u → v) ∈ P. ˇ ık´ame, ˇze w se pˇrep´ıˇse na z (p´ıˇseme w ⇒∗ z), jestliˇze: R´ ∃u1 , u2 , ..., un ∈ V ∗ w = u1 ⇒ u2 ⇒ ... ⇒ un = z. Posloupnost u1 , ..., un naz´ yv´ame odvozen´ım.
Jazyk Definice. Jazyk generovan´y gramatikou G je jazyk L(G) = {v|v ∈ T ∗ ∧ S ⇒∗ v}. [13] Slovo v tedy patˇr´ı do L(G), pokud plat´ı: • slovo v se skl´ad´a pouze z termin´aln´ıch symbol˚ u, • slovo v lze odvodit z poˇc´ ateˇcn´ıho symbolu S. 10
2.3
Pˇ revod regul´ arn´ı gramatiky na koneˇ cn´ y automat
Vˇ eta 1. Ke kaˇzd´e regul´arn´ı gramatice G = (VN , VT , S, P ) existuje koneˇcn´y automat A = (Q, Σ, δ, q0 , F ) takov´y, ˇze L(A) = L(G). D˚ ukaz. [11] L(G) je nˇejak´a regul´arn´ı gramatika obsahuj´ıc´ı pouze pravidla ve tvaru: X → aY a X → λ Definujme nedeterministick´ y koneˇcn´ y automat A = (VN , VT , δ, {S}, F ), kde: • F = {X|(X → λ) ∈ P } • δ(X, a) = {Y |(X → aY ) ∈ P } Jeˇstˇe L(G) = L(A)? 1) λ ∈ L(G) ⇔ (S → λ) ∈ P ⇔ S ∈ F ⇔ λ ∈ L(A) 2) a1 ...an ∈ L(G) ⇔ existuje odvozen´ı (S ⇒ a1 X1 ⇒ ... ⇒ a1 ...an Xn ⇒ a1 ...an ) ⇔ ∃X0 , ..., Xn ∈ VN tˇz. δ(Xi , ai+1 ) ∋ Xi+1 , X0 = S, Xn ∈ F ⇔ a1 ...an ∈ L(A)
11
3. Anal´ yza projektu 3.1
Programovac´ı jazyk
Jelikoˇz je c´ılem vytvoˇrit jazyk pro diskr´etn´ı simulace, nab´ız´ı se objektovˇe orientovan´e jazyky jako Java, C++, C#. D´ale je c´ılem kromˇe jazyka i vizualizace simulace. U C++ je designov´an´ı tˇeˇzkop´adnˇejˇs´ı a to i vˇcetnˇe knihovny QT. Z tohoto d˚ uvodu se C++ pˇr´ıliˇs nehod´ı. Nakonec jsme si jako jazyk zvolili C#.
3.2
Rozhodovac´ı konflikty
V t´eto sekci se budeme zab´ yvat hlavn´ımi rozhodovac´ımi konflikty, kter´e bylo potˇreba rozˇreˇsit.
3.2.1
Z´ aklad jazyka
Velmi d˚ uleˇzitou ot´azkou tohoto programu je univerz´alnost. Ot´azkou tedy je, co pouˇz´ıt jako jazyk, aby byla univerz´alnost zachov´ana. Odpovˇed´ı je nˇekolik, ale daj´ı se z´ uˇzit do dvou hlavn´ıch kategori´ı. Prvn´ı kategori´ı je vymyslet si vlastn´ı jazyk, kter´ y na nic nenavazuje. Do druh´e kategorie bych zaˇradil jazyky, u kter´ ych jako z´aklad vyuˇzijeme jiˇz zn´am´e prostˇredky. U prvn´ı kategorie mezi hlavn´ı d˚ uvody m˚ uˇzeme zaˇradit jednoduˇsˇs´ı programov´an´ı, jelikoˇz si m˚ uˇzeme vytvoˇrit jazyk, kter´ y bude vyhovovat n´am jako program´ator˚ um. Oproti tomu v druh´e kategorii, pokud si vybereme dobˇre, n´am odpadne ˇreˇsen´ı univerz´alnosti. Mezi dalˇs´ı v´ yhody se d´a zaˇradit jednoduˇsˇs´ı rozˇsiˇritelnost, protoˇze si jako z´aklad vybereme jiˇz zn´am´e prostˇredky, takˇze nˇekteˇr´ı uˇzivatel´e budou moci program pouˇz´ıvat s minimem obt´ıˇz´ı. Z v´ yˇse zm´ınˇen´ ych d˚ uvod˚ u jsme zvolili druhou kategorii. Ot´azkou je, co pouˇz´ıt jako z´aklad jazyka. Jako z´aklad jsme uvaˇzovali o automatu, gramatice, nebo vyuˇzit´ı nˇekter´eho z programovac´ıch jazyk˚ u (napˇr. C#, Java, ...). Vyuˇzit´ı programovac´ıho jazyku jsme si nevybrali, protoˇze bychom jen vytvoˇrili jin´ y interpret nˇekter´eho programovac´ıho jazyka. Jelikoˇz automat a gramatika jsou vz´ajemnˇe na sebe pˇrevoditeln´e, tak jsme se rozhodli pro vyuˇzit´ı obou tˇechto moˇznost´ı. Jako hlavn´ı pro simulaci jsme se rozhodli vyuˇz´ıt automat. Gramatiku nepouˇz´ıv´ame pro simulaci, ale jen ji pˇrevedeme na automat.
12
3.2.2
Automat
Automat˚ u existuje nˇekolik druh˚ u. Koneˇcn´e automaty, z´asobn´ıkov´e automaty, y pouˇzijeme. line´arnˇe omezen´e automaty a Turingovy stroje. [11] Ot´azkou je, kter´ Doporuˇcuje se, pokud je to moˇzn´e, pouˇzit´ı jednoduˇsˇs´ıho automatu. Nejjednoduˇsˇs´ım automatem je koneˇcn´ y automat. Pod´ıv´ame se, zda n´am koneˇcn´ y automat bude staˇcit. Pˇrechodov´a funkce u automatu n´am pom˚ uˇze reprezentovat pr´aci diskr´etn´ı simulace. Slova abecedy n´am mohou reprezentovat ˇcinnosti diskr´etn´ı simulace. Toto jsou pro n´as d˚ uleˇzit´e ˇca´sti, kter´e n´am koneˇcn´ y automat ˇreˇs´ı. Dalˇs´ı ˇc´asti, kter´ ymi jsou pˇredmˇety a procesy, simulace budeme definovat mimo koneˇcn´ y automat. Toto je jedna z ˇca´st´ı, kter´a n´am d´av´a odliˇsnosti od koneˇcn´eho automatu.
3.2.3
Nedeterminismus automatu
Koneˇcn´ y automat m˚ uˇze b´ yt deterministick´ y, ale i nedeterministick´ y. Ot´azkou tedy je, jak se s nedeterminismem vypoˇr´adat. Jedn´ım ˇreˇsen´ım by mohlo b´ yt nedeterminismus zak´azat, ale to bychom nemohli pouˇz´ıvat tento program pro vˇetˇsinu simulac´ı. Jako dalˇs´ı ˇreˇsen´ı bychom mohli pouˇz´ıt BFS, pomoc´ı kter´eho bychom v simulaci ˇreˇsili vˇsechny moˇzn´e cesty. V tomto ˇreˇsen´ı bychom dokonce dostali nejlepˇs´ı moˇzn´ y ˇcas. Ale jako nev´ yhodu bychom mohli oznaˇcit vˇetˇs´ı nekontrolovatelnost a pˇri vizualizaci nutnost nejdˇr´ıve simulaci dokonˇcit. Dokonˇcen´ı je pˇri vizualizaci nutn´e z toho d˚ uvodu, abychom mohli spr´avnˇe uˇzivateli signalizovat pˇrechod z jednoho stavu do jin´eho. Nakonec jsme se rozhodli pro n´asleduj´ıc´ı ˇreˇsen´ı nedeterminismu. Pˇri nedeterminismu se zavol´a podm´ınka, kterou uˇzivatel definoval. Zde pˇrechody m˚ uˇzeme mnohem v´ıce kontrolovat a nemus´ıme simulaci pˇred vizualizac´ı dokonˇcit, takˇze pˇri sloˇzitˇejˇs´ı simulaci je menˇs´ı pravdˇepodobnost ˇcek´an´ı.
3.2.4
V´ıce pˇ rechodov´ ych funkc´ı
Jelikoˇz zde nem´ame pˇredem danou sekvenci znak˚ u z abecedy, u kter´e chceme zjistit, zda je pˇrij´ım´ana naˇs´ım automatem, tak mus´ıme ˇreˇsit i probl´em v´ıce pˇrechodov´ ych funkc´ı vedouc´ı z jednoho stavu. Tohoto probl´emu se zbav´ıme stejnˇe jako probl´emu s nedeterminismem. Opˇet pouˇzijeme podm´ınky, kde to m˚ uˇzeme l´epe specifikovat.
13
3.2.5
Gramatika
Jako druhou ˇc´ast zad´av´an´ı diskr´etn´ı simulace jsme si zvolili gramatiku. Tˇech je tak´e nˇekolik druh˚ u, regul´arn´ı, bezkontextov´a, kontextov´a a typu 0. [11] Ot´azkou tedy je, jakou si vybereme. Jelikoˇz v naˇsem programu budeme gramatiku pˇrev´adˇet na koneˇcn´ y automat, logicky se nab´ız´ı regul´arn´ı gramatika. U regul´arn´ı gramatiky pouˇzijeme pouze pravidla typu: • X → aY a termin´al X, Y netermin´al • X→λ zde v programu λ nahrazena $ X netermin´al
3.2.6
Vizualizace
Souˇca´st´ı programu je i vizualizace diskr´etn´ı simulace. Ot´azkou tedy je, jak vizualizovat informace z diskr´etn´ı simulace. Jako jedna z variant se nab´ızela moˇznost zobrazen´ı stav˚ u s informacemi o pˇredmˇetech, kter´e se zde vyskytuj´ı. D´ale jinak zobrazit procesy s bliˇzˇs´ımi informacemi, kter´e pˇrech´az´ı z jednoho stavu do jin´eho. Toto zobrazen´ı je sice nejjednoduˇsˇs´ı na ˇcten´ı pr˚ ubˇehu diskr´etn´ı simulace, ale pˇri zobrazen´ı na menˇs´ıch obrazovk´ach by mohl nastat probl´em pˇri zobrazen´ı vˇetˇs´ıho mnoˇzstv´ı stav˚ u, ve kter´ ych bychom zobrazovali jeˇstˇe procesy. Proto jsme se pro toto zobrazen´ı nerozhodli. Dalˇs´ı variantou je zobrazit stavy a procesy zvl´aˇst’. T´ımto zp˚ usobem sn´ıˇz´ıme velikost stav˚ u. Ve stavech zobraz´ıme informace o pˇredmˇetech, kter´e se zde vyskytuj´ı, a n´azev procesu, kter´ y se zde v tento ˇcas vyskytuje. Procesy zobraz´ıme ve vedlejˇs´ım oknˇe jako seznam s bliˇz´ımi informacemi. D´ale zobraz´ıme informace o kalend´aˇri ud´alost´ı, abychom mˇeli lepˇs´ı pˇredstavu o nadch´azej´ıc´ıch ud´alostech. Pro tento zp˚ usob zobrazen´ı jsme se rozhodli z d˚ uvod˚ u, ˇze je celkem jednoduch´e z nˇej vyˇc´ıst pr˚ ubˇeh diskr´etn´ı simulace a i zobrazen´ı vˇetˇs´ıho mnoˇzstv´ı stav˚ u nen´ı velk´ y probl´em.
14
4. Implementace 4.1
Popis jednotliv´ ych souˇ c´ ast´ı
Celkov´ y program obsahuje nˇekolik souˇc´ast´ı pokr´ yvaj´ıc´ıch jednotliv´e ˇca´sti. Jsou jimi: • Automat • Gramatika • Vizualizace
Obr´azek 4.1: Diagram zachycuje vazby mezi projekty. Pokud vede ˇsipka od projektu X do projektu Y, tak existuje v Y reference na X. Projekt Automat je knihovna reprezentuj´ıc´ı koneˇcn´ y automat, jak jeho pr´aci, tak i naˇcten´ı. V´ıce se dozv´ıme v kapitole 4.2. Projekt Gramatika je knihovna reprezentuj´ıc´ı regul´arn´ı gramatiku. Tento projekt naˇcte gramatiku a pˇriprav´ı ji na pˇrevod na koneˇcn´ y automat. V´ıce se dozv´ıme v kapitole 4.3. Projekt vizualizace se star´a o zobrazen´ı diskr´etn´ı simulace. V´ıce se dozv´ıme v kapitole 4.4.
15
4.2
Koneˇ cn´ y automat
Zde budeme popisovat jednu ˇca´st programu popisuj´ıc´ı koneˇcn´ y automat.
Hlavn´ı tˇ r´ıdy Zde si uvedeme nˇekter´e hlavn´ı tˇr´ıdy a co reprezentuj´ı v r´amci koneˇcn´eho automatu. Mezi hlavn´ı tˇr´ıdy patˇr´ı tˇr´ıdy reprezentuj´ıc´ı jednotliv´e ˇc´asti koneˇcn´eho automatu. Jednou z nich je tˇr´ıda stav, kter´a reprezentuje jednotliv´e stavy koneˇcn´eho automatu. D´ale tu je tˇr´ıda abeceda, kter´a reprezentuje jednotliv´a slova abecedy. Tˇr´ıda predmet reprezentuje pˇredmˇety automatu, kter´e maj´ı procesy pˇrem´ıstit z jednoho stavu do jin´eho. Tˇr´ıda proces reprezentuje jednotliv´e procesy koneˇcn´eho automatu. Tyto procesy pˇredstavuj´ı konatele ˇcinnost´ı. Tˇr´ıda prechodova funkce reprezentuje pˇrechodov´e funkce koneˇcn´eho automatu. D´ale m˚ uˇze obsahovat n´azev podm´ınky, kter´a je potˇrebn´a pro spr´avn´e rozhodnut´ı. Tˇr´ıda podminka reprezentuje podm´ınky, kter´e jsou potˇrebn´e pro spr´avn´e zvolen´ı pˇrechodov´e funkce. Tˇr´ıda kalendar reprezentuje kalend´aˇr ud´alost´ı. Jednotliv´e ud´alosti jsou instancemi tˇr´ıdy Ud´ alost. Tˇr´ıda Automat obsahuje datov´e struktury pro ukl´ad´an´ı zm´ınˇen´ ych tˇr´ıd. D´ale prov´ad´ı pˇrechod z jednoho stavu do jin´eho.
Pr´ ace automatu Tˇr´ıda Automat reprezentuje koneˇcn´ y automat a prov´ad´ı jednotliv´e kroky diskr´etn´ı simulace. Obsahuje datov´e struktury reprezentuj´ıc´ı napˇr. abecedu, pˇrechodov´e funkce, atd. Prov´ad´ı pˇrechody z jednoho stavu do jin´eho a pˇri vol´an´ı podm´ınky prov´ad´ı jej´ı vyhodnocen´ı. D´ale pˇrev´ad´ı gramatiku na koneˇcn´ y automat. Tato tˇr´ıda je rozdˇelena do ˇctyˇr soubor˚ u. Jeden soubor se zab´ yv´a pˇreveden´ım regul´arn´ı gramatiky na koneˇcn´ y automat. Pˇrevod prov´ad´ı z pˇredpˇripraven´e regul´arn´ı gramatiky. K pˇrevodu pouˇz´ıv´a metody, kter´e z jednotliv´ ych ˇca´st´ı regul´arn´ı gramatiky vytvoˇr´ı postupnˇe jednotliv´e ˇc´asti koneˇcn´eho automatu (napˇr. netermin´aly pˇrevede na stavy). N´azev souboru je Automat gramatika. Dalˇs´ı soubor se zab´ yv´a vyhodnocen´ım podm´ınky. Tento soubor je urˇcen pro vyhodnocen´ı volan´e podm´ınky a urˇcen´ı spr´avn´e pˇrechodov´e funkce. K tomu je tak´e urˇcen seznam jiˇz volan´ ych podm´ınek, abychom se nezacyklili. Pˇri vyhodnocov´an´ı podm´ınek vytv´aˇr´ıme pˇrevodn´ı tabulku, kter´a slouˇz´ı pro pˇrevod pseudoparametr˚ u na parametry re´aln´e. N´azev souboru je Automat vyhodnoceni podminky.
16
V dalˇs´ım souboru ˇreˇs´ıme pˇrechod z jednoho stavu do jin´eho. K tomu vyuˇz´ıv´ame tak´e soubor urˇcen´ y k vyhodnocov´an´ı podm´ınek. Zde zjist´ıme aktu´aln´ı ud´alost a z t´eto ud´alosti dostaneme informace o procesu, stavu. Z tˇechto informac´ı urˇc´ıme pˇrechodovou funkci a slovo z abecedy. Pokud se n´am nepodaˇr´ı jednoznaˇcnˇe urˇcit pˇrechodovou funkci, zjist´ıme si z n´ı n´azev podm´ınky, kter´a ji urˇc´ı, a nech´ame ji vyˇreˇsit v souboru, kter´ y se zab´ yv´a vyhodnocov´an´ım podm´ınek. U slova z abecedy se pod´ıv´ame, zda nakl´ad´a pˇredmˇety na procesy nebo vykl´ad´a pˇredmˇety z proces˚ u. Pokud ano, zavolaj´ı se metody pro nakl´ad´an´ı ˇci vykl´ad´an´ı. D´ale pokud m´ame definov´an v´ ystup do souboru, provedeme v tomto souboru i tuto ˇcinnost. N´azev souboru je Automat zpracovani. Posledn´ı soubor obsahuje datov´e struktury, kter´e reprezentuj´ı vˇsechny d˚ uleˇzit´e ˇc´asti automatu, jako napˇr. pˇredmˇety, procesy, slova abecedy, pˇrechodov´e funkce, podm´ınky, stavy, chyby. V tomto souboru jsou tak´e metody viditeln´e zvenˇc´ı, kter´e slouˇz´ı napˇr. pro vytvoˇren´ı instance t´eto tˇr´ıdy, ˇci pro prov´adˇen´ı diskr´etn´ı simulace. Zde si n´aslednˇe vytv´aˇr´ıme inici´aln´ı ud´alosti, kde se jednotliv´e procesu budou nach´azet. A prov´ad´ıme si tu kontrolu, aby koneˇcn´ y automat obsahoval vˇsechny d˚ uleˇzit´e ˇc´asti. N´azev souboru je Automat inicializace.
Slova z abecedy Tˇr´ıda abeceda je urˇcen´a pro reprezentaci slov z abecedy. Slovo urˇcuje ˇcinnost simulace. Zde si pamatujeme n´azev slova z abecedy, resp. ˇcinnosti simulace, ˇc´ıslo ˇr´adku vyuˇz´ıvan´e pˇri nalezen´ı chyby a hodnoty indikuj´ıc´ı, zda je moˇzn´e u t´eto ˇcinnosti nakl´ad´an´ı pˇredmˇet˚ u, vykl´ad´an´ı pˇredmˇet˚ u, nebo si tuto ˇcinnost budeme pamatovat pro vyhodnocov´an´ı podm´ınek.
Kalend´ aˇ r ud´ alost´ı Tˇr´ıda kalendar reprezentuje jednotliv´e ud´alosti. Zde si pamatujeme nejbliˇzˇs´ı ud´alosti pro kaˇzd´ y proces. Jednotliv´e ud´alosti jsou instanc´ı tˇr´ıdy Ud´ alost. Tato tˇr´ıda slouˇz´ı pro vytv´aˇren´ı nov´ ych ud´alost´ı a odstraˇ nov´an´ı jiˇz probˇehl´ ych ud´alost´ı.
Podm´ınky pro spr´ avn´ e vyhodnocov´ an´ı Tˇr´ıda podminka je urˇcen´a pro reprezentaci podm´ınek. Podm´ınky slouˇz´ı pro vybr´an´ı spr´avn´e pˇrechodov´e funkce. Zde si pamatujeme n´azev podm´ınky, seznam pseudoparametr˚ u, za kter´e pˇri vol´an´ı dosad´ıme re´aln´e. D´ale je tu v´ yraz pro vyhodnocen´ı, kter´ y vrac´ı true, nebo false. Nakonec tu jsou vˇetve then a else a ˇc´ısla ˇr´adk˚ u, na kter´ ych podm´ınka zaˇc´ın´a a konˇc´ı v souboru. Pro vˇetev then a else pouˇz´ıv´ame abstraktv´ı tˇr´ıdu, kam ukl´ad´ame bud’ vˇetev reprezentuj´ıc´ı pˇrechodovou funkci, nebo vˇetev reprezentuj´ıc´ı vol´an´ı dalˇs´ı podm´ınku.
17
Pˇ redmˇ ety Tˇr´ıda predmet je urˇcen´a pro reprezentaci pˇredmˇet˚ u. Tyto pˇredmˇety jsou n´aslednˇe procesy pˇrev´aˇzeny z jednoho stavu do jin´eho. Zde si pamatujeme n´azev pˇredmˇetu, mnoˇzstv´ı, ˇcas, kdy s pˇredmˇetem m˚ uˇzeme zaˇc´ıt pracovat, startovn´ı stav, stav, kam je potˇreba dopravit, a ˇc´ıslo ˇr´adku pˇri pˇr´ıpadn´em v´ yskytu chyby.
Pˇ rechodov´ e funkce koneˇ cn´ eho automatu Tˇr´ıda prechodova funkce je urˇcen´a pro reprezentaci pˇrechodov´e funkce koneˇcn´eho automatu. Zde si pamatujeme n´azev stavu, ze kter´eho je pˇrechodov´a funkce vol´ana, zda je v pˇrechodov´e funkci vol´ana nˇejak´a podm´ınka pro zjiˇstˇen´ı spr´avn´e pˇrechodov´e funkce, ˇc´ıslo ˇr´adku ze souboru pro pˇr´ıpadn´e vyps´an´ı chyby. N´aslednˇe si zde pamatujeme bud’ n´azev slova z abecedy a stav, kam se pˇresuneme, nebo n´azev podm´ınky, kterou budeme volat, a seznam pˇred´avan´ ych parametr˚ u. Z pˇredchoz´ıho plyne, ˇze nikdy nejsou vyplnˇeny vˇsechny promˇenn´e. Pokud pˇrechodov´a funkce nevol´a ˇza´dnou podm´ınku, tak nen´ı vyplnˇen seznam parametr˚ u. A pokud podm´ınku vol´ame, tak nen´ı vyplnˇen stav, kam se pˇresuneme.
Stavy automatu Tˇr´ıda stav je urˇcen´a pro reprezentaci stavu koneˇcn´eho automatu. Zde si pamatujeme n´azev stavu a zda je stav pˇrij´ımac´ı, ˇci nikoliv a d´ale pro spr´avn´e oznaˇcen´ı chyby ˇc´ıslo ˇra´dku ze souboru.
Dalˇ s´ı tˇ r´ıdy Zde pop´ıˇseme dalˇs´ı tˇr´ıdy, kter´e automat obsahuje. Tyto tˇr´ıdy jsou zm´ınˇen´e zde, protoˇze se pouˇz´ıvaj´ı jen jednou, nebo jsou jednoduch´e na vysvˇetlen´ı. Cteni souboru Tˇr´ıda pˇreˇcte soubor a vytvoˇr´ı poloˇzky datov´ ych struktur automatu. Tˇr´ıda obsahuje jednu metodu pro ˇcten´ı souboru a vytv´aˇren´ı instanc´ı jin´ ych tˇr´ıd. Tyto instance tvoˇr´ı poloˇzky datov´ ych struktur automatu. Prevoz Tˇr´ıda reprezentuj´ıc´ı jednotliv´e poloˇzky, kter´e jsou naloˇzeny na procesech. Promˇenn´e reprezentuj´ı n´azev pˇredmˇetu, c´ılov´ y stav a poˇcet n´akladu na procesu.
18
Udalost Tˇr´ıda reprezentuj´ıc´ı jednotliv´e ud´alosti. Promˇenn´e reprezentuj´ı ˇcas ud´alosti, n´azev procesu, slovo abecedy, stav, ve kter´em se proces bude nach´azet, a n´aklad. N´aklad je reprezentov´an seznamem instanc´ı tˇr´ıdy prevoz. Avetev Abstraktn´ı tˇr´ıda slouˇz´ıc´ı jako pˇredek pro tˇr´ıdy vetev konecna a vetev podminka. Obsahuje promˇennou reprezentuj´ıc´ı bud’ slovo abecedy (vetev konecna), nebo n´azev dalˇs´ı podm´ınky (vetev podminka). D´ale obsahuje hlaviˇcku metody vyhodnot. Vetev konecna Tˇr´ıda reprezentuj´ıc´ı vˇetev podm´ınky, kter´a obsahuje pˇrechodovou funkci. Pˇredkem je abstraktn´ı tˇr´ıda Avetev. Metoda obsahuje promˇenn´e pro stavy reprezentuj´ıc´ı stav odkud a stav kam. Vetev podminka Tˇr´ıda reprezentuj´ıc´ı vˇetev podm´ınky, kter´a obsahuje vol´an´ı dalˇs´ı podm´ınky. Pˇredkem je abstraktn´ı tˇr´ıda Avetev. Metoda obsahuje seznam reprezentuj´ıc´ı parametry, kter´e se pˇredaj´ı volan´e podm´ınce.
19
4.3
Regul´ arn´ı gramatika
Tato ˇc´ast programu obsahuje jen dvˇe tˇr´ıdy, jelikoˇz se bude n´aslednˇe gramatika pˇrev´adˇet na automat.
Pr´ ace gramatiky Tˇr´ıda Gramatika reprezentuje naˇcten´ı gramatiky ze souboru a n´aslednou u ´pravu pro pˇrevod na koneˇcn´ y automat. Tˇr´ıda je rozdˇelena do tˇr´ı soubor˚ u. Jeden soubor reprezentuje ˇcten´ı gramatiky ze souboru a n´asledn´e uloˇzen´ı regul´arn´ı gramatiky do datov´ ych struktur. Zde jsou promˇenn´e pro pˇrij´ımac´ı stavy, kter´e mohou b´ yt zad´any bud’ pomoc´ı automatov´e syntaxe, nebo pˇres pravidla, ale ne obˇema zp˚ usoby. N´azev souboru je Gramatika cteni ze souboru. Dalˇs´ı soubor reprezentuje u ´pravu gramatiky pro pˇrevod na koneˇcn´ y automat. Zde si vytvoˇr´ıme seznamy pro reprezentaci netermin´al˚ u, termin´al˚ u a dalˇs´ıch ˇc´ast´ı, kter´e se n´aslednˇe budou jednoduˇsˇseji pˇrev´adˇet na koneˇcn´ y automat. Tak´e si zde vytv´aˇr´ıme podm´ınky, kter´e pouˇzijeme pˇri pr´aci koneˇcn´eho automatu. N´azev souboru je Gramatika prevod na KA. Posledn´ı soubor obsahuje definice datov´ ych struktur pro uloˇzen´ı gramatiky. Zde jsou datov´e struktury pro uloˇzen´ı d˚ uleˇzit´ ych informac´ı, napˇr. pravidel, proces˚ u, pˇredmˇet˚ u a dalˇs´ı. Zde vytv´aˇr´ıme instanci t´eto tˇr´ıdy a n´aslednˇe upravujeme pravidla, aby ˇsla jednoduˇseji pˇrev´est na pˇrechodov´e funkce koneˇcn´eho automatu. N´azev souboru je Gramatika inicializace.
Pravidla gramatiky Tˇr´ıda pravidlo reprezentuje pravidla gramatiky. Obsahuje promˇenn´e pro netermin´al, ze kter´eho je pravidlo vol´ano, d´ale termin´al reprezentuj´ıc´ı ˇcinnost automatu, netermin´al, kam se pomoc´ı tohoto pravidla dostaneme, podm´ınku, pokud je nutn´a. D´ale obsahuje ˇc´ısla ˇra´dk˚ u, kde pravidlo zaˇc´ın´a a konˇc´ı, a odkaz na dalˇs´ı pravidlo, pokud existuje. Zde nebudou vyplnˇen´e vˇsechny promˇenn´e, stejnˇe jako u pˇrechodov´ ych funkc´ı koneˇcn´eho automatu.
20
4.4
Vizualizace
Kaˇzd´a z n´asleduj´ıc´ıch tˇr´ıd reprezentuje jedno zobrazovan´e okno.
Uv´ıtac´ı obrazovka Okno MainWindow se zobraz´ı po spuˇstˇen´ı programu. Slouˇz´ı k otevˇren´ı pr´azdn´eho editoru, nebo otevˇre soubor, nebo se ukonˇc´ı.
Editor Okno Editor Automat slouˇz´ı pro u ´pravu automatu, nebo gramatiky. Toto okno obsahuje editor z programu AvalonEdit, kter´ y je pod licenc´ı LGPL-3.0. Obsahuje menu pro otevˇren´ı souboru, uloˇzen´ı souboru, otevˇren´ı nov´eho souboru a ukonˇcen´ı programu. D´ale jsou v menu poloˇzky pro spuˇstˇen´ı automatu a gramatiky. N´aslednˇe z tohoto okna lze spustit diskr´etn´ı simulaci.
Chyby Toto okno se zobraz´ı, pokud jsou v automatu nebo gramatice chyby. Tyto chyby jsou n´aslednˇe v editoru podtrˇzen´e ˇcervenˇe.
Zobrazen´ı atav˚ u Okno Automat zobrazeni se zobraz´ı, pokud nenastane chyba pˇri ˇcten´ı automatu nebo gramatiky. Zde se zobrazuj´ı stavy s bliˇzˇs´ımi informacemi o pˇredmˇetech, kter´e se v nich nach´azej´ı. D´ale zobrazuje n´azvy proces˚ u, kter´e se v tu chv´ıli v nich nach´azej´ı.
Zobrazen´ı kalend´ aˇ re Okno Automat kalendar se zobraz´ı spolu s okny Automat zobrazeni a Automat procesy. Zobraz´ı aktu´aln´ı ˇcas a ud´alosti obsaˇzen´e v kalend´aˇri.
Zobrazen´ı proces˚ u Okno Automat procesy se zobraz´ı spolu s okny Automat zobrazen´ ı a Automat kalendar. Zobraz´ı procesy a informace o jejich n´akladu, jako n´azev, mnoˇzstv´ı a c´ılov´ y stav.
21
5. Uˇ zivatelsk´ a dokumentace 5.1
Automat
Pˇ r´ıklad Uk´aˇzeme si pˇr´ıklad, na kter´em si demonstrujeme z´akladn´ı ˇca´sti koneˇcn´eho automatu, vˇcetnˇe podm´ınky. Pˇredmˇety co pisek 1000 0 (vydejce,vylozen) (prijemce,nalozen) co pisek 2000 500 (vydejce,vylozen) (prijemce,nalozen) Procesy p auto 10 (vydejce,vylozen):100 100 60 10 10 p auto2 100 (vydejce,vylozen):0 150 30 10 10
Q Q Q Q
Stavy (vydejce,vylozen) (vydejce,nalozen) (prijemce,vylozen) (prijemce,nalozen)
Pˇrij´ımac´ı stavy F (prijemce,vylozen)
X X X X
Slova abecedy jet pomalu jet nalozit + vylozit -
d d d d
Pˇrechodov´e funkce (vydejce,vylozen) nalozit (vydejce,nalozen) (vydejce,nalozen) check jizda [(vydejce,nalozen) (prijemce,nalozen)] (prijemce,nalozen) vylozit (prijemce,vylozen) (prijemce,vylozen) check jizda [(prijemce,vylozen) (vydejce,vylozen)]
Podm´ınky check jizda (x, y) { cas < 250 then (x) jet pomalu (y) else (x) jet (y) } Vlastn´ı v´ypis %predmet.name a proces.name spolu s casem aktualni.cas%
22
Vstupn´ı data Vstupn´ı data pro bˇeh programu mus´ı b´ yt uloˇzena v souboru s pˇr´ıponou .txt, jin´e koncovky program neakceptuje. Vstupn´ı soubor je logicky rozdˇelen do nˇekolika ˇc´ast´ı: • Promˇenn´e • Pˇredmˇety automatu • Procesy automatu • Stavy • Pˇrij´ımac´ı stavy • Abeceda • Pˇrechodov´e funkce • Podm´ınky • Vlasn´ı v´ ypis Koment´aˇre v souboru jsou pouze ˇra´dkov´e, tj. od posloupnosti znak˚ u // do konce ˇr´adku. Pˇri definov´an´ı vlastn´ıho v´ypisu budeme do souboru vypisovat n´ami zadan´a text.
Promˇ enn´ e Tato ˇc´ast je nepovinn´a pro bˇeh programu. Tato ˇc´ast se d´a vyuˇz´ıt pouze v podm´ınk´ach, kde slouˇz´ı ke zjednoduˇsen´ı vyhodnocov´an´ı podm´ınek, a pˇri vlastn´ım v´ ypisu. Promˇenn´ ych je omezen´ y poˇcet a vyskytuj´ı se jen ve v´ yrazu urˇcen´em k vyhodnocen´ı v podm´ınk´ach. Promˇenn´a se skl´ad´a ze dvou poloˇzek oddˇelen´ ych teˇckou. Prvn´ı poloˇzkou je n´azev logick´e ˇc´asti, kam promˇenn´a ukazuje (proces, predmet, abeceda). Druh´a poloˇzka pak ukazuje na konkr´etn´ı n´azev, na kter´ y se m˚ uˇzeme odk´azat v logick´e ˇca´sti, kterou m´ame urˇcenou prvn´ı poloˇzkou. Seznam moˇzn´ ych kombinac´ı, kter´e lze pouˇz´ıt v promˇenn´ ych: • proces.name tato promˇenn´a reprezentuje n´azev aktu´aln´ıho procesu • proces.kapacita tato promˇenn´a n´am dovoluje pˇristoupit k voln´e kapacitˇe procesu, kter´ y pr´avˇe vykon´av´a nˇejakou ˇcinnost • predmet.name tato promˇenn´a reprezentuje n´azvy pˇredmˇet˚ u 23
• predmet.kapacita zde zjist´ıme mnoˇzstv´ı pˇredmˇetu, kter´e jeˇstˇe zb´ yv´a pˇrem´ıstit • predmet.start zde zjist´ıme, kdy bude pˇredmˇet pˇripraven k pˇremist’ov´an´ı • predmet.in zde zjist´ıme, kde pˇredmˇet zaˇc´ın´a svou pout’ • predmet.out zde zjist´ıme, kam m´ame pˇredmˇet pˇrem´ıstit • abeceda.last zde dostaneme posledn´ı slovo z abecedy, kter´e je oznaˇceno znakem @ • aktualni.cas zde dostaneme aktu´aln´ı ˇcas • stav.konec tato promˇenn´a reprezentuje pˇrij´ımac´ı stavy • aktualni.stav tato promˇenn´a reprezentuje aktu´aln´ı stav, ve kter´em se proces nach´az´ı. tato promˇenn´a lze pouˇz´ıt pouze ve vlastn´ım v´ ypisu
Pˇ redmˇ et automatu Tato ˇc´ast je povinn´a pro bˇeh programu. Tato ˇc´ast n´am ˇr´ık´a, co se bude bˇehem bˇehu programu pˇremist’ovat z jednoho m´ısta do jin´eho m´ısta. Tak´e n´am ˇr´ık´a, kdy m˚ uˇzeme program ukonˇcit. Z´apis pˇredmˇetu v souboru: ˇr´adek zaˇc´ın´a slovem co, za kter´ ym n´asleduje tabul´ator. D´ale n´asleduje v tomhle poˇrad´ı: • n´azev • poˇcet • startovn´ı ˇcas, kdy s t´ımto pˇredmˇetem m˚ uˇzeme pracovat • m´ısto, na kter´em bude tento pˇredmˇet ˇcekat na zpracov´an´ı • m´ısto, kam pˇredmˇet pˇrem´ıst´ıme
24
Proces automatu Tato ˇca´st je povinn´a pro bˇeh programu. Ud´av´a n´am konatele, kter´ y bude proch´azet automatem. Z´apis procesu v souboru: ˇr´adek zaˇc´ın´a znakem p, kter´ y je n´asledov´an tabul´atorem. D´ale n´asleduj´ı tyto ˇc´asti: • n´azev • kapacita • startovn´ı m´ısto : startovn´ı ˇcas • n´asleduje seznam ˇcas˚ u pro jednotliv´e znaky z abecedy ve stejn´em poˇrad´ı, v jak´em jsou dan´e v abecedˇe
Stavy automatu Tato ˇca´st je povinn´a pro bˇeh programu. Ud´av´a n´am m´ısta, ve kter´ ych sledujeme diskr´etn´ı simulaci. Ve stavech sledujeme procesy, co tam pr´avˇe vykon´avaj´ı. Z´apis stavu v souboru: ˇr´adek zaˇc´ın´a znakem Q, kter´ y je n´asledov´an tabul´atorem. Pot´e n´asleduje jen jedna ˇc´ast, a to n´azev stavu. V n´azvu stavu se nesm´ı vyskytovat b´ıl´e znaky.
Pˇ rij´ımac´ı stavy Tato ˇc´ast je povinn´a pro bˇeh programu. Ud´avaj´ı n´am stavy, ve kter´ ych se mus´ı nach´azet procesy, aby simulace mohla b´ yt ukonˇcena. Z´apis stavu v souboru: ˇr´adek zaˇc´ın´a znakem F, kter´ y je n´asledov´an tabul´atorem. Pot´e m˚ uˇze nastat jedna ze dvou moˇznost´ı: • nap´ıˇseme n´azev stavu, kter´ y budeme cht´ıt m´ıt za pˇrij´ımac´ı • pouˇzijeme znak Q, kter´ y n´am ˇr´ık´a, ˇze za pˇrij´ımac´ı stavy chceme pouˇz´ıt vˇsechny stavy automatu
25
Abeceda Tato ˇca´st je povinn´a pro bˇeh programu. Ud´av´a n´am ˇcinnosti, pomoc´ı kter´ ych procesy pˇrech´az´ı z jednoho stavu do jin´eho. Z´apis abecedy v souboru: ˇr´adek zaˇc´ın´a znakem X, kter´ y je n´asledov´an tabul´atorem. D´ale obsahuje povinnˇe n´azev a nepovinnˇe m˚ uˇze obsahovat nˇekter´e z n´asleduj´ıc´ıch znak˚ u oddˇelen´e mezerou. • znak @ indikuje, ˇze takto oznaˇcen´a ˇcinnost, kter´a byla pouˇzita naposled, bude uloˇzena v promˇenn´e abeceda.last • znak + indikuje nakl´ad´an´ı pˇredmˇet˚ u na procesy • znak - indikuje vykl´ad´an´ı pˇredmˇet˚ u z proces˚ u
Pˇ rechodov´ e funkce Tato ˇc´ast je povinn´a pro bˇeh programu. Ud´avaj´ı n´am pˇrechod z jednoho stavu do jin´eho stavu pomoc´ı slova z abecedy. Z´apis pˇrechodov´e funkce v souboru: ˇr´adek zaˇc´ın´a znakem d, kter´ y je n´asledov´an tabul´atorem. Pˇrechodov´e funkce v programu jsou dvoj´ıho typu: • pˇr´ım´a pˇrechodov´a funkce • pˇrechodov´a funkce s podm´ınkou Pokud z jednoho stavu m´ame v´ıce pˇrechodov´ ych funkc´ı, tak pouˇzijeme pˇrechodovou funkci s podm´ınkou, kde po splnˇen´ı nˇejak´eho poˇctu podm´ınek dostaneme spr´avnou pˇrechodovou funkci, pomoc´ı kter´e se dostaneme do v´ ysledn´eho stavu. Pˇ r´ım´ a pˇ rechodov´ a funkce Pˇr´ım´a pˇrechodov´a funkce je pˇrechodov´a funkce, kter´a je pˇresnˇe definov´ana. Funkce obsahuje tuto posloupnost: • stav, kter´eho se tato funkce t´ yk´a • slovo z abecedy, kter´e ud´av´a, jak se proces dostane do dalˇs´ıho stavu • stav, ve kter´em se proces bude nach´azet
26
Pˇ rechodov´ a funkce s podm´ınkou Pˇrechodov´a funkce s podm´ınkou je pˇrechodov´a funkce, kter´a se pouˇzije, pokud by z jednoho stavu vedlo v´ıce r˚ uzn´ ych pˇrechodov´ ych funkc´ı. Funkce obsahuje n´asleduj´ıc´ı posloupnost: • stav, kter´eho se tato funkce t´ yk´a • slovo check, kter´e ud´av´a, ˇze funkce bude volat podm´ınku • n´azev podm´ınky, kter´a se bude vykon´avat • seznam stav˚ u v [ ], oddˇelen´ ych mezerou, kter´e se pˇredaj´ı zm´ınˇen´e podm´ınce
Podm´ınky Tato ˇca´st je nepovinn´a pro bˇeh programu. Pokud ze stavu vede v´ıce pˇrechodov´ ych funkc´ı, tak n´am podm´ınky pom´ahaj´ı vybrat jednu, kterou pouˇzijeme. Z´apis podm´ınky v souboru: ˇr´adek zaˇc´ın´a slovem check, n´asledovan´ y tabul´atorem. D´ale obsahuje tuto posloupnost: • n´azev podm´ınky, pˇres kter´ y ji budeme volat ych z´avork´ach, oddˇelen´ ych ˇc´arkou, seznam parametr˚ u • v kulat´ u je pouze znak {, kter´ y n´am urˇcuje zaˇca´tek samotn´e • za seznamem parametr˚ podm´ınky • podm´ınku, kter´a m˚ uˇze obsahovat pouze promˇenn´e, ˇc´ısla, parametry, ˇretˇezce pro porovn´an´ı a symboly || (or, disjunkce), && (and, konjunkce), <, >, == • vˇetev then, kter´a se zavol´a po splnˇen´ı podm´ınky obsahuje slovo then a n´aslednˇe pˇrechodovou funkci, nebo slovo check a n´azev jin´e podm´ınky a pˇridan´e parametry • vˇetev else, kter´a jen m´ısto slova then obsahuje slovo else, je totoˇzn´a zavol´a, pokud podm´ınka nen´ı splnˇena • na samostatn´em ˇra´dku znak }, kter´ y ukonˇcuje podm´ınku.
27
5.2
Gramatika
Pˇ r´ıklad Uk´aˇzeme si pˇr´ıklad, na kter´em si demonstrujeme z´akladn´ı ˇca´sti regul´arn´ı gramatiky. Pˇredmˇety co pisek 1000 0 (vydejce,vylozen) (prijemce,nalozen) Procesy p auto 100 (vydejce,vylozen):0 10 10 30 C´ıle F (prijemce,vylozen) Informace k termin´al˚ um info + nalozit info - vylozit
d d d d d
Pravidla (vydejce,vylozen) −> nalozit (vydejce,nalozen) (vydejce,nalozen) −> jet (prijemce,nalozen) (prijemce,nalozen) −> vylozit (prijemce,vylozen) (prijemce,vylozen) −> jet (vydejce,vylozen) (prijemce,vylozen) −> $
Vlastn´ı v´ypis ˇ je aktualni.cas, proces proces.name je v aktualni.stav% %Cas Dalˇs´ı moˇznosti zaps´an´ı pravidel: d (patro1) −> in out (patro1) { predmet.in == (patro1) && proces.kapacita > 0 || (patro1) == predmet.out} | nahoru (patro2) { predmet.in > (patro2) } | dolu (patro0) d (patro1) −> check pokus [(patro1) (patro2) (patro3)] check pokus (x, y, z) { predmet.in == x && proces.kapacita > 0 || x == predmet.out then in out (x) else check nah dol [x, y, z] }
28
Vstupn´ı data Vstupn´ı data pro bˇeh gramatiky mus´ı b´ yt uloˇzen v souboru s pˇr´ıponou .txt, jin´e koncovky program neakceptuje. Vstupn´ı soubor je logicky rozdˇelen do nˇekolika ˇc´ast´ı: • Promˇenn´e • Pˇredmˇety • Procesy • Pravidla • C´ıle • Podm´ınky • Info ypis • Vlasn´ı v´ Koment´aˇre v souboru jsou pouze ˇra´dkov´e, tj. od posloupnosti znak˚ u // do konce ˇr´adku. V programu bude gramatika pˇrevedena na koneˇcn´ y automat, kter´ y bude n´aslednˇe zpracov´av´an. Termin´al je ekvivalentn´ı slovu abecedy z automatu. Netermin´al je ekvivalentn´ı stavu z automatu. Promˇenn´e, Pˇredmˇety, Procesy a Vlastn´ı v´ypis jsou ˇca´sti gramatiky totoˇzn´e s ˇc´astmi z automatu.
Pravidla Tato ˇc´ast je povinn´a pro bˇeh programu. Ud´avaj´ı n´am pˇrechod z jednoho netermin´alu do jin´eho pomoc´ı termin´alu. Z´apis pravidla v souboru: ˇr´adek zaˇc´ın´a znakem d, kter´ y je n´asledov´an tabul´atorem. D´ale m˚ uˇze nastat jedna z n´asleduj´ıc´ıch moˇznost´ı: • jednoduch´e pravidlo • pravidlo s podm´ınkou • vol´an´ı podm´ınky • c´ılov´e pravidlo
29
Jednoduch´ e pravidlo Jednoduch´e pravidlo je pravidlo, kter´e popisuje pˇrechod z jednoho netermin´alu do jin´eho. Toto pravidlo nepovoluje popis pˇrechodu z netermin´alu do netermin´alu z mnoˇziny netermin´al˚ u. Toto pravidlo obsahuje: • netermin´al, ze kter´eho je pravidlo vol´ano • soubor znak˚ u −> • termin´al, pomoc´ı kter´eho se dostaneme do c´ılov´eho netermin´alu • netermin´al, kam se pˇresuneme pomoc´ı termin´alu Pravidlo s podm´ınkou Pravidlo s podm´ınkou je pravidlo, kter´e n´am dovoluje si vybrat z v´ıce netermin´al˚ u. Toto pravidlo obsahuje: • netermin´al, ze kter´eho je pravidlo vol´ano • soubor znak˚ u −> • termin´al, pomoc´ı kter´eho se dostaneme do c´ılov´eho netermin´alu • netermin´al, kam se pˇresuneme pomoc´ı termin´alu • v { } podm´ınka pokud je tato podm´ınka splnˇena, tak pouˇzijeme termin´al a netermin´al zm´ınˇen´ y v´ yˇse pokud ne, tak p˚ ujdeme na dalˇs´ı ˇr´adek • na dalˇs´ım ˇr´adku je znak |, kter´ y slouˇz´ı pro oddˇelen´ı posloupnost´ı termin´al˚ u, netermin´al˚ u a podm´ınek • za t´ımto znakem n´asleduje termin´al a netermin´al • za netermin´alem m˚ uˇze n´asledovat dalˇs´ı podm´ınka pokud zde bude, tak pravidlo mus´ı pokraˇcovat na dalˇs´ım ˇr´adku stejnˇe jako tento pokud zde podm´ınka nebude, tak toto pravidlo konˇc´ı
30
Vol´ an´ı podm´ınky Toto pravidlo slouˇz´ı k zavol´an´ı podm´ınky. Toto pravidlo obsahuje: • netermin´al, ze kter´eho je pravidlo vol´ano • soubor znak˚ u −> • slovo check, kter´e n´am ˇr´ık´a, ˇze budeme volat podm´ınku • n´azev podm´ınky, kter´a se bude volat • v [ ] oddˇelen´ ych mezerou seznam parametr˚ u, kter´e se pˇredaj´ı podm´ınce C´ılov´ e pravidlo Toto pravidlo slouˇz´ı k zaps´an´ı netermin´alu, kter´ y slouˇz´ı jako c´ıl. Toto pravidlo obsahuje: • netermin´al, ze kter´eho je pravidlo vol´ano • soubor znak˚ u −> • znak $, kter´ y n´am ˇr´ık´a, ˇze netermin´al bude i c´ıl tento znak lze pouˇz´ıt pouze v c´ılov´em pravidle, tzn. nelze pouˇz´ıt ani v pravidle s podm´ınkou
C´ıle Tato ˇca´st gramatiky je povinn´a. Tato ˇc´ast je ekvivalentn´ı k pˇrij´ımac´ım stav˚ um z automatu. Z´apis c´ıle lze do souboru zapsat jednou z n´asleduj´ıc´ıch moˇznost´ı: • pomoc´ı syntaxe pˇrij´ımac´ıch stav˚ u z automatu F tab netermin´al • pomoc´ı c´ılov´eho pravidla
Podm´ınky Podm´ınky maj´ı stejnou funkci jako u automatu. Tvar se liˇs´ı pouze ve vˇetvi then/else. Pokud vˇetev vol´a jinou podm´ınku, tak se nic nemˇen´ı. Pokud nevol´a podm´ınku, tak je v souboru vˇetev zaps´ana takto: then/else termin´ al netermin´ al
31
Info Tato ˇca´st nen´ı povinn´a. Slouˇz´ı k nastaven´ı bliˇzˇs´ıch informac´ı k termin´al˚ um. Z´apis v souboru: ˇ adek d´ale obsahuje: ˇr´adek zaˇc´ın´a slovem info, kter´e je n´asledov´ano tabul´atorem. R´ • znak reprezentuj´ıc´ı bliˇzˇs´ı informaci • termin´al, kter´eho se informace t´ yk´a Seznam moˇzn´ ych znak˚ u: + - tento znak n´am urˇcuje, kter´e termin´aly nakl´adaj´ı pˇredmˇety na procesy - - tento znak n´am urˇcuje, kter´e termin´aly vykl´adaj´ı pˇredmˇety z proces˚ u @ - tento znak n´am urˇcuje termin´aly, kter´e se program pamatuje pro vyhodnocen´ı podm´ınek
32
5.3
Ovl´ ad´ an´ı
Spuˇ stˇ en´ı Program po spuˇstˇen´ı zobraz´ı okno se tˇremi tlaˇc´ıtky: Nov´ y - otevˇre pr´azdn´ y editor pro psan´ı automatu Otevˇ r´ıt - otevˇre v editoru vybran´ y soubor s automatem - soubor se d´a upravovat i spouˇstˇet Zavˇ r´ıt - zavˇre cel´ y program
Editor Editor n´am slouˇz´ı k u ´pravˇe automatu. Cel´e okno obsahuje textov´ y editor, kter´ y slouˇz´ı pro u ´pravu textu, checkbox, kter´ y povol´ı v´ ypis do souboru, textov´e pole pro naps´an´ı cesty k souboru a menu se dvˇemi z´aloˇzkami: • Soubor Soubor d´ale obsahuje poloˇzky Nov´ y, Otevˇr´ıt, Uloˇzit, Zavˇr´ıt • Run Run obsahuje poloˇzku Automat a Gramatika Menu - Soubor V menu Soubor jsou n´asleduj´ıc´ı poloˇzky: • Nov´ y tato poloˇzka uloˇz´ı rozpracovanou ˇc´ast v editoru a n´aslednˇe editor vypr´azdn´ı lze pouˇz´ıt i zkratku Ctrl + N. • Otevˇr´ıt tato poloˇzka uloˇz´ı rozpracovanou pr´aci (pokud nˇejak´a byla) a otevˇre dialog pro vybr´an´ı souboru s dˇr´ıve rozpracovan´ ym automatem lze pouˇz´ıt i zkratku Ctrl + O. • Uloˇzit tato poloˇzka uloˇz´ı rozpracovanou pr´aci pokud pr´ace nebyla jiˇz dˇr´ıve uloˇzena, nab´ıdne dialog pro uloˇzen´ı pr´ace z editoru lze pouˇz´ıt i zkratku Ctrl + S. • Uloˇzit jako ... tato poloˇzka vˇzdy nab´ıdne dialog pro uloˇzen´ı pr´ace z editoru • Zavˇr´ıt tato poloˇzka uloˇz´ı pr´aci a uzavˇre cel´ y program 33
Menu - Run V menu Run je n´asleduj´ıc´ı poloˇzka: • Automat tato poloˇzka uloˇz´ı rozpracovanou pr´aci a spust´ı bˇeh automatu • Gramatika tato poloˇzka spust´ı pˇrevod gramatiky na automat a spust´ı bˇeh automatu
Grafick´ e zobrazen´ı Po spuˇstˇen´ı automatu se zobraz´ı nov´a okna pro zobrazen´ı automatu a bliˇzˇs´ı informace o simulaci. V hlavn´ım oknˇe se zobraz´ı v obd´eln´ıc´ıch stavy s ˇcekaj´ıc´ımi pˇredmˇety. Zobrazuj´ı se v nich procesy s posledn´ım pouˇzit´ ym slovem z abecedy. V dalˇs´ım oknˇe se zobrazuj´ı bliˇzˇs´ı informace o procesech, jako je jeho n´aklad. V posledn´ım oknˇe se zobrazuj´ı informace z kalend´aˇre. V horn´ı ˇca´sti je aktu´aln´ı ˇcas. D´ale se zobraz´ı procesy z kalend´aˇre spolu s ˇcasem, kdy bude d´ale pracovat.
Probl´ emy Pˇri v´ yskytu chyb se zobraz´ı chyby v nov´em oknˇe a v editoru budou chyby podtrˇzen´e ˇcervenˇe. Mezi z´akladn´ı chyby, kter´e se zobraz´ı, patˇr´ı chyby v logick´ ych ˇca´stech souboru: • Promˇenn´e zde m˚ uˇze nastat chyba pˇri nedodrˇzen´ı syntaxe pomoc´ı . (teˇcky), kter´a zajiˇst’uje rozdˇelen´ı promˇenn´e na hlavn´ı ˇca´st a konkretizuj´ıc´ı ˇc´ast • Pˇredmˇet zde m˚ uˇze nastat chyba jak pˇri nedodrˇzen´ı syntaxe, tak i vloˇzen´ı neˇc´ıseln´ ych znak˚ u do ˇc´ıseln´ ych ˇc´ast´ı • Proces zde m˚ uˇze nastat chyba pˇri vloˇzen´ı neˇc´ıseln´ ych znak˚ u do ˇc´ıseln´ ych ˇca´st´ı, ale tak´e pˇri nedodrˇzen´ı syntaxe, hlavnˇe pˇri poloˇzce start, kter´a se skl´ad´a ze dvou ˇca´st´ı oddˇelen´ ych : (dvojteˇckou) • Stavy zde m˚ uˇze nastat chyba, pokud bychom pouˇzili v n´azvu stavu mezeru, kter´a nen´ı povolen´a • Pˇrij´ımac´ı stavy zde m˚ uˇze nastat stejn´a chyba jako u stav˚ u 34
• Abeceda zde u abecedy m˚ uˇze nastat chyba pˇri nedodrˇzen´ı syntaxe napˇr´ıklad mezera v n´azvu nebo pouˇzit´ı nespr´avn´eho znaku pro bliˇzˇs´ı urˇcen´ı ˇcinnosti slova abecedy • Pˇrechodov´e funkce zde m˚ uˇze nastat chyba pˇri nedodrˇzen´ı syntaxe zde ale m˚ uˇze nastat i chyba, kter´a se nezobraz´ı napˇr´ıklad pokud pˇri psan´ı parametr˚ u pouˇzijeme m´ısto mezery jin´ y oddˇelovaˇc, t´ım zmˇen´ıme n´azev a pˇri vyhodnocov´an´ı podm´ınky se n´am nebudou shodovat n´azvy a program m˚ uˇze pracovat nespr´avnˇe • Podm´ınky zde by mohl nastat probl´em pˇri nedodrˇzen´ı syntaxe
Ukonˇ cen´ı programu Pro ukonˇcen´ı programu je nutn´e uzavˇr´ıt editor. Pˇri uzavˇren´ı jen grafick´eho zobrazen´ı z˚ ustane editor st´ale otevˇren. Pˇri uzavˇren´ı editoru se rozdˇelan´a pr´ace uloˇz´ı do souboru a program se zavˇre.
35
Z´ avˇ er C´ılem bylo vytvoˇren´ı programu umoˇzn ˇuj´ıc´ıho prov´adˇet diskr´etn´ı simulace r˚ uzn´ ych jev˚ u. To se tak´e podaˇrilo. ´ Uspˇechem je, ˇze jsme za pouˇzit´ı koneˇcn´eho automatu a regul´arn´ı gramatiky vyˇreˇsili univerzalitu, protoˇze univerzalita byla hlavn´ım probl´emem programu. V´ yhodou bylo vyˇreˇsen´ı nedeterminismu koneˇcn´eho automatu, kter´e neobsahuje zanedb´an´ı nedeterminismu. Dalˇs´ım u ´spˇechem je vytvoˇren´ı jednochuch´e vizualizace, kter´a bude lehce zobrazena i na menˇs´ıch obrazovk´ach. Bohuˇzel se nepodaˇrilo vyˇreˇsit vˇsechny probl´emy spojen´e s diskr´etn´ı simulac´ı. Jedn´ım z probl´em˚ u, kter´e nejsou vyˇreˇseny jsou pˇrestupy mezi jednotliv´ ymi automaty. Takˇze nelze vyuˇz´ıt simulaci, kde pˇremˇety jsou pˇred´av´any mezi jednotliv´ ymi procesy. Toto se d´a napravit naps´an´ım diskr´etn´ı simulace, kde si pˇrestupy zaˇr´ıd´ıme jako nov´e vstupy pˇredmˇet˚ u. Dalˇs´ım probl´emem je to, ˇze program neobsahuje gener´ator pseudon´ahodn´ ych veliˇcin. Proto se mus´ı vyuˇz´ıt jin´eho programu, kter´ y n´am tyto pseudon´ahodn´e veliˇciny vygeneruje. Dalˇ s´ı moˇ zn´ a rozˇ s´ıˇ ren´ı. Bohuˇzel jeˇstˇe zb´ yvaj´ı ˇca´st´ı, kter´e se nestihly naimplementovat. Mezi tyto ˇc´asti patˇr´ı v´ yˇse zm´ınˇen´e probl´emy. D´ale bychom mohli v programu vytv´aˇret statistiky. Program totiˇz prov´ad´ı pouze v´ ypis. Na vytvoˇren´ı statistiky mus´ıme v´ ypisy pˇredat do jin´eho programu, kter´ y n´am statistiku n´aslednˇe vytvoˇr´ı. Nakonec bychom mohli bˇehem pr˚ ubˇehu diskr´etn´ı simulace upravovat jednotliv´e ˇca´sti koneˇcn´eho automatu nebo regul´arn´ı gramatiky.
36
Seznam pouˇ zit´ e literatury ˇivy ´ , I, Kindler, E. Simulace a modelov´ [1] Kr an´ı. Ostrava: Ostravsk´a univerzita, 2001. [2] Kindler, E. Simulaˇcn´ı programovac´ı jazyky. Praha: SNTL, 1980. [3] Pidd, M. Computer simulation in management science. Velk´a Brit´anie: John Wiley, 1992. ISBN 0-471-93462-3. ˇ ic ˇka, P. Simulaˇcn´ı metody jako n´astroj pro rozhodov´ [4] Koc an´ı podniku - modelov´an´ı pomoc´ı programu Witness. Brno: Masarykova univerzita, 2009. [5] Mal´ık, M. Poˇc´ıtaˇcov´a simulace. Skripta MFF UK. Praha: UK Praha, 1989 ISBN 0-201-85449-X ¨ u ¨ n, O., Barlas, Y. Discrete vs. Continuous Simulation: When Does It [6] Ozg Matter? (on-line) Istanbul: Bo˘gazi¸ci University, 2009 [7] Park, S., Leemis, L. Discrete-Event Simulation: A First Course (on-line) College of William and Mary ˇar, P. Teoretick´a informatika: uˇcebn´ı text (on-line). 1. vyd´an´ı. Ostrava: [8] Janc ˇ Ediˇcn´ı stˇredisko VSB-TUO, 2007 ISBN 978-80-248-1487-2. ´ [9] Kocour, P. Uvod do teorie koneˇcn´ych automat˚ u a form´aln´ıch jazyk˚ u. 1. vyd´an´ı. Plzeˇ n: Z´apadoˇcesk´a univerzita v Plzni, 2001. ISBN 80-7082-813-7. ˇ Teorie jazyk˚ ˇkova ´ , S. [10] Vavrec u a automat˚ u: studijn´ı texty (on-line). Opava: Slezsk´a univerzita v Opavˇe, 2007. ´ k, R. Automaty a gramatiky: studijn´ı texty (on-line). Praha: UK Pra[11] Barta ha, 2012. ˇ ´ , I., Kr ˇet´ınska ´, M., Kuc ˇera, A. Automaty a form´aln´ı jazyky I. [12] Cern a (on-line). Verze 1.3 Brno: Masarykova univerzita, 2002 [13] Hopcroft, J. E., Ullman, J. D. Form´ alne jazyky a automaty. Pˇrel. B. Rovan, P. Mikuleck´ y. 1. vyd´an´ı Bratislava: Alfa, 1978 Pˇrel. z: Formal languages and their relation to automata. ISBN 63-096-78 [14] Internetov´e podp˚ urn´e prostˇred´ı k pˇredmˇetu Teoretick´ a informatika Univerzita Hradec Kr´alov´e: Fakulta informatiky a managementu. URL: http://iris.uhk.cz/tein [15] MacDonald, M. Pro WPF in C# 2010: Windows Presentation Foundation in .NET 4.0 USA: Apress, 2010 ISBN 978-1-4302-7205-2 [16] Richter, J. CLR via C# 3. vyd´an´ı Washington: Microsoft Press, 2010 ISBN 978-0735627048
37
Seznam tabulek 2.1 Pˇrechodovou funkci reprezentujeme v´ yˇctem vˇsech pˇrechod˚ u. . . . 2.2 Koneˇcn´ y automat reprezentovan´ y tabulkou. . . . . . . . . . . . .
38
7 8
Pˇ r´ılohy Pˇ r´ıloha A: Obsah pˇ riloˇ zen´ eho CD Obsah pˇriloˇzen´eho CD. • Tato bakal´aˇrsk´a pr´ace v elektronick´e formˇe. • Instalaˇcn´ı soubor pro instalaci programu Univerz´ aln´ ı diskr´ etn´ ı simul´ ator. Soubor se nach´az´ı v adres´aˇri Instalace. • Dokumentace programu v adres´aˇri Dokumentace. • Zdrojov´e k´ody v adres´aˇri Zdrojov´ e k´ ody. • Testovac´ı data v adres´aˇri Test.
39