Univerzita Karlova v Praze Matematicko-fyzikální fakulta

Univerzita Karlova v Praze Matematicko-fyzikáln´ı fakulta

´ RSK ˇ ´ PRACE ´ BAKALA A

Jiˇr´ı Vytasil Univerz´ aln´ı diskr´ etn´ı simul´ ator Kabinet software a v´ yuky informatiky

Vedouc´ı bakaláˇrské práce: RNDr. Martin Pergel, Ph.D. Studijn´ı program: Informatika Studijn´ı obor: Správa poˇc´ıtaˇcov´ ych systém˚ u

Praha 2012

Rád bych podˇekoval mému vedouc´ımu bakaláˇrské práce, panu RNDr. Martinovi Pergelovi, Ph.D., za ochotu, cenné rady a vstˇr´ıcnost, které mi projevoval v pr˚ ubˇehu psan´ı programu a této práce. Dále bych rád podˇekoval sv´ ym koleg˚ um, se kter´ ymi jsem mohl konzultovat technologie a postupy. Nakonec bych rád podˇekoval své rodinˇe za jejich podporu.

Prohlaˇsuji, ˇze jsem tuto bakaláˇrskou práci 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áci vztahuj´ı práva a povinnosti vypl´ yvaj´ıc´ı ze zákona ˇc. 121/2000 Sb., autorského zákona v platném znˇen´ı, zejména skuteˇcnost, ˇze Univerzita Karlova v Praze má právo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı této práce jako ˇskoln´ıho d´ıla podle §60 odst. 1 autorského zákona.

V Praze dne 31. 7. 2012

Podpis autora

Název práce: Univerzáln´ı diskrétn´ı simulátor Autor: Jiˇr´ı Vytasil Katedra: Kabinet software a v´ yuky informatiky Vedouc´ı bakaláˇrské práce: RNDr. Martin Pergel, Ph.D., Kabinet software a v´ yuky informatiky Abstrakt: V této práce je rozebrán návrh a implementace programu umoˇzn ˇuj´ıc´ıho provádˇet diskrétn´ı simulace. Dále je v programu implementována vizualizace pr˚ ubˇehu diskrétn´ı simulace. D˚ uraz je kladen pˇredevˇs´ım na univerzalitu. Kromˇe programu a jeho popisu jsou zde informace o diskrétn´ı simulaci, které umoˇzn´ı jednoduˇsˇs´ı pochopen´ı ˇcinnosti programu. Pro popis diskrétn´ı simulace pouˇz´ıváme koneˇcné automaty a regulárn´ı gramatiky. Zm´ınˇené ˇca´sti zde v´ıce popisujeme, abychom jednoduˇseji pochopili popis diskrétn´ı simulace. Systém dále umoˇzn ˇuje u ´pravu vstupn´ıch soubor˚ u pro jednoduˇsˇs´ı práci programu. Kl´ıˇcová slova: diskrétn´ı simulace, koneˇcn´ y automat, regulárn´ı 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ém, model, modelován´ı . . . . . . 1.2 Definice simulace . . . . . . . . . . . . 1.3 Spojitá simulace . . . . . . . . . . . . . 1.4 Diskrétn´ı simulace . . . . . . . . . . . 1.4.1 Komponenty diskrétn´ı 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árn´ı 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áklad 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ádán´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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árn´ı gramatika . . . . 4.4 Vizualizace . . . . . . . . .

. . . .

. . . .

1

. . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

. . . . .

. . . . . . . .

. . . .

´ Uvod C´ılem bakaláˇrské práce je vytvoˇren´ı programu umoˇzn ˇuj´ıc´ıho provádˇet diskrétn´ı simulace r˚ uzn´ ych jev˚ u. Pˇredmˇetem bakaláˇrské práce je také jazyk, kter´ y popisuje jednotlivé u ´ˇcastn´ıky diskrétn´ı simulace, a vhodná vizualizace diskrétn´ı simulace. Zvolili jsme si toto téma, protoˇze jsme chtˇeli vytvoˇrit srozumiteln´ y program pro diskrétn´ı simulace. V programu je kladen d˚ uraz pˇredevˇs´ım na univerzalitu. Univerzalitu jsme zaruˇcili pˇri pouˇzit´ı koneˇcného automatu a regulárn´ı gramatiky jako základ jazyka. V´ıce o univerzalitˇe v 3.2.1. Vyuˇzit´ım koneˇcného automatu a regulárn´ı gramatiky jsme pouˇzili jiˇz známé prostˇredky, takˇze je popis diskrétn´ı simulace jednoduˇsˇs´ı na pochopen´ı. Vytvoˇrili jsme program, kter´ y se dá vyuˇz´ıt pro vizualizaci diskrétn´ı simulace. Dá se ale také vyuˇz´ıt pouze jej´ı ˇca´st reprezentuj´ıc´ı práci diskrétn´ı simulace, která se dá zavolat i z jiné aplikace.

2

1. Simulace 1.1

Syst´ em, model, modelov´ an´ı

Syst´ em Systém je abstraktn´ı objekt, kter´ y byl vytvoˇren systémov´ ym pˇr´ıstupem. [4] Definice systému od L. von Bertalanffyho: Systém je komplex prvk˚ u nacházej´ıc´ıch se ve vzájemné interakci. V této definici jsou zachyceny dvˇe základn´ı vlastnosti kaˇzdého systému. Tˇemi jsou jeho struktura a chován´ı. Struktura systému ja dána elementárn´ımi prvky a vazbami mezi nimi. Pokud je systém tvoˇren r˚ uzn´ ymi prvky, mluv´ıme o strukturovaném systému. Jednotlivé prvky jsou pak nestrukturované systémy. Kaˇzd´ y prvek má obvykle ˇradu vlastnost´ı, oznaˇcovan´ ych jako atribut prvku. Chován´ı systému je forma závislosti v´ ystupu systému na vstupech.

Model Term´ın model je pouˇzit pro analogii mezi dvˇema systémy. Prvn´ı systém, kter´ y odpov´ıdá zkoumanému objektu, je modelovaný systém. Druh´ y systém, kter´ y definujeme, je modeluj´ıc´ı systém. [1, 4] Vztah obou systém˚ u je dán t´ım, ˇze kaˇzdému prvku P modelovaného ststému je pˇriˇrazen prvek Q modeluj´ıc´ıho systému. Kaˇzdému atributu g prvku P je pˇriˇrazen atribut h prvku Q a pro hodnoty atribut˚ u g a h je dána nˇejaká relace. [1, 4]

Modelov´ an´ı Vytváˇren´ı analogie mezi modely se naz´ yvá modelován´ı. Modelovan´ y systém b´ yvá oznaˇcován jako originál a m´ısto pojmu modeluj´ıc´ı systém se pouˇz´ıvá term´ın model. [4]

1.2

Definice simulace

Dahl: Simulace je v´ yzkumná technika, jej´ıˇz podstatou podstata spoˇc´ıvá v tom, ˇze zkouman´ y dynamick´ y systém nahrad´ıme jeho simulátorem (modelem) a s n´ım provád´ıme pokusy (experimenty) s c´ılem z´ıskat informaci o p˚ uvodn´ım zkoumaném systému. Shannon: Simulace je proces tvorby modelu reálného systému a provádˇen´ı experiment˚ u s t´ımto modelem za u ´ˇcelem dosaˇzen´ı lepˇs´ıho pochopen´ı chován´ı studovaného systému ˇci za u ´ˇcelem posouzen´ı r˚ uzn´ ych variant ˇcinnosti systému. 3

Naylor: Simulace je numerická metoda, která spoˇc´ıvá v experimentován´ı s matematick´ ymi modely reáln´ ych systém˚ u na ˇc´ıslicov´ ych poˇc´ıtaˇc´ıch. Cendel´ın: Simulace je technika pro v´ yzkum dynamick´ ych systém˚ u, jej´ıˇz podstata spoˇc´ıvá v tom, ˇze zkouman´ y systém nahrad´ıme jeho simulaˇcn´ım modelem a s t´ımto modelem provád´ıme experimenty proto, abychom z´ıskali informace o p˚ uvodn´ım zkoumaném systému. Originál (zkouman´ y systém) se v simulaci naz´ yvá simulovaný systém a simulaˇcn´ı model se naz´ yvá simuluj´ıc´ı systém nebo také simul´ ator.

1.3

Spojit´ a simulace

Spojitá simulace je zaloˇzena na zmˇenách rovnomˇernˇe vzdálen´ ych v ˇcase. Nejsou zde privilegované okamˇziky. Na simulaci nahl´ıˇz´ıme v pravideln´ ych intervalech, at’ uˇz se dˇeje nˇeco zaj´ımevého, ˇci nikoliv.

1.4

Diskr´ etn´ı simulace

V diskrétn´ı simulaci se zmˇeny dˇej´ı nespojitˇe v ˇcase. Model, nad kter´ ym diskrétn´ı simulac prob´ıhá, pak obsahuje chronologicky navazuj´ıc´ı dˇeje.

Procesy Proces je posloupnost logicky na sebe navazuj´ıc´ıch událost´ı. Stavy proces˚ u V souvislosti s plánován´ım proces˚ u rozliˇsujeme ˇctyˇri stavy proces˚ u [1]: 1. Stav aktivn´ı. Proces je právˇe provádˇen, tj. je právˇe realizován v´ ypoˇcet odpov´ıdaj´ıc´ı nˇekteré jeho události. V aktivn´ım stavu m˚ uˇze b´ yt v daném 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án, ani naplánován k provádˇen´ı. 3. Stav pˇ ripraven´ y neboli suspendovan´ y. Proces je naplánován k provádˇen´ı v nˇejakém konkrén´ım okamˇziku simulárn´ıho ˇcasu. 4. Stav pasivn´ı. Proces nen´ı ukonˇcen´ y, ale nen´ı ani naplánován k provádˇen´ı. K jeho vyvolán´ı m˚ uˇze doj´ıt tehdy, bude-li naplánován prostˇrednictv´ım nˇejakého jiného procesu. Jak´ ykoliv vytvoˇren´ y proces se v kaˇzdém okamˇziku vyskytuje právˇe v jednom z uveden´ ych stav˚ u. 4

1.4.1

Komponenty diskr´ etn´ı simulace

Mezi komponenty diskrétn´ı simulace patˇr´ı: ˇcas, kalendáˇr událost´ı, generátor náhodn´ ych ˇc´ısel, statistiky a koneˇcné podm´ınky. Pˇredstavme si ˇcasovou pˇr´ımku pro ˇcas, kter´ y ub´ıhá uvnitˇr simulace. Na této pˇr´ımce máme spoustu bod˚ u odpov´ıdaj´ıc´ıch událostem. Uvnitˇr simulace potˇrebujeme tyto události proj´ıt a zpracovat v poˇrad´ı, jak leˇz´ı na pˇr´ımce. Pˇred spuˇstˇen´ım simulace jsme naplánovali nˇekolik událost´ı. Dalˇs´ı vznikly jako d˚ usledek pˇredeˇsl´ ych událost´ı. Kalendáˇr událost´ı je ˇr´ıd´ıc´ı struktura simulaˇcn´ıho programu, která zahrnuje pˇredevˇs´ım programové prostˇredky pro plánován´ı událost´ı. Posloupnost událost´ı v simulaˇcn´ım modelu nen´ı pˇrirozenˇe dána pˇredem. Proto je základn´ım u ´kolem simulaˇcn´ıho programu tuto posloupnost vytváˇret a pr˚ ubˇeˇznˇe aktualizovat. A je to právˇe kalendáˇr událost´ı, jenˇz mus´ı plnˇen´ı tohoto u ´kolu zajiˇst’ovat. [1] Z´ akladn´ı funkce kalend´ aˇ re ud´ alost´ı Vyˇzadujeme, aby kalendáˇr zabezpeˇcoval ˇctyˇri základn´ı funkce [5]: 1. zjistit, zda je daná událost naplánována ˇci nikoliv, a v pˇr´ıpadˇe, ˇze naplánována je, zjistit hodnotou jej´ıho aktivn´ıho ˇcasu 2. vybrat proces s minimáln´ı 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ánovat momentálnˇe nenaplánovanou událost (proces) 4. zruˇsit plán momentálnˇe naplánované události (procesu) Simulace potˇrebuje generovat pseudonáhodné veliˇciny, které závis´ı na modelu. Toto je splnˇeno jedn´ım, nebo v´ıce pseudonáhodnými generátory. Pseudonáhodná ˇc´ısla se vyuˇz´ıvaj´ı k napodoben´ı reáln´ ych podm´ınek. Program neimplementuje pseudonáhodn´ y generátor. V´ ystupem simulace jsou statistická data z´ıskaná pˇri simulaci, která mus´ıme dále zpracovat, abychom z´ıskali v´ ysledné informace. Program negeneruje statistiky. Pro simulaci je d˚ uleˇzité, aby mohla nˇekdy skonˇcit. Proto je nutné zavést koncové podm´ınky, kdy simulace skonˇc´ı. Napˇr. v ˇcase t nebo po proveden´ı n událost´ı.

5

2. Koneˇ cn´ y automat a gramatika 2.1

Koneˇ cn´ y automat

Definice • Abeceda je libovolná koneˇcná neprázdná mnoˇzina prvk˚ u oznaˇcovaná p´ısmenem Σ. Prvky abecedy se naz´ yvaj´ı symboly nebo téˇz znaky abecedy. [12] u dané abecedy Σ. Posloup• Slovo v je libovolná koneˇcná posloupnost symbol˚ nost a1 , a2 , ..., an , kde ai (pro i = 1, 2, ..., n) ∈ Σ, je moˇzno zapsat zkrácenˇ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ázdn´ ych slov v abecedˇe Σ. • Σ∗ = Σ+ ∪ {λ} • Délka slova je poˇcet znak˚ u, které slovo tvoˇr´ı. y symbol a znaˇc´ı se znakem ε. • Prázdné slovo neobsahuje ˇza´dn´ • Prefix oznaˇcuje zaˇca´tek slova, sufix konec slova. • Podslovo je pak jakákoliv ˇca´st slova. • Prázdné 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áln´ı 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á jazyk obsahuje.

6

Deterministick´ y a nedeterministick´ y koneˇ cn´ y automat Definice. Deterministický koneˇcný automat je definován jako uspoˇr´ adan´ a pˇetice (Q, Σ, δ, q0 , F ), kde [11] : • Q je koneˇcná neprázdn´ a mnoˇzina stav˚ u. • Σ je koneˇcná neprázdn´ a mnoˇzina vstupn´ıch symbol˚ u, tzv. vstupn´ı abeceda. • δ je pˇrechodová funkce, δ : Q × Σ → Q. • q0 je poˇcáteˇcn´ı neboli iniciáln´ı stav, q0 ∈ Q. • F je mnoˇzina koncových neboli pˇrij´ımac´ıch stav˚ u, F ⊆ Q. Definice. Nedeterministický koneˇcný automat je definován jako uspoˇr´ adan´ a pˇetice (Q, Σ, δ, S, F ), kde [11] : • Q je koneˇcná neprázdn´ a mnoˇzina stav˚ u. a mnoˇzina vstupn´ıch symbol˚ u, tzv. vstupn´ı abeceda. • Σ je koneˇcná neprázdn´ • δ je pˇrechodová funkce, δ : Q × Σ → P (Q). • S je mnoˇzina poˇcáteˇcn´ıch (iniciáln´ıch) stav˚ u, S ⊆ Q. u, F ⊆ Q. • F je mnoˇzina koncových neboli pˇrij´ımac´ıch stav˚

Reprezentace koneˇ cn´ eho automatu Existuje nˇekolik reprezentac´ı koneˇcného automatu. Zde uvedeme 4 zp˚ usoby, které jsou popsány v [8, 9, 10, 11]. V´ yˇ cet prvk˚ u Kaˇzd´ y mnoˇzinov´ y ˇclen dané pˇetice je urˇcen v´ yˇctem prvk˚ u, které obsahuje. U pˇrechodové 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á funkce vypadá: 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áhlav´ı sloupc˚ u tvoˇr´ı symboly vstupn´ı abecedy a záhlav´ı ˇra´dk˚ u stavy automatu. Oznaˇcen´ı stav˚ u: • Poˇcáteˇcn´ı stavy symbolem →. • Pˇrij´ımac´ı stavy symbolem ←. • Stavy, které 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ázek 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ého vrcholu, kter´ y nen´ı listem, vycház´ı právˇe tolik hran, kolik má pˇr´ısluˇsn´ y stav následn´ık˚ u. Pokud nˇejak´ y stav odpov´ıdá v´ıce vrchol˚ um, pak hrany vycházj´ı jen z jednoho z nich. Poˇca´teˇcn´ım stavem je koˇren stavového stromu. Pˇrij´ımac´ı stavy jsou oznaˇceny bud’ dvojit´ ym kruhem, nebo → vedouc´ı z vrcholu. Pˇr´ıklad: Obrázek 2.2. 8

Obrázek 2.1: Stavov´ y diagram

Obrázek 2.2: Stavov´ y strom

9

2.2

Gramatika

Regul´ arn´ı gramatika Formáln´ı gramatikou naz´ yváme ˇctveˇrici (VN , VT , S, P ) [13] : • VN je koneˇcná mnoˇzina netermináln´ıch symbol˚ u • VT je koneˇcná mnoˇzina termináln´ıch symbol˚ u • S ∈ VN je poˇcáteˇcn´ı netermináln´ı symbol • P je koneˇcná mnoˇzina pˇrepisovac´ıch pravidel Mnoˇziny VN a VT jsou disjunktn´ı, tj. VN ∩ VT = ∅. V je tzv. celková abeceda, tj. V = VN ∪ VT . Regulárn´ı gramatika dovoluje pouze pravidla ve tvaru X → wY, X → w, kde X, Y ∈ VN , w ∈ VT∗ .

Pˇ repisovac´ı syst´ emy Pˇrepisovac´ım systémem naz´ yváme dvojici R = (V, P ), kde [11] • V je koneˇcná abeceda • P je koneˇcná mnoˇzina pˇrepisovac´ıch pravidel Pˇrepisovac´ı pravodlo je uspoˇrádaná dvojice slov (α, β), kde α je slovo, které obsahuje alespoˇ n jeden netermináln´ı 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áme, ˇ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áme, ˇ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áme odvozen´ım.

Jazyk Definice. Jazyk generovaný 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ádá pouze z termináln´ı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é regulárn´ı gramatice G = (VN , VT , S, P ) existuje koneˇcný automat A = (Q, Σ, δ, q0 , F ) takový, ˇze L(A) = L(G). D˚ ukaz. [11] L(G) je nˇejaká regulárn´ı 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étn´ı simulace, nab´ız´ı se objektovˇe orientované jazyky jako Java, C++, C#. Dále je c´ılem kromˇe jazyka i vizualizace simulace. U C++ je designován´ı tˇeˇzkopádnˇ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éto sekci se budeme zab´ yvat hlavn´ımi rozhodovac´ımi konflikty, které bylo potˇreba rozˇreˇsit.

3.2.1

Z´ aklad jazyka

Velmi d˚ uleˇzitou otázkou tohoto programu je univerzálnost. Otázkou tedy je, co pouˇz´ıt jako jazyk, aby byla univerzálnost zachována. 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é kategorie bych zaˇradil jazyky, u kter´ ych jako základ vyuˇzijeme jiˇz známé prostˇredky. U prvn´ı kategorie mezi hlavn´ı d˚ uvody m˚ uˇzeme zaˇradit jednoduˇsˇs´ı programován´ı, jelikoˇz si m˚ uˇzeme vytvoˇrit jazyk, kter´ y bude vyhovovat nám jako programátor˚ um. Oproti tomu v druhé kategorii, pokud si vybereme dobˇre, nám odpadne ˇreˇsen´ı univerzálnosti. Mezi dalˇs´ı v´ yhody se dá zaˇradit jednoduˇsˇs´ı rozˇsiˇritelnost, protoˇze si jako základ vybereme jiˇz známé prostˇredky, takˇze nˇekteˇr´ı uˇzivatelé 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ázkou je, co pouˇz´ıt jako základ jazyka. Jako základ jsme uvaˇzovali o automatu, gramatice, nebo vyuˇzit´ı nˇekterého 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ého programovac´ıho jazyka. Jelikoˇz automat a gramatika jsou vzájemnˇe na sebe pˇrevoditelné, 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áme pro simulaci, ale jen ji pˇrevedeme na automat.

12

3.2.2

Automat

Automat˚ u existuje nˇekolik druh˚ u. Koneˇcné automaty, zásobn´ıkové automaty, y pouˇzijeme. lineárnˇe omezené automaty a Turingovy stroje. [11] Otázkou je, kter´ Doporuˇcuje se, pokud je to moˇzné, pouˇzit´ı jednoduˇsˇs´ıho automatu. Nejjednoduˇsˇs´ım automatem je koneˇcn´ y automat. Pod´ıváme se, zda nám koneˇcn´ y automat bude staˇcit. Pˇrechodová funkce u automatu nám pom˚ uˇze reprezentovat práci diskrétn´ı simulace. Slova abecedy nám mohou reprezentovat ˇcinnosti diskrétn´ı simulace. Toto jsou pro nás d˚ uleˇzité ˇca´sti, které nám koneˇcn´ y automat ˇreˇs´ı. Dalˇs´ı ˇcásti, kter´ ymi jsou pˇredmˇety a procesy, simulace budeme definovat mimo koneˇcn´ y automat. Toto je jedna z ˇca´st´ı, která nám dává odliˇsnosti od koneˇcného automatu.

3.2.3

Nedeterminismus automatu

Koneˇcn´ y automat m˚ uˇze b´ yt deterministick´ y, ale i nedeterministick´ y. Otázkou tedy je, jak se s nedeterminismem vypoˇrádat. Jedn´ım ˇreˇsen´ım by mohlo b´ yt nedeterminismus zakázat, 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ého bychom v simulaci ˇreˇsili vˇsechny moˇzné 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é z toho d˚ uvodu, abychom mohli správnˇe uˇzivateli signalizovat pˇrechod z jednoho stavu do jiného. Nakonec jsme se rozhodli pro následuj´ıc´ı ˇreˇsen´ı nedeterminismu. Pˇri nedeterminismu se zavolá 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án´ı.

3.2.4

V´ıce pˇ rechodov´ ych funkc´ı

Jelikoˇz zde nemáme pˇredem danou sekvenci znak˚ u z abecedy, u které chceme zjistit, zda je pˇrij´ımána naˇs´ım automatem, tak mus´ıme ˇreˇsit i problém v´ıce pˇrechodov´ ych funkc´ı vedouc´ı z jednoho stavu. Tohoto problému se zbav´ıme stejnˇe jako problému s nedeterminismem. Opˇet pouˇzijeme podm´ınky, kde to m˚ uˇzeme lépe specifikovat.

13

3.2.5

Gramatika

Jako druhou ˇcást zadáván´ı diskrétn´ı simulace jsme si zvolili gramatiku. Tˇech je také nˇekolik druh˚ u, regulárn´ı, bezkontextová, kontextová a typu 0. [11] Otázkou tedy je, jakou si vybereme. Jelikoˇz v naˇsem programu budeme gramatiku pˇrevádˇet na koneˇcn´ y automat, logicky se nab´ız´ı regulárn´ı gramatika. U regulárn´ı gramatiky pouˇzijeme pouze pravidla typu: • X → aY a terminál X, Y neterminál • X→λ zde v programu λ nahrazena $ X neterminál

3.2.6

Vizualizace

Souˇca´st´ı programu je i vizualizace diskrétn´ı simulace. Otázkou tedy je, jak vizualizovat informace z diskrétn´ı simulace. Jako jedna z variant se nab´ızela moˇznost zobrazen´ı stav˚ u s informacemi o pˇredmˇetech, které se zde vyskytuj´ı. Dále jinak zobrazit procesy s bliˇzˇs´ımi informacemi, které pˇrecház´ı z jednoho stavu do jiného. Toto zobrazen´ı je sice nejjednoduˇsˇs´ı na ˇcten´ı pr˚ ubˇehu diskrétn´ı simulace, ale pˇri zobrazen´ı na menˇs´ıch obrazovkách by mohl nastat problém 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áˇst’. T´ımto zp˚ usobem sn´ıˇz´ıme velikost stav˚ u. Ve stavech zobraz´ıme informace o pˇredmˇetech, které se zde vyskytuj´ı, a název 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ále zobraz´ıme informace o kalendáˇri událost´ı, abychom mˇeli lepˇs´ı pˇredstavu o nadcházej´ıc´ıch událostech. Pro tento zp˚ usob zobrazen´ı jsme se rozhodli z d˚ uvod˚ u, ˇze je celkem jednoduché z nˇej vyˇc´ıst pr˚ ubˇeh diskrétn´ı simulace a i zobrazen´ı vˇetˇs´ıho mnoˇzstv´ı stav˚ u nen´ı velk´ y problém.

14

4. Implementace 4.1

Popis jednotliv´ ych souˇ c´ ast´ı

Celkov´ y program obsahuje nˇekolik souˇcást´ı pokr´ yvaj´ıc´ıch jednotlivé ˇca´sti. Jsou jimi: • Automat • Gramatika • Vizualizace

Obrázek 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áci, tak i naˇcten´ı. V´ıce se dozv´ıme v kapitole 4.2. Projekt Gramatika je knihovna reprezentuj´ıc´ı regulárn´ı 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á o zobrazen´ı diskrétn´ı 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é hlavn´ı tˇr´ıdy a co reprezentuj´ı v rámci koneˇcného automatu. Mezi hlavn´ı tˇr´ıdy patˇr´ı tˇr´ıdy reprezentuj´ıc´ı jednotlivé ˇcásti koneˇcného automatu. Jednou z nich je tˇr´ıda stav, která reprezentuje jednotlivé stavy koneˇcného automatu. Dále tu je tˇr´ıda abeceda, která reprezentuje jednotlivá slova abecedy. Tˇr´ıda predmet reprezentuje pˇredmˇety automatu, které maj´ı procesy pˇrem´ıstit z jednoho stavu do jiného. Tˇr´ıda proces reprezentuje jednotlivé procesy koneˇcného automatu. Tyto procesy pˇredstavuj´ı konatele ˇcinnost´ı. Tˇr´ıda prechodova funkce reprezentuje pˇrechodové funkce koneˇcného automatu. Dále m˚ uˇze obsahovat název podm´ınky, která je potˇrebná pro správné rozhodnut´ı. Tˇr´ıda podminka reprezentuje podm´ınky, které jsou potˇrebné pro správné zvolen´ı pˇrechodové funkce. Tˇr´ıda kalendar reprezentuje kalendáˇr událost´ı. Jednotlivé události jsou instancemi tˇr´ıdy Ud´ alost. Tˇr´ıda Automat obsahuje datové struktury pro ukládán´ı zm´ınˇen´ ych tˇr´ıd. Dále provád´ı pˇrechod z jednoho stavu do jiného.

Pr´ ace automatu Tˇr´ıda Automat reprezentuje koneˇcn´ y automat a provád´ı jednotlivé kroky diskrétn´ı simulace. Obsahuje datové struktury reprezentuj´ıc´ı napˇr. abecedu, pˇrechodové funkce, atd. Provád´ı pˇrechody z jednoho stavu do jiného a pˇri volán´ı podm´ınky provád´ı jej´ı vyhodnocen´ı. Dále pˇrevád´ı gramatiku na koneˇcn´ y automat. Tato tˇr´ıda je rozdˇelena do ˇctyˇr soubor˚ u. Jeden soubor se zab´ yvá pˇreveden´ım regulárn´ı gramatiky na koneˇcn´ y automat. Pˇrevod provád´ı z pˇredpˇripravené regulárn´ı gramatiky. K pˇrevodu pouˇz´ıvá metody, které z jednotliv´ ych ˇca´st´ı regulárn´ı gramatiky vytvoˇr´ı postupnˇe jednotlivé ˇcásti koneˇcného automatu (napˇr. neterminály pˇrevede na stavy). Název souboru je Automat gramatika. Dalˇs´ı soubor se zab´ yvá vyhodnocen´ım podm´ınky. Tento soubor je urˇcen pro vyhodnocen´ı volané podm´ınky a urˇcen´ı správné pˇrechodové funkce. K tomu je také urˇcen seznam jiˇz volan´ ych podm´ınek, abychom se nezacyklili. Pˇri vyhodnocován´ı podm´ınek vytváˇr´ıme pˇrevodn´ı tabulku, která slouˇz´ı pro pˇrevod pseudoparametr˚ u na parametry reálné. Název souboru je Automat vyhodnoceni podminky.

16

V dalˇs´ım souboru ˇreˇs´ıme pˇrechod z jednoho stavu do jiného. K tomu vyuˇz´ıváme také soubor urˇcen´ y k vyhodnocován´ı podm´ınek. Zde zjist´ıme aktuáln´ı událost a z této události dostaneme informace o procesu, stavu. Z tˇechto informac´ı urˇc´ıme pˇrechodovou funkci a slovo z abecedy. Pokud se nám nepodaˇr´ı jednoznaˇcnˇe urˇcit pˇrechodovou funkci, zjist´ıme si z n´ı název podm´ınky, která ji urˇc´ı, a necháme ji vyˇreˇsit v souboru, kter´ y se zab´ yvá vyhodnocován´ım podm´ınek. U slova z abecedy se pod´ıváme, zda nakládá pˇredmˇety na procesy nebo vykládá pˇredmˇety z proces˚ u. Pokud ano, zavolaj´ı se metody pro nakládán´ı ˇci vykládán´ı. Dále pokud máme definován v´ ystup do souboru, provedeme v tomto souboru i tuto ˇcinnost. Název souboru je Automat zpracovani. Posledn´ı soubor obsahuje datové struktury, které reprezentuj´ı vˇsechny d˚ uleˇzité ˇcásti automatu, jako napˇr. pˇredmˇety, procesy, slova abecedy, pˇrechodové funkce, podm´ınky, stavy, chyby. V tomto souboru jsou také metody viditelné zvenˇc´ı, které slouˇz´ı napˇr. pro vytvoˇren´ı instance této tˇr´ıdy, ˇci pro provádˇen´ı diskrétn´ı simulace. Zde si následnˇe vytváˇr´ıme iniciáln´ı události, kde se jednotlivé procesu budou nacházet. A provád´ıme si tu kontrolu, aby koneˇcn´ y automat obsahoval vˇsechny d˚ uleˇzité ˇcásti. Název souboru je Automat inicializace.

Slova z abecedy Tˇr´ıda abeceda je urˇcená pro reprezentaci slov z abecedy. Slovo urˇcuje ˇcinnost simulace. Zde si pamatujeme název slova z abecedy, resp. ˇcinnosti simulace, ˇc´ıslo ˇrádku vyuˇz´ıvané pˇri nalezen´ı chyby a hodnoty indikuj´ıc´ı, zda je moˇzné u této ˇcinnosti nakládán´ı pˇredmˇet˚ u, vykládán´ı pˇredmˇet˚ u, nebo si tuto ˇcinnost budeme pamatovat pro vyhodnocován´ı podm´ınek.

Kalend´ aˇ r ud´ alost´ı Tˇr´ıda kalendar reprezentuje jednotlivé události. Zde si pamatujeme nejbliˇzˇs´ı události pro kaˇzd´ y proces. Jednotlivé události jsou instanc´ı tˇr´ıdy Ud´ alost. Tato tˇr´ıda slouˇz´ı pro vytváˇren´ı nov´ ych událost´ı a odstraˇ nován´ı jiˇz probˇehl´ ych událost´ı.

Podm´ınky pro spr´ avn´ e vyhodnocov´ an´ı Tˇr´ıda podminka je urˇcená pro reprezentaci podm´ınek. Podm´ınky slouˇz´ı pro vybrán´ı správné pˇrechodové funkce. Zde si pamatujeme název podm´ınky, seznam pseudoparametr˚ u, za které pˇri volán´ı dosad´ıme reálné. Dále je tu v´ yraz pro vyhodnocen´ı, kter´ y vrac´ı true, nebo false. Nakonec tu jsou vˇetve then a else a ˇc´ısla ˇrádk˚ u, na kter´ ych podm´ınka zaˇc´ıná a konˇc´ı v souboru. Pro vˇetev then a else pouˇz´ıváme abstraktv´ı tˇr´ıdu, kam ukládáme bud’ vˇetev reprezentuj´ıc´ı pˇrechodovou funkci, nebo vˇetev reprezentuj´ıc´ı volán´ı dalˇs´ı podm´ınku.

17

Pˇ redmˇ ety Tˇr´ıda predmet je urˇcená pro reprezentaci pˇredmˇet˚ u. Tyto pˇredmˇety jsou následnˇe procesy pˇreváˇzeny z jednoho stavu do jiného. Zde si pamatujeme název 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ádku pˇri pˇr´ıpadném v´ yskytu chyby.

Pˇ rechodov´ e funkce koneˇ cn´ eho automatu Tˇr´ıda prechodova funkce je urˇcená pro reprezentaci pˇrechodové funkce koneˇcného automatu. Zde si pamatujeme název stavu, ze kterého je pˇrechodová funkce volána, zda je v pˇrechodové funkci volána nˇejaká podm´ınka pro zjiˇstˇen´ı správné pˇrechodové funkce, ˇc´ıslo ˇrádku ze souboru pro pˇr´ıpadné vypsán´ı chyby. Následnˇe si zde pamatujeme bud’ název slova z abecedy a stav, kam se pˇresuneme, nebo název podm´ınky, kterou budeme volat, a seznam pˇredávan´ ych parametr˚ u. Z pˇredchoz´ıho plyne, ˇze nikdy nejsou vyplnˇeny vˇsechny promˇenné. Pokud pˇrechodová funkce nevolá ˇza´dnou podm´ınku, tak nen´ı vyplnˇen seznam parametr˚ u. A pokud podm´ınku voláme, tak nen´ı vyplnˇen stav, kam se pˇresuneme.

Stavy automatu Tˇr´ıda stav je urˇcená pro reprezentaci stavu koneˇcného automatu. Zde si pamatujeme název stavu a zda je stav pˇrij´ımac´ı, ˇci nikoliv a dále pro správné oznaˇcen´ı chyby ˇc´ıslo ˇra´dku ze souboru.

Dalˇ s´ı tˇ r´ıdy Zde pop´ıˇseme dalˇs´ı tˇr´ıdy, které automat obsahuje. Tyto tˇr´ıdy jsou zm´ınˇené zde, protoˇze se pouˇz´ıvaj´ı jen jednou, nebo jsou jednoduché 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áˇren´ı instanc´ı jin´ ych tˇr´ıd. Tyto instance tvoˇr´ı poloˇzky datov´ ych struktur automatu. Prevoz Tˇr´ıda reprezentuj´ıc´ı jednotlivé poloˇzky, které jsou naloˇzeny na procesech. Promˇenné reprezentuj´ı název pˇredmˇetu, c´ılov´ y stav a poˇcet nákladu na procesu.

18

Udalost Tˇr´ıda reprezentuj´ıc´ı jednotlivé události. Promˇenné reprezentuj´ı ˇcas události, název procesu, slovo abecedy, stav, ve kterém se proces bude nacházet, a náklad. Náklad je reprezentován 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ázev dalˇs´ı podm´ınky (vetev podminka). Dále obsahuje hlaviˇcku metody vyhodnot. Vetev konecna Tˇr´ıda reprezentuj´ıc´ı vˇetev podm´ınky, která obsahuje pˇrechodovou funkci. Pˇredkem je abstraktn´ı tˇr´ıda Avetev. Metoda obsahuje promˇenné pro stavy reprezentuj´ıc´ı stav odkud a stav kam. Vetev podminka Tˇr´ıda reprezentuj´ıc´ı vˇetev podm´ınky, která obsahuje volán´ı dalˇs´ı podm´ınky. Pˇredkem je abstraktn´ı tˇr´ıda Avetev. Metoda obsahuje seznam reprezentuj´ıc´ı parametry, které se pˇredaj´ı volané podm´ınce.

19

4.3

Regul´ arn´ı gramatika

Tato ˇcást programu obsahuje jen dvˇe tˇr´ıdy, jelikoˇz se bude následnˇe gramatika pˇrevádˇet na automat.

Pr´ ace gramatiky Tˇr´ıda Gramatika reprezentuje naˇcten´ı gramatiky ze souboru a následnou 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ásledné uloˇzen´ı regulárn´ı gramatiky do datov´ ych struktur. Zde jsou promˇenné pro pˇrij´ımac´ı stavy, které mohou b´ yt zadány bud’ pomoc´ı automatové syntaxe, nebo pˇres pravidla, ale ne obˇema zp˚ usoby. Název 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ál˚ u, terminál˚ u a dalˇs´ıch ˇcást´ı, které se následnˇe budou jednoduˇsˇseji pˇrevádˇet na koneˇcn´ y automat. Také si zde vytváˇr´ıme podm´ınky, které pouˇzijeme pˇri práci koneˇcného automatu. Název souboru je Gramatika prevod na KA. Posledn´ı soubor obsahuje definice datov´ ych struktur pro uloˇzen´ı gramatiky. Zde jsou datové struktury pro uloˇzen´ı d˚ uleˇzit´ ych informac´ı, napˇr. pravidel, proces˚ u, pˇredmˇet˚ u a dalˇs´ı. Zde vytváˇr´ıme instanci této tˇr´ıdy a následnˇe upravujeme pravidla, aby ˇsla jednoduˇseji pˇrevést na pˇrechodové funkce koneˇcného automatu. Název souboru je Gramatika inicializace.

Pravidla gramatiky Tˇr´ıda pravidlo reprezentuje pravidla gramatiky. Obsahuje promˇenné pro neterminál, ze kterého je pravidlo voláno, dále terminál reprezentuj´ıc´ı ˇcinnost automatu, neterminál, kam se pomoc´ı tohoto pravidla dostaneme, podm´ınku, pokud je nutná. Dále obsahuje ˇc´ısla ˇra´dk˚ u, kde pravidlo zaˇc´ıná a konˇc´ı, a odkaz na dalˇs´ı pravidlo, pokud existuje. Zde nebudou vyplnˇené vˇsechny promˇenné, stejnˇe jako u pˇrechodov´ ych funkc´ı koneˇcného automatu.

20

4.4

Vizualizace

Kaˇzdá z následuj´ıc´ıch tˇr´ıd reprezentuje jedno zobrazované okno.

Uv´ıtac´ı obrazovka Okno MainWindow se zobraz´ı po spuˇstˇen´ı programu. Slouˇz´ı k otevˇren´ı prázdného 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ého souboru a ukonˇcen´ı programu. Dále jsou v menu poloˇzky pro spuˇstˇen´ı automatu a gramatiky. Následnˇe z tohoto okna lze spustit diskrétn´ı simulaci.

Chyby Toto okno se zobraz´ı, pokud jsou v automatu nebo gramatice chyby. Tyto chyby jsou následnˇe v editoru podtrˇzené ˇ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é se v nich nacházej´ı. Dále zobrazuje názvy proces˚ u, které se v tu chv´ıli v nich nacházej´ı.

Zobrazen´ı kalend´ aˇ re Okno Automat kalendar se zobraz´ı spolu s okny Automat zobrazeni a Automat procesy. Zobraz´ı aktuáln´ı ˇcas a události obsaˇzené v kalendáˇri.

Zobrazen´ı proces˚ u Okno Automat procesy se zobraz´ı spolu s okny Automat zobrazen´ ı a Automat kalendar. Zobraz´ı procesy a informace o jejich nákladu, jako název, mnoˇzstv´ı a c´ılov´ y stav.

21

5. Uˇ zivatelsk´ a dokumentace 5.1

Automat

Pˇ r´ıklad Ukáˇzeme si pˇr´ıklad, na kterém si demonstrujeme základn´ı ˇca´sti koneˇcného 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é 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ýpis %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é koncovky program neakceptuje. Vstupn´ı soubor je logicky rozdˇelen do nˇekolika ˇcást´ı: • Promˇenné • Pˇredmˇety automatu • Procesy automatu • Stavy • Pˇrij´ımac´ı stavy • Abeceda • Pˇrechodové funkce • Podm´ınky • Vlasn´ı v´ ypis Komentáˇre v souboru jsou pouze ˇra´dkové, tj. od posloupnosti znak˚ u // do konce ˇrádku. Pˇri definován´ı vlastn´ıho výpisu budeme do souboru vypisovat námi zadaná text.

Promˇ enn´ e Tato ˇcást je nepovinná pro bˇeh programu. Tato ˇcást se dá vyuˇz´ıt pouze v podm´ınkách, kde slouˇz´ı ke zjednoduˇsen´ı vyhodnocován´ı 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ém k vyhodnocen´ı v podm´ınkách. Promˇenná se skládá ze dvou poloˇzek oddˇelen´ ych teˇckou. Prvn´ı poloˇzkou je název logické ˇcásti, kam promˇenná ukazuje (proces, predmet, abeceda). Druhá poloˇzka pak ukazuje na konkrétn´ı název, na kter´ y se m˚ uˇzeme odkázat v logické ˇca´sti, kterou máme urˇcenou prvn´ı poloˇzkou. Seznam moˇzn´ ych kombinac´ı, které lze pouˇz´ıt v promˇenn´ ych: • proces.name tato promˇenná reprezentuje název aktuáln´ıho procesu • proces.kapacita tato promˇenná nám dovoluje pˇristoupit k volné kapacitˇe procesu, kter´ y právˇe vykonává nˇejakou ˇcinnost • predmet.name tato promˇenná reprezentuje názvy pˇredmˇet˚ u 23

• predmet.kapacita zde zjist´ıme mnoˇzstv´ı pˇredmˇetu, které jeˇstˇe zb´ yvá pˇrem´ıstit • predmet.start zde zjist´ıme, kdy bude pˇredmˇet pˇripraven k pˇremist’ován´ı • predmet.in zde zjist´ıme, kde pˇredmˇet zaˇc´ıná svou pout’ • predmet.out zde zjist´ıme, kam máme pˇredmˇet pˇrem´ıstit • abeceda.last zde dostaneme posledn´ı slovo z abecedy, které je oznaˇceno znakem @ • aktualni.cas zde dostaneme aktuáln´ı ˇcas • stav.konec tato promˇenná reprezentuje pˇrij´ımac´ı stavy • aktualni.stav tato promˇenná reprezentuje aktuáln´ı stav, ve kterém se proces nacház´ı. tato promˇenná lze pouˇz´ıt pouze ve vlastn´ım v´ ypisu

Pˇ redmˇ et automatu Tato ˇcást je povinná pro bˇeh programu. Tato ˇcást nám ˇr´ıká, co se bude bˇehem bˇehu programu pˇremist’ovat z jednoho m´ısta do jiného m´ısta. Také nám ˇr´ıká, kdy m˚ uˇzeme program ukonˇcit. Zápis pˇredmˇetu v souboru: ˇrádek zaˇc´ıná slovem co, za kter´ ym následuje tabulátor. Dále následuje v tomhle poˇrad´ı: • název • poˇcet • startovn´ı ˇcas, kdy s t´ımto pˇredmˇetem m˚ uˇzeme pracovat • m´ısto, na kterém bude tento pˇredmˇet ˇcekat na zpracován´ı • m´ısto, kam pˇredmˇet pˇrem´ıst´ıme

24

Proces automatu Tato ˇca´st je povinná pro bˇeh programu. Udává nám konatele, kter´ y bude procházet automatem. Zápis procesu v souboru: ˇrádek zaˇc´ıná znakem p, kter´ y je následován tabulátorem. Dále následuj´ı tyto ˇcásti: • název • kapacita • startovn´ı m´ısto : startovn´ı ˇcas • následuje seznam ˇcas˚ u pro jednotlivé znaky z abecedy ve stejném poˇrad´ı, v jakém jsou dané v abecedˇe

Stavy automatu Tato ˇca´st je povinná pro bˇeh programu. Udává nám m´ısta, ve kter´ ych sledujeme diskrétn´ı simulaci. Ve stavech sledujeme procesy, co tam právˇe vykonávaj´ı. Zápis stavu v souboru: ˇrádek zaˇc´ıná znakem Q, kter´ y je následován tabulátorem. Poté následuje jen jedna ˇcást, a to název stavu. V názvu stavu se nesm´ı vyskytovat b´ılé znaky.

Pˇ rij´ımac´ı stavy Tato ˇcást je povinná pro bˇeh programu. Udávaj´ı nám stavy, ve kter´ ych se mus´ı nacházet procesy, aby simulace mohla b´ yt ukonˇcena. Zápis stavu v souboru: ˇrádek zaˇc´ıná znakem F, kter´ y je následován tabulátorem. Poté m˚ uˇze nastat jedna ze dvou moˇznost´ı: • nap´ıˇseme název stavu, kter´ y budeme cht´ıt m´ıt za pˇrij´ımac´ı • pouˇzijeme znak Q, kter´ y nám ˇr´ıká, ˇze za pˇrij´ımac´ı stavy chceme pouˇz´ıt vˇsechny stavy automatu

25

Abeceda Tato ˇca´st je povinná pro bˇeh programu. Udává nám ˇcinnosti, pomoc´ı kter´ ych procesy pˇrecház´ı z jednoho stavu do jiného. Zápis abecedy v souboru: ˇrádek zaˇc´ıná znakem X, kter´ y je následován tabulátorem. Dále obsahuje povinnˇe název a nepovinnˇe m˚ uˇze obsahovat nˇekteré z následuj´ıc´ıch znak˚ u oddˇelené mezerou. • znak @ indikuje, ˇze takto oznaˇcená ˇcinnost, která byla pouˇzita naposled, bude uloˇzena v promˇenné abeceda.last • znak + indikuje nakládán´ı pˇredmˇet˚ u na procesy • znak - indikuje vykládán´ı pˇredmˇet˚ u z proces˚ u

Pˇ rechodov´ e funkce Tato ˇcást je povinná pro bˇeh programu. Udávaj´ı nám pˇrechod z jednoho stavu do jiného stavu pomoc´ı slova z abecedy. Zápis pˇrechodové funkce v souboru: ˇrádek zaˇc´ıná znakem d, kter´ y je následován tabulátorem. Pˇrechodové funkce v programu jsou dvoj´ıho typu: • pˇr´ımá pˇrechodová funkce • pˇrechodová funkce s podm´ınkou Pokud z jednoho stavu máme v´ıce pˇrechodov´ ych funkc´ı, tak pouˇzijeme pˇrechodovou funkci s podm´ınkou, kde po splnˇen´ı nˇejakého poˇctu podm´ınek dostaneme správnou pˇrechodovou funkci, pomoc´ı které se dostaneme do v´ ysledného stavu. Pˇ r´ım´ a pˇ rechodov´ a funkce Pˇr´ımá pˇrechodová funkce je pˇrechodová funkce, která je pˇresnˇe definována. Funkce obsahuje tuto posloupnost: • stav, kterého se tato funkce t´ yká • slovo z abecedy, které udává, jak se proces dostane do dalˇs´ıho stavu • stav, ve kterém se proces bude nacházet

26

Pˇ rechodov´ a funkce s podm´ınkou Pˇrechodová funkce s podm´ınkou je pˇrechodová funkce, která se pouˇzije, pokud by z jednoho stavu vedlo v´ıce r˚ uzn´ ych pˇrechodov´ ych funkc´ı. Funkce obsahuje následuj´ıc´ı posloupnost: • stav, kterého se tato funkce t´ yká • slovo check, které udává, ˇze funkce bude volat podm´ınku • název podm´ınky, která se bude vykonávat • seznam stav˚ u v [ ], oddˇelen´ ych mezerou, které se pˇredaj´ı zm´ınˇené podm´ınce

Podm´ınky Tato ˇca´st je nepovinná pro bˇeh programu. Pokud ze stavu vede v´ıce pˇrechodov´ ych funkc´ı, tak nám podm´ınky pomáhaj´ı vybrat jednu, kterou pouˇzijeme. Zápis podm´ınky v souboru: ˇrádek zaˇc´ıná slovem check, následovan´ y tabulátorem. Dále obsahuje tuto posloupnost: • název podm´ınky, pˇres kter´ y ji budeme volat ych závorkách, oddˇelen´ ych ˇcárkou, seznam parametr˚ u • v kulat´ u je pouze znak {, kter´ y nám urˇcuje zaˇca´tek samotné • za seznamem parametr˚ podm´ınky • podm´ınku, která m˚ uˇze obsahovat pouze promˇenné, ˇc´ısla, parametry, ˇretˇezce pro porovnán´ı a symboly || (or, disjunkce), && (and, konjunkce), <, >, == • vˇetev then, která se zavolá po splnˇen´ı podm´ınky obsahuje slovo then a následnˇe pˇrechodovou funkci, nebo slovo check a název jiné podm´ınky a pˇridané parametry • vˇetev else, která jen m´ısto slova then obsahuje slovo else, je totoˇzná zavolá, pokud podm´ınka nen´ı splnˇena • na samostatném ˇra´dku znak }, kter´ y ukonˇcuje podm´ınku.

27

5.2

Gramatika

Pˇ r´ıklad Ukáˇzeme si pˇr´ıklad, na kterém si demonstrujeme základn´ı ˇca´sti regulárn´ı 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ál˚ 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ýpis ˇ je aktualni.cas, proces proces.name je v aktualni.stav% %Cas Dalˇs´ı moˇznosti zapsán´ı 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é koncovky program neakceptuje. Vstupn´ı soubor je logicky rozdˇelen do nˇekolika ˇcást´ı: • Promˇenné • Pˇredmˇety • Procesy • Pravidla • C´ıle • Podm´ınky • Info ypis • Vlasn´ı v´ Komentáˇre v souboru jsou pouze ˇra´dkové, tj. od posloupnosti znak˚ u // do konce ˇrádku. V programu bude gramatika pˇrevedena na koneˇcn´ y automat, kter´ y bude následnˇe zpracováván. Terminál je ekvivalentn´ı slovu abecedy z automatu. Neterminál je ekvivalentn´ı stavu z automatu. Promˇenné, Pˇredmˇety, Procesy a Vlastn´ı výpis jsou ˇca´sti gramatiky totoˇzné s ˇcástmi z automatu.

Pravidla Tato ˇcást je povinná pro bˇeh programu. Udávaj´ı nám pˇrechod z jednoho neterminálu do jiného pomoc´ı terminálu. Zápis pravidla v souboru: ˇrádek zaˇc´ıná znakem d, kter´ y je následován tabulátorem. Dále m˚ uˇze nastat jedna z následuj´ıc´ıch moˇznost´ı: • jednoduché pravidlo • pravidlo s podm´ınkou • volán´ı podm´ınky • c´ılové pravidlo

29

Jednoduch´ e pravidlo Jednoduché pravidlo je pravidlo, které popisuje pˇrechod z jednoho neterminálu do jiného. Toto pravidlo nepovoluje popis pˇrechodu z neterminálu do neterminálu z mnoˇziny neterminál˚ u. Toto pravidlo obsahuje: • neterminál, ze kterého je pravidlo voláno • soubor znak˚ u −> • terminál, pomoc´ı kterého se dostaneme do c´ılového neterminálu • neterminál, kam se pˇresuneme pomoc´ı terminálu Pravidlo s podm´ınkou Pravidlo s podm´ınkou je pravidlo, které nám dovoluje si vybrat z v´ıce neterminál˚ u. Toto pravidlo obsahuje: • neterminál, ze kterého je pravidlo voláno • soubor znak˚ u −> • terminál, pomoc´ı kterého se dostaneme do c´ılového neterminálu • neterminál, kam se pˇresuneme pomoc´ı terminálu • v { } podm´ınka pokud je tato podm´ınka splnˇena, tak pouˇzijeme terminál a neterminál zm´ınˇen´ y v´ yˇse pokud ne, tak p˚ ujdeme na dalˇs´ı ˇrádek • na dalˇs´ım ˇrádku je znak |, kter´ y slouˇz´ı pro oddˇelen´ı posloupnost´ı terminál˚ u, neterminál˚ u a podm´ınek • za t´ımto znakem následuje terminál a neterminál • za neterminálem m˚ uˇze následovat dalˇs´ı podm´ınka pokud zde bude, tak pravidlo mus´ı pokraˇcovat na dalˇs´ım ˇrádku 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án´ı podm´ınky. Toto pravidlo obsahuje: • neterminál, ze kterého je pravidlo voláno • soubor znak˚ u −> • slovo check, které nám ˇr´ıká, ˇze budeme volat podm´ınku • název podm´ınky, která se bude volat • v [ ] oddˇelen´ ych mezerou seznam parametr˚ u, které se pˇredaj´ı podm´ınce C´ılov´ e pravidlo Toto pravidlo slouˇz´ı k zapsán´ı neterminálu, kter´ y slouˇz´ı jako c´ıl. Toto pravidlo obsahuje: • neterminál, ze kterého je pravidlo voláno • soubor znak˚ u −> • znak $, kter´ y nám ˇr´ıká, ˇze neterminál bude i c´ıl tento znak lze pouˇz´ıt pouze v c´ılovém pravidle, tzn. nelze pouˇz´ıt ani v pravidle s podm´ınkou

C´ıle Tato ˇca´st gramatiky je povinná. Tato ˇcást je ekvivalentn´ı k pˇrij´ımac´ım stav˚ um z automatu. Zápis c´ıle lze do souboru zapsat jednou z následuj´ıc´ıch moˇznost´ı: • pomoc´ı syntaxe pˇrij´ımac´ıch stav˚ u z automatu F tab neterminál • pomoc´ı c´ılového 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á jinou podm´ınku, tak se nic nemˇen´ı. Pokud nevolá podm´ınku, tak je v souboru vˇetev zapsána takto: then/else termin´ al netermin´ al

31

Info Tato ˇca´st nen´ı povinná. Slouˇz´ı k nastaven´ı bliˇzˇs´ıch informac´ı k terminál˚ um. Zápis v souboru: ˇ adek dále obsahuje: ˇrádek zaˇc´ıná slovem info, které je následováno tabulátorem. R´ • znak reprezentuj´ıc´ı bliˇzˇs´ı informaci • terminál, kterého se informace t´ yká Seznam moˇzn´ ych znak˚ u: + - tento znak nám urˇcuje, které terminály nakládaj´ı pˇredmˇety na procesy - - tento znak nám urˇcuje, které terminály vykládaj´ı pˇredmˇety z proces˚ u @ - tento znak nám urˇcuje terminály, které 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ázdn´ y editor pro psan´ı automatu Otevˇ r´ıt - otevˇre v editoru vybran´ y soubor s automatem - soubor se dá upravovat i spouˇstˇet Zavˇ r´ıt - zavˇre cel´ y program

Editor Editor nám slouˇz´ı k u ´pravˇe automatu. Celé okno obsahuje textov´ y editor, kter´ y slouˇz´ı pro u ´pravu textu, checkbox, kter´ y povol´ı v´ ypis do souboru, textové pole pro napsán´ı cesty k souboru a menu se dvˇemi záloˇzkami: • Soubor Soubor dále 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ásleduj´ıc´ı poloˇzky: • Nov´ y tato poloˇzka uloˇz´ı rozpracovanou ˇcást v editoru a následnˇe editor vyprázdn´ı lze pouˇz´ıt i zkratku Ctrl + N. • Otevˇr´ıt tato poloˇzka uloˇz´ı rozpracovanou práci (pokud nˇejaká byla) a otevˇre dialog pro vybrán´ı 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áci pokud práce nebyla jiˇz dˇr´ıve uloˇzena, nab´ıdne dialog pro uloˇzen´ı práce 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áce z editoru • Zavˇr´ıt tato poloˇzka uloˇz´ı práci a uzavˇre cel´ y program 33

Menu - Run V menu Run je následuj´ıc´ı poloˇzka: • Automat tato poloˇzka uloˇz´ı rozpracovanou práci 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á okna pro zobrazen´ı automatu a bliˇzˇs´ı informace o simulaci. V hlavn´ım oknˇe se zobraz´ı v obdéln´ı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áklad. V posledn´ım oknˇe se zobrazuj´ı informace z kalendáˇre. V horn´ı ˇca´sti je aktuáln´ı ˇcas. Dále se zobraz´ı procesy z kalendáˇre spolu s ˇcasem, kdy bude dále pracovat.

Probl´ emy Pˇri v´ yskytu chyb se zobraz´ı chyby v novém oknˇe a v editoru budou chyby podtrˇzené ˇcervenˇe. Mezi základn´ı chyby, které se zobraz´ı, patˇr´ı chyby v logick´ ych ˇca´stech souboru: • Promˇenné zde m˚ uˇze nastat chyba pˇri nedodrˇzen´ı syntaxe pomoc´ı . (teˇcky), která zajiˇst’uje rozdˇelen´ı promˇenné na hlavn´ı ˇca´st a konkretizuj´ıc´ı ˇcást • 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ást´ı • 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é pˇri nedodrˇzen´ı syntaxe, hlavnˇe pˇri poloˇzce start, která se skládá ze dvou ˇca´st´ı oddˇelen´ ych : (dvojteˇckou) • Stavy zde m˚ uˇze nastat chyba, pokud bychom pouˇzili v názvu stavu mezeru, která nen´ı povolená • Pˇrij´ımac´ı stavy zde m˚ uˇze nastat stejná 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ázvu nebo pouˇzit´ı nesprávného znaku pro bliˇzˇs´ı urˇcen´ı ˇcinnosti slova abecedy • Pˇrechodové funkce zde m˚ uˇze nastat chyba pˇri nedodrˇzen´ı syntaxe zde ale m˚ uˇze nastat i chyba, která 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ázev a pˇri vyhodnocován´ı podm´ınky se nám nebudou shodovat názvy a program m˚ uˇze pracovat nesprávnˇe • Podm´ınky zde by mohl nastat problém pˇri nedodrˇzen´ı syntaxe

Ukonˇ cen´ı programu Pro ukonˇcen´ı programu je nutné uzavˇr´ıt editor. Pˇri uzavˇren´ı jen grafického zobrazen´ı z˚ ustane editor stále otevˇren. Pˇri uzavˇren´ı editoru se rozdˇelaná práce 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ádˇet diskrétn´ı simulace r˚ uzn´ ych jev˚ u. To se také podaˇrilo. ´ Uspˇechem je, ˇze jsme za pouˇzit´ı koneˇcného automatu a regulárn´ı gramatiky vyˇreˇsili univerzalitu, protoˇze univerzalita byla hlavn´ım problémem programu. V´ yhodou bylo vyˇreˇsen´ı nedeterminismu koneˇcného automatu, které neobsahuje zanedbán´ı nedeterminismu. Dalˇs´ım u ´spˇechem je vytvoˇren´ı jednochuché vizualizace, která bude lehce zobrazena i na menˇs´ıch obrazovkách. Bohuˇzel se nepodaˇrilo vyˇreˇsit vˇsechny problémy spojené s diskrétn´ı simulac´ı. Jedn´ım z problém˚ u, které 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ávány mezi jednotliv´ ymi procesy. Toto se dá napravit napsán´ım diskrétn´ı simulace, kde si pˇrestupy zaˇr´ıd´ıme jako nové vstupy pˇredmˇet˚ u. Dalˇs´ım problémem je to, ˇze program neobsahuje generátor pseudonáhodn´ ych veliˇcin. Proto se mus´ı vyuˇz´ıt jiného programu, kter´ y nám tyto pseudonáhodné veliˇciny vygeneruje. Dalˇ s´ı moˇ zn´ a rozˇ s´ıˇ ren´ı. Bohuˇzel jeˇstˇe zb´ yvaj´ı ˇca´st´ı, které se nestihly naimplementovat. Mezi tyto ˇcásti patˇr´ı v´ yˇse zm´ınˇené problémy. Dále bychom mohli v programu vytváˇret statistiky. Program totiˇz provád´ı pouze v´ ypis. Na vytvoˇren´ı statistiky mus´ıme v´ ypisy pˇredat do jiného programu, kter´ y nám statistiku následnˇe vytvoˇr´ı. Nakonec bychom mohli bˇehem pr˚ ubˇehu diskrétn´ı simulace upravovat jednotlivé ˇca´sti koneˇcného automatu nebo regulárn´ı gramatiky.

36

Seznam pouˇ zit´ e literatury ˇivy ´ , I, Kindler, E. Simulace a modelov´ [1] Kr an´ı. Ostrava: Ostravská univerzita, 2001. [2] Kindler, E. Simulaˇcn´ı programovac´ı jazyky. Praha: SNTL, 1980. [3] Pidd, M. Computer simulation in management science. Velká Británie: John Wiley, 1992. ISBN 0-471-93462-3. ˇ ic ˇka, P. Simulaˇcn´ı metody jako nástroj pro rozhodov´ [4] Koc an´ı podniku - modelován´ı pomoc´ı programu Witness. Brno: Masarykova univerzita, 2009. [5] Mal´ık, M. Poˇc´ıtaˇcová 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á informatika: uˇcebn´ı text (on-line). 1. vydán´ı. Ostrava: [8] Janc ˇ Ediˇcn´ı stˇredisko VSB-TUO, 2007 ISBN 978-80-248-1487-2. ´ [9] Kocour, P. Uvod do teorie koneˇcných automat˚ u a formáln´ıch jazyk˚ u. 1. vydán´ı. Plzeˇ n: Západoˇceská 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á 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áln´ı 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án´ı Bratislava: Alfa, 1978 Pˇrel. z: Formal languages and their relation to automata. ISBN 63-096-78 [14] Internetové podp˚ urné prostˇred´ı k pˇredmˇetu Teoretick´ a informatika Univerzita Hradec Králové: 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án´ı 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ého CD. • Tato bakaláˇrská práce v elektronické formˇe. • Instalaˇcn´ı soubor pro instalaci programu Univerz´ aln´ ı diskr´ etn´ ı simul´ ator. Soubor se nacház´ı v adresáˇri Instalace. • Dokumentace programu v adresáˇri Dokumentace. • Zdrojové kódy v adresáˇri Zdrojov´ e k´ ody. • Testovac´ı data v adresáˇri Test.

39

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

Recommend Documents