Webový simulátor Turingova stroje

MASARYKOVA UNIVERZITA Fakulta informatiky

Webový simulátor Turingova stroje Bakalářská práce

Stanislav Straka

Vedoucí práce: Mgr. Jiří Barnat Ph.D. Brno 2006

Shrnutí Cílem této bakalářské práce je napsat webový simulátor Turingova stroje. Tento simulátor by měl být schopen načíst Turingův stroj ze souboru, který je napsaný ve speciálně navrženém formátu. Po načtení Turingova stroje by měl být schopen simulovat a graficky znázorňovat výpočet tohoto Turingova stroje nad nějakým vstupním slovem. Turingův stroj, vstupní slovo a způsob simulace by si pomocí ovládacích prvků simulátoru měl volit samotný uživatel.

Klíčová slova webový, simulátor, turingův stroj, applet, java

Prohlášení Prohlašuji, že jsem bakalářskou práci vypracoval samostatně a použil pouze literaturu uvedenou v přiloženém seznamu. Nemám námitek proti půjčení práce se souhlasem katedry ani proti zveřejnění práce nebo její části.

V Brně dne 5. ledna 2006

Stanislav Straka

Obsah 1. Teoretický úvod do Turingových strojů ......................................................................... 6 1.1. Neformální popis Turingova stroje ...................................................................... 6 1.2. Formální popis Turingova stroje .......................................................................... 7 1.3. Nedeterministický Turingův stroj ........................................................................ 7 2. Formát zápisu Turingova stroje pro tento simulátor ................................................... 9 2.1. Zápis Turingova stroje ........................................................................................... 9 2.1.1. Hlavicka Turingova stroje .......................................................................... 9 2.1.2. Tělo turingova stroje ................................................................................. 11 2.2. Vzorový Turingův stroj ....................................................................................... 13 3. Uživatelská příručka simulátoru Turingova stroje ..................................................... 15 3.1. Spuštění simulátoru Turingova stroje ............................................................... 15 3.2. Jak nahrát Turingův stroj do simulátoru? ......................................................... 15 3.2.1. Výběr z databáze simulátoru ................................................................... 16 3.2.2. Načtení Turingova stroje z externího souboru ...................................... 16 3.3. Simulace výpočtu Turingova stroje .................................................................... 16 3.3.1. Grafické znázornění řídící jednotky Turingova stroje ............................ 16 3.3.2. Spuštění simulace Turingova stroje ........................................................ 17 3.3.3. Funkce tlačítek Přejdi a Přejdi o délku vstupu ................................... 17 3.3.4. Funkce tlačítek Simulace, Stop, Dokonči ............................................. 17 3.3.5. Tlačítka Náhodná simulace a Dokonči náhodně ................................ 18 3.3.6. Tlačítka ve spodním bílém poli ............................................................... 18 3.4. Instalace simulátoru na novém URL ................................................................. 19 4. Implementace Webového simulátoru Turingova stroje ............................................. 20 4.1. Syntaktický analyzátor, balíček parser ............................................................. 20 4.1.1. Obecný postup při syntaktické analýze ................................................. 20 4.1.2. Součásti syntaktického analyzárou ......................................................... 21 4.1.3. Popis jednotlivých tříd syntaktického analyzátoru .............................. 21 4.2. Výkonná jednotka simulátoru, balíček turing ................................................. 24 4.2.1. Části výkonné jednotky simulátoru ....................................................... 24 4.2.2. Popis jednotlivých částí výkonné jednotky simulátoru ....................... 24 4.3. Zobrazovací jednotka simulátoru ...................................................................... 26 4.3.1. Části zobrazovací jednotky simulátoru .................................................. 26 4.3.2. Popis jednotlivých tříd zobrazovací jednotky simulátoru .................. 27 4.4. Hlavní řídicí jednotka simulátoru, balík main .................................................. 28 4.4.1. Části řídicí jednotky simulátoru, balík main .......................................... 28 4.4.2. Popis pomocných tříd řídící jednotky simulátoru ................................ 29 4.4.3. Popis činnosti třídy MujApplet ................................................................. 30 5. Závěr .................................................................................................................................. 36 1. Obsah archivu .................................................................................................................. 37 Literatura .............................................................................................................................. 38

5

Kapitola 1 Teoretický úvod do Turingových strojů Turingův stroj je pojmenován podle britského matematika Alana Turinga(19121954),který ho roku 1937 v článku nazvaném O vyčíslitelnosti (On Computable Numbers) definoval. Turingův stroj dokáže realizovat libovolný proces, který lze intuitivně nazvat algoritmem.

1.1. Neformální popis Turingova stroje Turingův stroj byl navržen dlouho předtím, než se objevil první počítač. Motivací pro jeho definici byla snaha přesně rozlišit, co je a co není vyčíslitelné, tj. co lze a co nelze efektivně vypočítat. Z toho vyplynuly základní požadavky. Zaprvé, každý výpočet se musí dát reprezentovat konečným způsobem. Zadruhé, výpočet se má skládat z diskrétních kroků, přičemž každý z nich je mechanicky realizovatelný Turingův stroj se skládá z konečné množiny stavů Q, pásky, která je rozdělena na jednotlivá políčka, a hlavy, která se může po pásce pohybovat doleva a doprava, číst a zapisovat symboly. Na každém políčku pásky je zapsán právě jeden z konečně mnoha páskových (pracovních) symbolů. Páska je jednosměrně nekonečná. Na jejím nejlevějším (nuletém) políčku je zapsán speciální symbol >, oznacující levý konec pásky. Na začátku výpočtu je na 1. až n., kde n ≥ 0, políčku pásky zapsán vstupní řetězec (vstupem může být i prázdný řetězec). Ostatních nekonečně mnoho políček napravo od vstupu je prázdných, respektive obsahují speciální znak _. Výpočet začíná v počátečním stavu q0, přičemž hlava snímá nulté poíčko obsahující levou koncovou značku >. Krok výpočtu spočívá v tom, že stroj v závislosti na momentálním stavu a symbolu snímaném hlavou provede následující: 1.

změní svůj stav, či přesněji může změnit,

2.

zapíše symbol na políčko snímané hlavou, čímž přepíše symbol, který tam byl zapsán předtím,

3.

posune hlavu o jedno políčko doprava, nebo doleva.

Způsob jakým se má změnit stav, přepsat symbol a posunout hlava, předepisuje přechodová funkce δ. Stroj akceptuje (přijme) vstupní řetězec, přávě když přejde do

6

1.2. Formální popis Turingova stroje speciálního stavu qaccept. Stroj zamítá, právě když přejde do speciálního zamítajícího stavu qreject. Na některých vstupech může výpočet běžet nekonečně dlouho, aniž by stroj vstupní slovo akceptoval, nebo zamítnul. V takovém případě říkáme, že stroj pro daný vstup cyklí.

1.2. Formální popis Turingova stroje V celé své práci jsem se držel formální definice[1], neboť je tato definice vyučována na zdejší fakultě. Turingův stroje je devítice M =(Q,Σ,Γ,>,_,δ,q0,qaccept,qreject) kde: • Q je konečná množina stavů; • Σ je konečná množina vstupních symbolů; • Γ je konečná množina páskových symbolů; • > ∈ Γ\Σ je levá koncová značka; • _ ∈ Γ\Σ je symbol označující prázdné políčko; • δ:(Q\{qaccept,qreject}×Γ → Q×Γ×{L,R} je totální přechodová funkce; • q0 ∈ Q je počáteční stav; • qaccept ∈ Q je akceptující stav; • qreject ∈ Q je zamítající stav; Navíc vyžadujeme, aby Turingův stroj nikdy nepřepsal levou koncovou značku jiným symbolem a aby nikdy neposunul svou hlavu vlevo od políčka obsahujícího levou koncovou značku. Formálně, požadujeme aby pro ∀q ∈ Q existoval stav p ∈ Q takový,že

δ(q,>) = (p,>,R). Množina stavů spolu s přechodovou funkcí se někdy souhrnně označuje jako řídící jednotka Turingova stroje.

1.3. Nedeterministický Turingův stroj Rozdíl oproti původnímu (deterministickému) Turingovu stroji spočívá v tom, že pro daný stav a snímaný symbol má nedeterministický stroj obecně několik možností pro následující krok. Každá možnost zahrnuje nový stav, symbol,který se má zapsat na pásku a směr, kterým se má posunout čtecí hlava. Nedeterministický stroj akceptuje, právě když existuje výpočet (tj. nějaká posloupnost výběru kroků) vedoucí do akceptující konfigurace.

7

1.3. Nedeterministický Turingův stroj Deterministický a nedeterministický Turingův stroj jsou, co se týče příjímané třídy jazyků, ekvivalentní. Jednodušeji pro každý nedeterministický Turingův stroj existuje deterministický Turingův stroj, který akceptuje stejný jazyk a naopak[1]. Důkaz, že pro každý deterministický Turingů stroj existuje nedeterministický,který akceptuje stejný jazyk je zřejmý. Nedeterministický Turingův stroj mající pro každou kombinaci stavu a symbolu pouze jednu možnost přechodu je zřejmě deterministický Turingův stroj. Důkaz opačného tvrzení je složitější a není náplní této práce.

8

Kapitola 2 Formát zápisu Turingova stroje pro tento simulátor Vzhledem k neexistenci nějakého normalizovaného formátu zápisu Turingova stroje jsem byl nucen si navrhnout formát vlastní, tak jako to udělali autoři podobných simulátorů. Při návrhu jsem vycházel z formální definice[1]. Tento zápis by tudíž měl být pro studenty intuitivně zřejmý a přehledný.

2.1. Zápis Turingova stroje Zápis Turingova stroje se skládá z hlavičky a těla. V hlavičce se definuje množina stavů, vstupní abeceda a páskové abeceda, počáteční znak a znak prázdného políčka a počáteční, akceptující a zamítající stav. V těle Turingova stroje se pak definuje přechodová funkce. Každý příkaz v zápisu Turingova stroje musí být ukončen středníkem. Každý nový příkaz, či definice musí začínat na novém řádku. Každé slovo, nebo znak napsaný na novém řádku je automaticky považován za začátek nového příkazu, či definice. Každé slovo či znak napsaný za středníkem na tomtéž řádku jako středník je ignorován a může sloužit jako komentář. Soubor, ve kterém je Turingův soubor zapsán, musí mít příponu tm. Napíklad:

TuringMachine.tm

2.1.1. Hlavicka Turingova stroje První řádek může a nemusí obsahovat jméno Turingova stroje. Tento řádek může sloužit též jako poznámka, co vlastně tento Turingův stroj má dělá, nejvhodnější je popis jazyka přijímaného daným Turingovým strojem. Je zde pouze omezení, že se tento nápis musí nacházet celý na prvním řádku a musí být rovněž zakončen středníkem. Tato část je nepovinná a na funkci či vzhled Turingova stroje nemá žádný vliv. Využití nepovinné části je vhodné hlavně v případě, že hodláme tímto Turingovým strojem rozšířit vnitřní databázi simulátoru. První povinnou součástí zápisu Turingova stroje je definování uspořádané devítice. Řádek tedy začíná závorkou a následuje jméno množiny stavů, vstupní abecedy, pá9

2.1.1. Hlavicka Turingova stroje skové abecedy, počátečnícho znaku, znaku prázdného políčka, přechodové funkce, počátečího stavu, akceptujícího stavu a zamítajícího stavu. Všechny prvky devítice musí být odděleny čárkou. Uspořádaná devítice je ukončena závorkou a celý řádek je následně ukončen středníkem.

(MnožinaStavů,vstupní_abeceda,pásková_abeceda,>,_,delta,q0,qAccept,qReject);

První tři prvky devítice (množina stavů, vstupní a pásková abeceda) a přechodová funkce jsou pouze jména a jejich obsah bude definován na následujících řádcích. Nezáleží na pořadí, v jakém jsou definovány první tři prvky devítice, ale přechodová funkce musí být definována až jako poslední. 2.1.1.1. Definice množiny stavů K definici množiny stavů je ještě třeba dodat, jak lze pojmenovat stav. Stav může nést jaké koliv jméno, které neobsahuje čárku, středník nebo dvojtečku. Bude-li obsahovat bílý znak, tento znak bude vymazán. Je-li ovšem nevyhnutelné, či pro přehlednost žádoucí, pojmenovat si stav za pomocí čárky, je možné název celého stavu uzavřít do obyčejných, či hranatých závorek, popřípadě do uvozovek. Následně je ovšem důležité toto označení používat v celém souboru a to včetně uzavíracích značek. Tedy stav [q0,a] není ekvivalentní stavu (q0,a) ani "q0,a" ani naopak. Možné zápisy stavů: q0zacatek libovolný řetězec bez střeníku, čárky a dvojtečky "q1,a" název uzavřený uvozovkami obsahující čárku (q2,navrat) název uzavřený závorkami obsahující čárku [q1,b] název uzavřený hranatými závorkami obsahující čárku Jméno množiny stavů je určeno prvním povinným řádkem. Definice obsahu pak následuje na dalších řádcích. Definice se skládá z návěští, kterým je jméno množiny, dvojtečky a pak následuje výčet všech stavů vzájemně oddělených čárkou a zakončený středníkem.

10

2.1.2. Tělo turingova stroje

MnožinaStavů:q0,q1,q2,"q0,a",qAccept,qReject; Ve výčtu stavů nesmíte za pomenout na stavy jmenované v úvodní devítici. Devítice určuje pouze jejich význam pro Turingův stroj, nikoli jejich existenci. 2.1.1.2. Definice množiny vstupní abecedy Jméno vstupní abecedy je určeno prvním povinným řádkem. Definice obsahu pak následuje na dalších řádcích. Definice se skládá z návěští, kterým je jméno abecedy, dvojtečky a pak následuje výčet všech symbolů vzájemně oddělených čárkou. Celou definici vstupní abecedy zakončujeme středníkem.

vstupní_abeceda:a,b,c; 2.1.1.3. Definice množiny páskové abecedy Jméno páskové abecedy je opět určeno prvním povinným řádkem. Definice obsahu pak následuje na dalších řádcích. Definice se skládá z návěští, kterým je jméno abecedy, dvojtečky a pak následuje výčet všech symbolů vzájemně oddělených čárkou a zakončený středníkem. Ve výčtu symbolů nesmíte uvést ty symboly, které jste uvedli, či uvedete, do abecedy vstupní. Vstupní abeceda má zásadní vliv na jazyk akceptovaný Turingovým strojem a proto musí být uvedena zvlášť. Protože vstupní abeceda je podmnožinou páskové abecedy, objevily by se tyto symboly v zápisu dvakrát, což je zbytečné. Zároveň však nesmíme zapomenout vyjmenovat ty symboly obsažené v základní devítici. Devítice i zde určuje pouze význam a né definici těchto symbolů.

pásková_abeceda:>,X,_;

2.1.2. Tělo turingova stroje Jak bylo řečeno výše tělo turingova stroje je tvořeno definicí jeho přechodové funkce. Přechodová funkce je vlastně výkonná část určující, co bude daný Turingův stroj dělat. V této části definice turingova stroje lze již pracovat pouze se symboly a stavy definovanými dříve, proto si musíme dávat pozor zda jsme definovali všechy stavy a znaky, které budeme potřebovat. 2.1.2.1. Definice přechodového pravidla Přechodová funkce se skládá z přechodových pravidel. A proto je třeba nejprve osvětlit jak se definují přechodová pravidla. Přechodové pravidlo se skládá z aktuální konfigurace stroje a konfigurace, do které má stroj přejít. Aktuální konfigurace se skládá z aktuálního stavu a znaku pod čtecí hlavou vzájemně oddělených čárkou. Následuje dvojtečka a po ní přechodová konfigurace.

11

2.1.2. Tělo turingova stroje Přechodová konfigurace je celá uzavřena do obyčejných závorek a skládá se ze stavu, do kterého má Turingův stroj přejít, znaku, kterým má být přepsán aktuální znak pod hlavou, a pohybu hlavy. Vše je opět vzájemně oddělené čárkou. Pohyb hlavy se zapisuje pomoci velkých písmen R (doprava), L (doleva) a S (zůstaň stát). Celé přechodové pravidlo je pak ukončeno středníkem. Celé přechodové pravidlo pak vypadá takto:

q0,a : (q1,X,L); Uvádíme-li přechodové pravidlo, které má jako svůj cíl jeden z konečných stavů, tedy akceptující, nebo zamítající stav je stavem, do kterého se podle tohoto pravidla má přejít, pak nemáme povinnost vyplňovat následující položky přechodové konfigurace (tj. symbol a směr pohybu hlavy) smysluplnými, tedy dříve definovanými, znaky. Jako náhradu za ně lze uvést jakékoliv znaky jiné, nebo žádné. Čárky a závorky jsou však povinné.

q4,_: (qAccept,-,-); q4,b: (qReject,-,-); Tento simulátor je schopen simulovat také nedeterministický Turingův stroj, proto i formát zápisu přechodové funkce musí být schopen toto popsat. Jak bylo řečeno dříve nedeterministický Turingův stroj se od deterministického liší pouze v přechodové funkci. Nedeterministický stroj má pro některé konfigurace definované dva a více přechodových konfigurací. Tato skutečnost se vyjádří tím, že za aktuální konfiguraci uvedeme tyto přechodové konfigurace vzájemně oddělené dvojtečkou a za poslední opět napíšeme ukončovací středník. Nedeterministické přechodové pravidlo tedy může být zapsáno například takto:

q0,a: (q1,X,L) : (q2,a,R) : (q1,a,L); 2.1.2.2. Definice přechodové funkce V úvodní devítici jsme předodovou funci pojmenovali a toto jméno slouží jako návěští pro začátek její definice. Definice přechodové funkce tedy začíná na novém řádku svým jménem následovaným dvojtečkou. Hned za touto dvojtečkou následuje první přechodové pravidlo zakončené středníkem. Následující pravidla se musí uvádět vždy na nový řádek a musí vždy končit středníkem. Celá definice přechodové funkce se ukončuje středníkem na samostatném řádku. Ukončením definice přechodové funkce se zároveň ukončuje i definice celého Turingova stroje. Za tímto středníkem se jako za jediným nesmí nacházet komentář na tomtéž řádku. Ukončující středník musí stát na řádce naprosto osamocen. Komentář lze napsat až na řádek následující.

12

2.2. Vzorový Turingův stroj

delta: q0,>: (q1,>,R); q1,a: (q1,X,q2); skrtne symbol "a" ... ... q3,_: (qAccept,-,-); ; konec delta

2.2. Vzorový Turingův stroj

{a^n*b^n| n >= 0}; (MnozinaStavu,VstupniAbeceda,PaskovaAbeceda,>,_,delta,q0,qAccept,qReject); MnozinaStavu:q0,[q1,a],(q2,b),q3,q4,q5,qAccept,qReject; VstupniAbeceda:a,b; PaskovaAbeceda:>,X,_; delta: q0,>:(q0,>,R); q0,a:([q1,a],a,R); slovo zacina Ackem tedy muze byt z jazyka q0,b:(qReject,-,-); slovo zacina Beckem tedy neni z jazyka q0,_:(qAccept,-,-); jedna se o prazdne slovo tedy je z jazyka [q1,a],a:([q1,a],a,R); [q1,a],b:((q2,b),b,R); [q1,a],_:(qReject,-,-); slovo se zklada jen z Acek tedy neni z jazyka (q2,b),a:(qReject,-,-); slovo je tvaru aaaaaaabbbba (q2,b),b:((q2,b),b,R); (q2,b),_:(q3,_,L); q3,a:(q3,a,L); q3,b:(q3,b,L); stav q3 vrati hlavu na zacatek pasky q3,X:(q3,X,L); q3,>:(q4,>,R); q4,a:(q5,X,R); skrtne prvni Acko na ktere narazi q4,b:(qReject,-,-); ve slove je vice Becek nez Acek q4,X:(q4,X,R);

13

2.2. Vzorový Turingův stroj q4,_:(qAccept,-,-); ve slove je stejne Acek jako Becek q5,a:(q5,a,R); q5,b:(q3,X,L); skrtne prvni becko na ktere narazi q5,X:(q5,X,R); q5,_:(qReject,-,-); ve slove je vice Acek nezli Becek ; konec definice Turingova stroje "Posledni strednik ukoncujici definici prechodove funkce musi byt sam na samostatnem radku!!!!!"

14

Kapitola 3 Uživatelská příručka Turingova stroje

simulátoru

Mojí snahou bylo vytvořit uživatelské prostredí, které by nedovolilo uživately udělat chybu při samotné simulaci výpočtu Turingova stroje. Pokud se chyba nachází přímo v definici Turingova stroje, měl by ji tento simulátor odhalit a upozornit na ni autora onoho stroje, ale pouze v případě, jedná-li se o chybu, která je výslovně zakázána samotnou definicí Turingova stroje, jako je například přepsání levé koncové značky, nebo pohyb od levé koncové značky doleva, používání dříve nedefinovaných stavů, značek apod.

3.1. Spuštění simulátoru Turingova stroje Simulátor spustíte pouze tím, že do svého prohlížeče zadáte webovou stránku s adresou appletu. Pro zprávný běh simulátoru je třeba, aby prohlížeč byl schopen pracovat s java applety napsané v Javě 1.5. Následně se nám zobrazí simulátor s jedním již načteným Turingovým strojem. Turin-gův stroj, který se načte hned po spuštění je první v databázi simulátoru a jeho jméno je navolené na rolovacím tlačítku, které je určené pro výběr z této databáze. Celý simulátor se nachází ve stavu, který je stejný jako po jakémkoliv jiném načtení stroje, ať už byl načten z externího souboru nebo z databáze. Simulátor se zobrazí vždy přes celé okno prohlížeče. Máme-li Turingův stroj, jehož zobrazení se nevejde do okna simulátoru, můžeme velikost zobrazovací plochy přizpůsobit změnou velikosti okna prohlížeče.

3.2. Jak nahrát Turingův stroj do simulátoru? Turingův stroj je možné si zvolit, jak již bylo výše zmíněno, dvojím způsobem. Lze si jej buď vybrat z databáze simulátoru, kde bude menší množství „nejpoužívanějších“ Turingových strojů, nebo z externího souboru, tedy ze souboru který je uložen v počítači uživatele. Nahrát Turingův stroj je možné i v případě, že máme nějaký jiný Turingův stroj již do simulátoru nahraný a probíhá jeho simulace. Rozhodne-li se uživatel v takovéto situaci vyměnit Turingův stroj za jiný, dojde k zapomenutí stavu výpočtu starého Turingova stroje a načte se nový v iniciálním stavu. 15

3.2.1. Výběr z databáze simulátoru

3.2.1. Výběr z databáze simulátoru Výběr Turingova stroje z databáze simulátoru je velice jednoduchý. V Pravém horním rohu simulátoru se nachází výběrové tlačítko. Na toto tlačítko stačí pouze kliknout a rozbalí se nám seznam všech Turingových strojů z databáze. Následné kliknutí na daný Turingův stroj vede k jeho načtení a zobrazení.

3.2.2. Načtení Turingova stroje z externího souboru Načtení Turingova stroje z externího souboru se provede pomocí tlačítka Načti z externího souboru. Toto tlačítko je první od zhora v pravé části simulátoru. Po kliknutí na toto tlačítko se zobrazí klasické okno pro výběr souboru. V tomto okně následně vybereme soubor, ve kterém máme napsaný náš vlastní Turingův stroj, a potvrdíme. Při nahrávání vlastního Turingova stroje musí každý uživatel počítat s tím, že není neomylný a v jeho souboru se mohou nacházet syntaktické chyby. Všechny syntaktické chyby tento simulátor patrně odhalit neumí, ale pokud nějakou odhalí, tak na ni uživatele upozorní malým oknem s názvem Chybové hlášení a příslušným popisem chyby a číslem řádku, na kterém se chyba nacházela. Simulátor upozorňuje pouze na jednu odhalenou chybu. Je-li v souboru chyb více, bude vždy odhalena pouze první z nich (myšleno od začátku souboru).

3.3. Simulace výpočtu Turingova stroje V předchozí části jsme si zvolili Turingův stroj, jehož výpočet chceme simulovat. Po načtení stroje do simulátoru se zobrazí v prostřením bílém okně grafické znázornění řídící jednotky našeho Turingova stroje. V horním bílém oknu se nám zobrazí páska stroje se čtecí hlavou na levé koncové značce. V pravo do levé koncové značky se zobrazí symbol prázdného políčka. Toto vyobrazení symbolizuje prázdnou pásku. Na druhém řádku simulátoru, tedy hned pod výběrovými tlačítky, se zobrazí pásková a vstupní abeceda načteného Turingova stroje.

3.3.1. Grafické znázornění řídící jednotky Turingova stroje Turingův stroje je graficky znázorněn v podobě tabulky. V první sloupci se nacházejí všechny stavy, seřazené ve stejném pořadí jako ve zdrojovém souboru v definici množiny stavů. Na prvním řádku se nacházejí páskové symboly, opět ve stejném pořadní v jakém jsou zapsány ve zdrojovém souboru. V ostatních buňkách se nacházejí přechodové konfigurace pro daný stav (řádek) a daný symbol (sloupec). Neexistuje-li pro nejakou kombinaci stavu a symbolu přechodové pravidlo, pak se místo pravidla zobrazí několik pomlček. Je-li pro nějakou kombinaci stavu a symbolu přechodů více, pak se tyto přechodové konfigurace zobrazí ve stejné buňce podsebou seřazeny od shora v takovém pořadí v jakém jsou uvedeny ve zdrojovém souboru. Aktuální stav je označen malou šipkou z levé strany tabulky a zvýrazněn modrou barvou. Symbol nacházející se pod aktuální pozicí čtecí hlavy je rovněž zvýrazněn modrou barvou. Přechodové konfigurace, které se budou provádět v následném kroku

16

3.3.2. Spuštění simulace Turingova stroje výpočtu jsou zvýrazněny barvou červenou. Všechny ostatní prvky tabulky jsou vykresleny barvou černou.

3.3.2. Spuštění simulace Turingova stroje Z tlačítek je kromě výběrových tlačítek aktivní pouze Zapiš na pásku. Turingův stroj se nyní nachází v iniciálním stavu a vlastní simulace začíná teprve zápisem slova na pásku. Slovo, pro které chceme provádět výpočet, je třeba zapsat do textového pole, které se nachází vlevo od tlačítka Zapiš na pásku. Chceme-li zadat prázdné slovo, pak to tohoto pole zapíšeme prázdné slovo. Chcemeli zadat nějaké jiné slovo, pak toto slovo zapíšeme do tohoto pole. Je třeba dávat si pozor zda zadáváme slovo, které je tvořeno pouze znaky vstupní abecedy stroje. Zadáme-li slovo obsahující znaky, které nejsou obsaženy ve vstupní abecedě stroje, pak nás simulátor upozorní na nekorektnost vstupu. Opět je toto upozornění ve formě okna Chybové hlášení s hlášením o výskytu nepovoleného znaku. Nachází-li se ve vstupním řetězci více chybných znaků, jsme upozorněni pouze na první z nich. Zapsat na pásku lze i v případě, že již máme spuštěnou simulaci nějakého Turingova stroje na nějakém vstupní slově. Zapíšeme-li však na pásku v tomto případě, simulátor zapomene stav výpočtu stroje a tváří se, jako by se stroj před zapsáním na pásku nacházel v iniciálním stavu. Tedy počítá opět od začátku. Po úspěšném zapsání na pásku stroje se začíná vlastní simulace výpočtu Turingova stroje nad daným slovem.

3.3.3. Funkce tlačítek Přejdi a Přejdi o délku vstupu Jak již název napovídá jedná se o tlačítka sloužící pro ruční simulaci krok po kroku. Pomocí těchto tlačítek můžeme podrobně sledovat výpočet. Obě tato tlačítka jsou však použitelná pouze, jedná-li se o deterministické přechody z kofigurace do konfigurace. O simulaci nedeterministických kroků bude řeč později. Tlačítko Přejdi je svázáno s textovým polem nacházejícím se nad ním. Do tohoto pole je třeba uvést po kolika krocích chceme simulaci provádět. Tento počet musí být uveden celým číslem větším než nula. Uvedeme-li nulu pak se po kliku na tlačítko Přejdi neprovede nic, jak lze konec konců očekávat. Uvedeme-li tedy nenulový počet kroků, pak simulátor provede daný počet kroků a zastaví, či spíše čeká na další příkazy. Tlačítko Přejdi o délku vstupu funguje obdobným způsobem jako tlačítko Přejdi s tím rozdílem, že vždy přejde o počet kroků, který se rovná dálce vstupního slova. Toto tlačítko je tedy možné použít pro učení efektivity výpočtu daného Turingova stroje. V případě, že simulátor při přechodu z jedné konfigurace do jiné pomocí těchto tlačítek narazí na nedeterministickou volbu, zastaví svůj výpočet. Jak postupovat při nedeterministické volbě, bude uvedeno později.

3.3.4. Funkce tlačítek Simulace, Stop, Dokonči Tlačítka Simulace a Stop jsou vzájemně provázána. Jak se jistě dá vytušit tlačítko Simulace zapíná časovou simulaci výpočtu Turingova stroje a Stop ji zastavuje. Tlačítko

17

3.3.5. Tlačítka Náhodná simulace a Dokonči náhodně Simulace je závislé na textovém poli nacházejícím se nad ním. V tomto okně musí být uvedeno časové zpoždění v milisekundách mezi jednotlivými kroky výpočtu. Pokud časovou simulaci nezastavíme, někdy během výpočtu tlačítkem Stop bude její výpočet pokračovat dokud stroj neakceptuje nebo nezamítne. Napíšeme-li tedy Turingův stroj, který by pro nějaké slovo cyklil, pak bude simulace vypočtu nad tímto slovem pokračovat do nekonečna. Tlačítko Dokonči funguje v podstatě stejně jako tlačítko Simulace, s tím rozdílem že se zobrazuje pouze výsledek výpočtu tedy konečný stav a obsah pásky po konci výpočtu. Bude-li však výpočet cyklit, pomůže pouze vypnutí a opětovné zapnutí prohlížeče. Tato tlačítka jsou rovněž použitelná pouze pro deterministické přechody. Narazíli simulátor po stisku těchto tlačítek na nedeterministikou volbu, stejně jako v předchocím případě zastaví svůj výpočet a vyčkává dalších rozkazů. Jak postupovat při nedeterministické volbě viz další dvě podkapitoly.

3.3.5. Tlačítka Náhodná simulace a Dokonči náhodně Mezi tlačítka umožňující simulaci nedeterministických voleb v nedeterministických Turingovych strojich patří Náhodná simulace a Dokonči náhodně. Tato tlačítka jsou jen zvláštní verzí tlačítek Simulace a Dokonči. Tlačítko Náhodná simulace je rovněž svázáno s tlačítkem Stop a textovým polem udávajícím zpoždění. Rozdíl mezi těmito tlačítky spočívá pouze v reakci na nedeterministickou volbu. Jak již název napovídá, narazí-li tato tlačítka na nedeterministickou volbu, tak náhodně vyberou některý z možných přechodů a pokračují ve výpočtu právě tímto přechodem. Tato tlačítka se samozřejmě dají použít i pro výpočty deterministických Turingových strojů, neboť, jak bylo řečeno v teoretické části, každý deterministický Turingův stroj je zároveň nedeterministickým Turingovým strojem. Při tomto použití se pak tato tlačítka chovají naprosto stejným způsobem jako jejich „nenáhodné“ protějšky.

3.3.6. Tlačítka ve spodním bílém poli Po úspěšném zápsaní nějakého řetězce na pásku se v dolním bílém poli objeví tlačítko (tlačítka) přechodu. Na tomto tlačítku je vždy uvedeno přechodové pravidlo, které lze v dané konfiguraci stroje právě provést. Po kliknutí na toto tlačítko se provede právě jeden krok výpočtu a to takový krok, který byl uvedený jako název tohoto tlačítka. V případě nedeterministické volby se pro každé možné přechodové pravidlo uvedené ve zdrojovém souboru zobrazí právě jedno tlačítko, provádějící tento výpočtový krok. . Tato tlačítka tedy nechávají uživateli kontrolu nad nedeterministickou volbou při simulaci nějakého stroje. Zároveň rovněž umožňují uživateli lepší přehled o právě prováděných krocích výpočtu. Tato tlačítka lze použít jak pro deterministická, tak pro nedeterministická přechodová pravidla.

18

3.4. Instalace simulátoru na novém URL

3.4. Instalace simulátoru na novém URL Chceme-li instalovat tento simulátor na nějaké nové webové stránce, pak si musíme nejprve stáhnout javojský archiv archiv.jar. Tento archiv obsahuje všechny potřebné informace a proto není potřeba stahovat nic jiného. Po stažení jej musíme nakopírovat do příslušného adresáře. Pro vlastní provoz simulátoru je třeba nejprve z archivu archiv.jar extrahovat soubory mujapplet.html, MujApplet.crt a celý adresář tm. Všechny tyto věci se musí nacházet ve stejném adresáři jako javojský archiv archiv.jar. Tímto je instalace hotova a simulátor je připraven ke spustění.

19

Kapitola 4 Implementace Webového Turingova stroje

simulátoru

Simulátor Turingova stroje je vlastně počítač simulovaný v počítači. Jako takový se skládá z několika vzájemně propojených částí a to ze syntaktického analyzátru, výkoné jednotky, zobrazovacího zařízení a ovládacího panelu. 1.

Syntaktickou analýzu provádí třídy v balíčku parser.

2.

Výkonou jednotku simulátoru představuje balíček turing.

3.

Zobrazování stavu výpočtu zajišťuje balíček paint

4.

Ovládací prvky a propojení všech výše zmíněných částí zajišťuje balíček main

4.1. Syntaktický analyzátor, balíček parser Syntaktický analyzátor slouží ke správné interpretaci zápisu Turingova stroje v souboru a jeho nahrání do vnitřní struktury simulátoru. Případné chyby v tomto zápisu by měl syntaktický analyzátor identivikovat a upozornit na ně autora zdrojového souboru. Tento syntaktický analyzátor nedokáže odhalit všechny chyby, kterých se může dopustit pisatel, ale ty nejzákladnější a nejčastěji se vyskytující ano.

4.1.1. Obecný postup při syntaktické analýze Syntaktický analyzátor vždy načte celý řádek. Poté určí, zda daný řádek obsahuje středník. Neobsahuje-li daný řádek středník, pak načte další celý řádek, připojí jej za konec dříve načteného řádku a opět zkontroluje přítomnost středníku. Tento postup opakuje dokud nenarazí na řádek, který tento středník obsahuje. Po načtení řádku se středníkem vymaže analyzátor všechny bílé znaky z řetězce. Následně určí význam řádku, tedy zda se jedná o definici devítice, množiny stavů apod. Podle určení významu řádku pak tento řádek postupně rozděluje do významových částí a zároveň kontroluje správnost zápisu.

20

4.1.2. Součásti syntaktického analyzárou Správně zapsaná data v řádce předá výkonné jednotce simulátoru jako parametry. Z těchto parametrů výkoná jednotka simulátoru sestavý Turingův stroj, který se bude simulovat.

4.1.2. Součásti syntaktického analyzárou Jak bylo řečeno výše, je syntaktický analyzátor realizován balíkem parser, respektive třídami v něm obsaženými. Balík parser obsahuje dvě třídy pro vlastní syntaktickou analýzu a několik výjimek pro odhalení chyb v zápise. Třídy určené pro syntaktickou analýzu a načtení do výkonné jednotky simulátoru: • NactiZeSouboru • ParserElement Výjimky určené pro odhalování chyb v zápise Turingova stroje: • NeznamySymbolException • NotEnoughtSegmentException • PrepisujeLevouZnackuException • OdLeveZnackyDolevaException

4.1.3. Popis jednotlivých tříd syntaktického analyzátoru Tato část je věnována podrobnému popisu jednotlivých tříd obsažených v balíku parser. Nejprve se budeme zabývat výjimkami, protože jejich význam je důležitý pro pochopení vlastní činnosti syntaktického analyzátoru. 4.1.3.1. Výjimka NotEnoughtSegmentException Tato výjimka je vyvolána, pokud se v definici devítice nachází nesprávný počet částí, tedy pokud v devítici není některá část uvedena, nebo je-li uvedena některá část navíc. Výjimka při svém vyvolání vrací textovou zprávu, která obsahuje popis chyby a číslo řádku, na kterém byla odhalena. 4.1.3.2. Výjimka NeznamySymbolException Tato výjimka, jak již název napovídá, by měla upozornit na syntaktickou chybu způsobenou symbolem, který nebyl dříve v souboru definován. Tato výjimka se tedy vyvolá vždy, pokud analyzátor při analýze přechodové funkce narazí na symbol (jméno), který nebyl uveden v hlavičce souboru, nebo pokud je uveden na špatném místě. Na špatném místě se například nachází stav, který je uveden na místě, kde je očekáván páskový symbol apod. Tato výjimka při svém vyvolání vrací krátkou textovou zprávu. Textová zpráva vždy obsahuje číslo řádku, na kterém se chyba nachází. Může také obsahovat onen 21

4.1.3. Popis jednotlivých tříd syntaktického analyzátoru neidentifikovatelný symbol, popřípadě ještě nějakou jinou poznámku týkající se dané chyby. 4.1.3.3. Výjimka PrepisujeLevouZnackuExcetion Jméno této výjimky vychází z funkce, kterou zastává při syntaktické analýze. Je tedy vyvolána v případě, že syntaktický analyzátor narazí na přechodové pravidlo, ve kterém dochází k přepisování levé koncové značky na pásce, což definice Turingova stroje výslovně zakazuje. Výjimka PrepisujeLevouZnackuException vrací při svém vyvolání krátkou textovou zprávu, která obsahuje popis chyby a číslo řádku, na kterém k chybě dochází. 4.1.3.4. Výjimka OdLeveZnackyDolevaException Tato výjimka je vyvolána právě tehdy, když se v definici přechodové funkce nachází pravidlo, které se snaží pohnout čtecí hlavou nalevo od levé koncové značky. Výjimka OdLeveZnackyDolevaException při svém vyvolání vrací textovou zprávu, která obsahuje popis chyby a číslo řádku, na kterém byla tato chyba odhalena. 4.1.3.5. Třída ParserElement Třída ParserElement slouží k rozdělování jednotlivých řádků na části. Částí se rozumí například jméno stavu, symbol abecedy, symbol posunutí čtecí hlavy apod. Význam těchto částí a jejich správnost pak vyhodnocuje až třída NactiZeSouboru. Tato třída pracuje tak, že si zjistí polohu prvního následujícího oddělovacího znaku (standartně je jím čárka) v řetězci a celý podřetězec od začátku po tento znak vrátí jako hledanou část a svůj řetězec o tento podřetězec zkrátí. V případě, že prvním symbolem řetězce, který se má rozdělit, je jedno z uzavíracích znamének (závorka, hranatá závorka, uvozovky) vrátí jako hledanou část celý podřetězec uzavřený do těchto znamének včetně těchto znamének. Svůj pracovní řetězec opět zkrátí o tuto část. 4.1.3.6. Třída NactiZeSouboru Tato třída slouží k otevření souboru s Turingovým strojem. Je hlavní třídou v balíku parser a provádí vlastní syntaktickou analýzu souboru s Turingovým strojem. Ke své činnosti využívá výše uvedené třídy. Po otevření souboru s Turingovým stroje začíná syntaktická analýza načtením prvního řádku souboru, restektive prvních několik řádků po první středník (dále jen řádek). Následně vyhodnotí, zda se jedná o definici devítice nebo popis (jméno) Turingova stroje. Jedná-li se o popis Turingova stroje, je tento řádek zahozen a načten další. Po načtení řádku obsahující definici devítice dojde k vymazání úvodní závorky, uzavírací závorky a všeho, co se nachází za ní. Následuje rozdělení pomocí třídy ParserElement na jednotlivé části. Po kontrole počtu částí, není-li vyvolána výjimka NotEnoughtSegmentException, dojde k určení významu jednotlivých částí pro Turingův stroj. některé části jsou rovnou předány Výkonné jednotce. Zbylé části slouží k určení následujících definic.

22

4.1.3. Popis jednotlivých tříd syntaktického analyzátoru Části předané Výkonné jednotce: • Symbol levé koncové značky • Symbol prázdného políčka • Počáteční stav • Akceptující stav • Zamítající stav Po definici devítice mohou v libovolném pořadí následovat definice množiny stavů, vstupní abecedy a páskové abecedy. Další načtený řádek může tedy obsahovat jednu z těchto možností, a proto je třeba nejprve určit, o kterou z nich se jedná. Návěští řádku (tj. jméno před dvojtečkou) je porovnáno se jmény uvedenými v devítici, čímž je určen význam celého řádku. Řádek obsahující definici množiny stavů je zpracován následovně. Vymaže se první část tohoto řádku, kterou je návěští a dvojtečka, a zbytek se rozdělí pomocí třídy ParserElement na jednotlivá jména stavů. Tato jména jsou následně předána výkonné jednotce. Řádky obsahující definice vstupní a páskové abecedy jsou zpracovány obdobným způsobem jako řádek pro definici stavů. Opět je vymazáno návěští a jednotlivé znaky jsou z řádku vytaženy pomocí třídy ParserElement a následně předány výkonné jednotce. Začátek definic přechodové funkce je určen návěštím, tedy jménem přechodové funkce a dvojtečkou. Po načtení návěští přechodové funkce analyzátor ví, že dále lze zapisovat pouze přechodová pravidla. Návěští přechodové funkce je roněž vymazáno a na řádku tímto zůstává první přechodové pravidlo, které má Turingův stroj provádět. Přechodová pravidla se skládají z aktuální konfigurace, dvojtečky a přechodových konfigurací. Nejdříve se zpracovává aktuální konfigurace, tedy vezme se část řádku od začátku po první dvojtečku. Tento podřetězec je rozdělen na významové části. Řádek je poté o tuto část včetně dvojtečky zkrácen. Následuje zpracování přechodové konfigurace. Z řádku se tedy vyjme část od začátku po první dvojtečku, popřípadě středník. Je-li za přechodovou konfigurací uvedena dvojtečka, znamená to, že následuje další přechodová konfigurace. Je-li zde uveden středník, znamená to konec definice přechodového pravidla. Při zpracování přechodové konfigurace se vymažou vnější závorky, které tuto konfiguraci uzavírají, a zbytek je rozdělen na části. Výkoné jednotce se poté oznámí, že pro stav daného jména má vytvořit danou přechovou konfiguraci pod daným znakem. Následuje-li za touto přechodovou konfigurací konfigurace jiná, pak se proces zpracování přechodové konfigurace opakuje, jinak následuje načtení dalšího řádku. Při zpracovávání přechodové funkce se provádí kontrola korektnosti zápisu a definice všech použitých symbolů a jmen. Celá syntaktická analýza zápisu Turingova stroje se ukončuje v případě, že analyzátor načte řádek obsahující samotný středník.

23

4.2. Výkonná jednotka simulátoru, balíček turing

4.2. Výkonná jednotka simulátoru, balíček turing Výkonná jednotka simulátoru je ta část simulátoru, která provádí vlastní výpočet Turingova stroje nad daným vstupním slovem. Jedná se tedy o strukturu, která je sestavena z údajů od syntaktického analyzátoru a která je zobrazována pomocí zobrazovací jednotky simulátoru a řízena pomocí hlavní řídící jednotky simulátoru.

4.2.1. Části výkonné jednotky simulátoru Výkonná jednotka se skládá z hlavní výpočetní třídy TuringMachine, která provádí vlastní výpočet Turingova stroje za pomoci tříd Stav a Prechod. Pomocí výjimek a metod komunikuje s hlavní řídící jednotkou simulátoru. O vlastní výpočet se starají tyto třídy: • TuringMachine • Stav • Prechod Na vyjímečné stavy nastalé při simulaci upozorňují tyto výjimky: • JeTuVetveniException • KonecVypoctuException

4.2.2. Popis jednotlivých částí výkonné jednotky simulátoru Při popisu jednotlivých součástí výkonné jednotky simulátoru si nejprve osvětlíme funkci pomocných tříd a výjimek, aby byl popis funkce hlavní třídy tohoto balíku lépe pochopitelný. 4.2.2.1. Pomocná třída Prechod Pomocná třída Prechod je struktura, v níž je uložená přechodová konfigurace. Jedná se o jednoduchou třídu, která v sobě obsahuje informaci, jak se má stroj zachovat, budeli použito dané přechodové konfigurace. Obsahuje pouze metody pro výstup. Výstupem této třídy je pohyb hlavou, znak, který se má zapsat na pásku, a stav do kterého se má přejít. 4.2.2.2. Pomocná třída Stav V pomocné třídě Stav jsou uloženy veškeré informace, které je potřeba o stavu vědět, tedy jméno jako identifikátor stavu a asociované pole obsahující přechodovou funkci pro daný stav. Asociované pole obsahuje pro každý klíč, kterým je zde páskový symbol, pole (ArrayList) přechodů (objektů třídy Prechod), které lze provést pod daným páskovým

24

4.2.2. Popis jednotlivých částí výkonné jednotky simulátoru symbolem. Jedná-li se o deterministický přechod je toto pole vždy jednoprvkové, ale obecně může obsahovat více jak jeden přechod. Jak je tedy vidět, celá přechodová funkce Turingova stroje byla převedena do jednotlivých stavů a hlavní třída tohoto balíku se už o ni nemusí starat. 4.2.2.3. Výjimka JeTuVetveniException Výjimka JeTuVetveniException je vyvolána vždy, když výpočet narazí na nedeterministickou volbu, tedy když množina přechodů pro aktuální stav a aktuální symbol pod čtecí hlavou není jednoprvková. Tato výjimka se vyhodnocuje vždy na konci každého kroku, aby před následujícím krokem mohla řídící jednotka simulátoru adekvátně zareagovat na možný výskyt nedeterministické volby. 4.2.2.4. Výjimka KonecVypoctuException Výjimka KonecVypoctuException je vyvolána vždy, když výpočet dospěje do jednoho z konečných stavů, tedy když se po provedení kroku ocitne Turingův stroj v akceptujícím, nebo zamítajícím stavu. Jako své hlášení vrací tato výjimka textovou zprávu o tom, zda stroj akceptoval, nebo zamítl. Tato výjimka je rovněž vyhodnocována na konci každého kroku, aby simulátor nevyžadoval po konečných stavech přechod od někud někam, což by vedlo ke kolizi celého programu. 4.2.2.5. Třída TuringMachine Jak již bylo řečeno dříve, je třída TuringMachine hlavní třídou výkonné jednotky simulátoru. Obsahuje v sobě metody určené pro načtení Turingova stroje do své vnitřní struktury, pro provádění výpočtu daného Turingova stroje a také metody určené pro komunikaci s řídící a zobrazovací jednotkou simulátoru. Tato třída má o daném Turingově stroji uloženy všechny informace uvedené v devítici. Množinu stavů zde reprezentuje pole stavů (objektů třídy Stav). Je zde také uložen aktuální obsah pásky Turingova stroje ve formě řetězce (String) a poloha čtecí hlavy jako kladné celé číslo. Protože páska Turingova stroje je obecně jednosměrně nekonečná, což se špatně ukládá do proměné, je třeba využít toho, že se její obsah dá vždy reprezentovat konečným způsobem. Obsah pásky je tedy uložen v paměti jako řetězec (String) s jedním znakem prázdného políčka na konci. Dostane-li se čtecí hlava během výpočtu na poslední pole, na kterém je zapsán symbol prázdného políčka, je za celý řetězec připojen další symbol prázdného políčka, čímž se simuluje nekonečnost pásky. Třída TuringMachine ve spolupráci se syntaktickým analyzátorem načte Turingův stroj do své vnitřní struktury. Po načtení se nastaví do iniciálního stavu. Na pásce je pouze levý koncový symbol a symbol prázdného políčka, což představuje prázdný obsah pásky. Aktuálním stavem je počáteční stav a čtecí hlava se nachází na nultém políčku pásky. Stroj je tak připraven začít simulovat výpočet daného Turingova stroje.

25

4.3. Zobrazovací jednotka simulátoru Teprve když je stroj takto připraven provede se vykreslení Turingova stroje pomocí zobrazovací jednotky simulátoru. Vlastní simulace výpočtu začíná teprve ve chvíli, kdy dojde z řídící jednotky simulátoru příkaz, aby bylo zapsáno na pásku. Po změně obsahu pásky dojde k překreslení Turingova stoje zobrazovací jednotkou simulátoru. Řídící jednotce simulátoru se zase oznámí přechody, které bude možno v následujícím kroku provést, a ona vytvoří v dolním bílém poli odpovídající přechodová tlačítka. Dále již výkonná jednotka přijímá pouze povely zda má přejít do dalšího stavu, a v případě nedeterministické volby i informaci o tom, kterou z možností má ve výpočtu pokračovat. Přechod z konfigurace do jiné konfigurace je realizován jako dotaz pro aktuální stav, jaký přechod (objekt třídy Prechod) se má provést pro symbol pod čtecí hlavou. Následně je aktuální stav nahrazen stavem získaným z této struktury. Symbol na pásce je nahrazen příslušným symbolem a hlava se pohne určeným směrem. Přechod je ve třídě TuringMachine prováděn metodou prejdi(int index) kde index představuje index přechodu v poli možných přechodů v dané konfiguraci stroje. V případě deterministického přechodu řídící jednotka simulátoru nastavuje tento index automaticky na nulu. Pro nedeterministické volby pak předává takto třídě TuringMachine informaci. který přechod se má použít. Vlastní volba se tedy řeší až v řídící jednotce simulátoru, která je na nedeterministickou volbu upozorněna výjimkou JeTuVetveniException.

4.3. Zobrazovací jednotka simulátoru Zobrazovací jednotka simulátoru zprostředkovává uživateli zpětnou vazbu mezi ním a simulátorem. Pomocí ní může kontrolovat výpočet nad daným Turingovým strojem. Jasně pozná, zda Turingův stroj opravdu počítá, tak jak předpokládal, neboť má dobrý přehled o aktuální konfiguraci Turingova stroje.

4.3.1. Části zobrazovací jednotky simulátoru Zobrazovací jednotka simulátoru se skládá ze dvou dílčích částí. První částí je třída pro zobrazování pásky Turingova stroje a čtecí hlavy. Tato část se zobrazuje samostatně v horním bílém poli simulátoru. Druhou částí jsou třídy pro vykreslení množiny stavů s přechodovou funkcí (tzv. řídící jednotka stroje). Třída zobrazující pásku stroje: • PaintPasku Třídy pro zobrazení řídící jednotky stroje: • Bunka • PaintStavovaJednotka • PaintTuring

26

4.3.2. Popis jednotlivých tříd zobrazovací jednotky simulátoru

4.3.2. Popis jednotlivých tříd zobrazovací jednotky simulátoru Pásku Turingova stroje zobrazuji odděleně, neboť obsah pásky je sice vždy konečný ale libovolně dlouhý, takže by společné zobrazení řídící jednotky stroje a pásky stroje vedlo k nepřehlednosti. Buď by nebyla vidět řídící jednotka stroje, nebo aktuální pozice čtecí hlavy. Šlo by to sice udělat v jednom a přitom zachovat přehlednost zobrazení. Posouvala by se řídící jednotka a páska by zůstávala na místě. V této realizaci by však bylo nutné posouvat celým plátnem tak, aby byla řídící jednotka vždy vyditelná na stejném místě, neboť posouvání působí dosti nepřirozeně a rušivě. Vzhledem ke složitosti těchto postupů se mi rozdělení na dvě nezávislé vykreslovací procedury jeví jako nejlepší řešení. 4.3.2.1. Zobrazení pásky stroje,třída PaintPasku Páska Turingova stroje se zobrazuje jako obdélník rozdělený na čtverečky. Každý čtvereček představuje jedno políčko pásky. Čtecí hlava je zobrazena o něco větším čtverečkem než jsou políčka pásky. Třída PaintPasku si pamatuje odkaz na momentálně platný Turingův stroj. Od tohoto stroje dostává po každém kroku či jiné změně, informaci o aktuálním obsahu pásky. Třída si pak následně přepočítá velikost plátna potřebnou k vykreslení celého obsahu pásky a pásku vykreslí. Překreslování pásky provádí metoda repaint(), která je volána z hlavní řídící jednotky simulátoru. 4.3.2.2. Třída Bunka Třída Bunka je nejzákladnějším kamenem zobrazování řídící jednotky Turingova stroje. Jak bylo řečeno v kapitole 3.3.1., je řídící jednotka Turingova stroje zobrazena ve formě tabulky. Každá tabulka se musí logicky skádat z jednotlivých buňek. Formát a vzhled každé buňky má nastarosti tato třída. Každá buňka je vytvářena ve třídě PaintStavovaJednotka, která vytvoří buňku potřebné velikosti a přiřadí jí obsah. Obsahem buňky je krátký textový řetězec popisující přechodovou konfiguraci, která má být v dané buňce znázorněna. Text je zarovnán na střed buňky. Nutno podotknout, že některé zejména kratší texty (páskový symbol) se mi nepodařilo zarovnat přesně do středu, neboť javovské funkce vracející délku určitého textu v daném fontu nejsou příliš přesné. Obsahuje-li více přechodových konfigurací, jsou tyto přechodové konfigurace uvedeny podsebou. Má-li buňka výšku, do které by se vešlo více přechodových konfigurací, než kolik jich buňka skutečně obsahuje (např. má výšku na 3, ale obsahuje pouze 2), jsou tyto přechodové konfigurace rozmístěny rovnoměrně po celé buňce, tedy podsebou se stejnými rozestupy. 4.3.2.3. Třída PaintStavovaJednotka Tato třída se stará o správné zobrazení řídící jednotky Turingova stroje. Základní funkcí je vykreslení tabulky tak, aby v každém řádku byly všechny buňky stejně vysoké

27

4.4. Hlavní řídicí jednotka simulátoru, balík main a v každém sloupci stejně široké, aby se do nich vešly celé popisy přechodových konfigurací. Základní funkci třídy PaintStavovaJednotka realizují dvě metody vymer a draw. Metoda vymer prozkoumá Turingův stroj, který má být simulován, a metoda draw jej podle spočítaných velikostí vykreslí. Metoda vymer nejprve vytvoří příslušný počet buňek (objektů třídy Bunka, dále jen buňka). Poté každé buňce přiřadí příslušný textový obsah. Není-li pro určitou buňku obsah definován, neexistuje přechod pro daný stav a páskový symbol, přiřadí buňce několik pomlček. V následujících krocích tato metoda projde všechny buňky. Každé se zeptá na šířku a výšku, kterou potřebuje buňka pro své úplné bezchybné vykreslení, respektive kolik přechodových konfigurací obsahuje a délku zápisu nejdelší z nich. Z těchto údajů určí pro každý řádek a každý sloupec minimální rozměry tak, aby byly bezchybně vykresleny všechny buňky na daném řádku a v daném sloupci. Tyto rozměry posléze nastaví buňkám jako jejich výšku a šířku. Tato metoda se provádí v konstruktoru této třídy. Metoda draw už pouze vykresluje jednotlivé buňky za sebe, jak náleží. Při vykreslování se každé ptá, zda neobsahuje jméno aktuálního stavu, symbolu na pásce nebo přechodovou konfiguraci, která se bude v následném kroku provádět. Tyto buňky pak vykreslí jinou barvou než všechny ostatní. 4.3.2.4. Třída PaintTuring Tato třída je hlavní třídou zobrazování řídící jednotky Turingova stroje. Od ní se ostatní třídy dozví, který Turingův stroj bude vykreslován. Stará se o plátno, na které se má Turingův stroj vykreslit, a kdy má být vykreslen. Tato třída je pak sama řízena z hlavní řídící jednotky simulátoru. Přijme-li tato třída nový Turingův stroj, nejprve vytvoří nový objekt třídy PaintStavovaJednotak. Poté se zeptá na velikost zobrazení daného Turingova stroje a podle toho zvolí velikost plátna, na které se bude daný Turingův stroj vykreslovat. Následné vykreslování se provádí pomocí metody repaint(), která je volána z hlavní řídící jednotky simulátoru.

4.4. Hlavní řídicí jednotka simulátoru, balík main Je základním stavebním kamenem celého simulátoru. Hlavní řídící jednotka simulátoru zajišťuje komunikaci s uživatelem. Udává povely všem ostatním jednotkám simulátoru a vzájemně je propojuje.

4.4.1. Části řídicí jednotky simulátoru, balík main Řídící jednotka simulátoru obsahuje jednu hlavní třídu, která využívá všechny ostatní třídy v tomto balíku. Pomocné třídy v balíku main slouží jen jako podrobné definice komponent, které nebylo možné zadefinovat přímo v hlavní třídě. Vedlejší třídy balíku main jsou tyto: • MyChoice

28

4.4.2. Popis pomocných tříd řídící jednotky simulátoru • ButtonPrechod • Casovac Hlavní třída balíku main je tyto: • MujApplet

4.4.2. Popis pomocných tříd řídící jednotky simulátoru 4.4.2.1. Třída MyChoice Tato třída je potomkem třídy Choice, která v Javě slouží jako rolovací tlačítko. Na řídícím panelu simulátoru slouží tato komponenta pro výběr Turingova stroje z databáze simulátoru. Třída MyChoice je její rozšíření třídy Choice o metodu NactiVsechnyTM. Tato metoda provede načtení všech jmen Turingových strojů z databáze a jejich uložení do seznamu, který se rozbalí kliknutím na toto rolovací tlačítko. Soubory s Turingovými stroji se nacházejí v adresáři tm, který se nachází ve stejném adresáři jako javovský archiv archiv.jar. Jména souborů s Turingovými stroji se skládají z pořadového čísla a přípony tm.

0.tm 1.tm 13.tm Pořadová čísla souborů jsou vždy číslována od nuly a musí tvořit souvislou řadu, aby byly načteny všechny, neboť tato metoda načítá soubory podle názvů od nuly po jedné, dokud nenarazí na nějaké číslo, jemuž odpovídající soubor se v adresáři nenachází. Jako jméno Turingova stroje se zde bere první řádek v souboru, na kterém se může nacházet popis jazyka příjímaný Turingovým strojem nebo jeho název. Pro tento účel je vyhrazen první řádek souboru viz. kapitola 2.1.1.. Po použití rolovacího tlačítka pro výběr Turingova stroje z databáze vrátí tato třída řídící jednotce simulátoru číslo, které odpovídá pozici daného Turingova stroje v seznamu, která je shodná se jménem příslušného souboru. 4.4.2.2. Třída ButtonPrechod Pomocí této třídy se vytvářejí tlačítka, která se nacházejí ve spodním bílém poli řídícího panelu viz. kapitola 3.3.6.. Protože tato tlačítka vznikají dynamicky během simulace, bylo mnohem vhodnější pro ně definovat samostatnou třídu. Třída ButtonPrechod je potomek třídy Button. Tlačítko při svém vzniku obdrží jméno, kterým je zápis přechodového pravidla, index daného přechodového pravidla a odkaz na instanci hlavní řídící třídy MujApplet. Po stisku vrátí tlačítko hlavní řídící třídě své číslo a ta si ho nastaví jako přechodový index a přikáže výkoné jednotce simulátoru přejít pod tímto indexem. Index je proměnná,

29

4.4.3. Popis činnosti třídy MujApplet která uvádí, které z možných přechodových pravidel má být při výpočtovém kroku použito. Přechody jsou číslovány od nuly viz. kapitola 4.4.2.3. Třída Casovac Třída Casovac je potomkem třídy TimerTask. Slouží pouze k definování funkce run(), která je volaná časovačem při každém vypršení časové prodlevy a určuje, že se má provést další krok výpočtu Turingova stroje.

4.4.3. Popis činnosti třídy MujApplet Jedinou třídou, se kterou přímo komunikuje uživatel, je právě třída MujApplet. Představuje jakýsi ovládací terminál, kterým lze ovládat celý simulátor. 4.4.3.1. Hlavní funkce • Konstrukce a správa uživatelského rozhraní • Načtení souboru s Turingovým strojem a jeho předání syntaktickému analyzátoru • Předání zpracovaného Turingova stroje zobrazovací jednotce • Řízení a kontrola výpočtu výkonné jednotky simulátoru • Hlášení nastalých chyb uživateli 4.4.3.2. Konstrukce uživatelského rozhraní Tato podkapitola se bude zabývat, jakým způsobem bylo vytvořeno uživatelské rozhraní simulátoru. Na každé uživatelské rozhraní jsou kladeny určité požadavky, co se týče vzhledu a funkcionality. Jak je v Javě dobrým zvykem, byl vzhled simulátoru navržen pomocí Layout managerů. Layout managery jsou třídy, které se v aplikacích používají pro správu rozmístění komponent na panelu. Jejich funkci lze například ocenit při změně velikosti okna aplikace. Protože Layout managery jsou obecné třídy, nelze ve většině aplikací použít pouze jednoho Layout manageru, tak abychom dostali požadovaný vzhled, ale je třeba sestavit vhodou kombinaci několika vzájemně vnořených Layout managerů. Seznam použitých Layout managerů • GridBagLayout • GridLayout • BorderLayout • FlowLayout

30

4.4.3. Popis činnosti třídy MujApplet GridBagLayout byl použit jako hlavní Layout manager. Rozděluje hlavní okno simulátoru na čtyři různé panely. Tyto panely jsem pojmenoval panel11, panel12, panel21, panel22, kde čísla udávají řádek a sloupec, ve kterém se který panel nachází. Zvláštností třídy GridBagLayout je, že dokáže panel rozdělit na panely různých velikostí. Pro každý panel se pochopitelně volí velikost vzávislosti na tom, k jakému účelu bude sloužit, respektive které prvky simulátoru se na něm budou nacházet. Panely panel11, panel12 a panel22 slouží jako prostor pro ovládací tlačítka a jiné ovládací prvky, proto je pro ně vyhrazen menší prostor. Panel panel21 poskytuje prostor pro zobrazovací jednotku simulátoru, a proto je mu věnována převážná část okna aplikace. Další zvláštností třídy GridBaglayout je, že dokáže fixovat šířku nebo délku zvolených panelů. Lze tedy za jejího použití zařídit, aby při zvětšení okna aplikace uživatelem do3lo ke zvětšení pouze jednoho určitého panelu. Této vlastnosti jsem využil tak, že při změně velikosti okna dojde ke zvětšení velikosti panelu panel21. V případě, že zobrazený Turingův stroj se nevejde do okna celý, je možné změnou velikosti okna aplikace zvětšit zobrazovací prostor. 4.4.3.2.1. Konstrukce panelů panel11 a panel22 Tyto panely jsou rozděleny pomocí třídy GridLayout na tři řádky. Každý řádek obsahuje další panel. Správu komponent na těchto panelech zařizuje třída FlowLayout, která naskládá dané komponenty tak, jak se vejdou a zarovná je na střed panelu. K rozdělení panelů panel11 a panel22 na dílčí části jsem přistoupil z důvodu přehlednosti, aby se ty prvky, které spolu vzájemně souvisejí, nacházely vždy ve stejné části okna aplikace. 4.4.3.2.2. Konstrukce panelu panel12 Zde je rozložení řízeno třídou FlowLayout, která všechny komponenty zarovnává na střed. Při původním návrhu se na tomto panelu některé ovládací prvky nacházely, ale v konečné fázi zůstal nevyužit. Vzhledem k možnosti budoucího funkčního rozšíření simulátoru byl v aplikaci zachován. 4.4.3.2.3. Konstrukce panelu panel21 Panel panel21 slouží jako prostor pro zobrazení pásky a řídící jednotky Turingova stroje a pro zobrazování tlačítek přechodu (tlačítka v dolím bílém poli viz. kapitola 3.3.6.). Z tohoto důvodu byl panel21 rozdělen na tři oddělené části. Rozdělení je provedeno pomocí třídy BorderLayout. Tato třída rozděluje panel na jeden hlavní, který se nachází uprostřed, a několik vedlejších, které se nacházejí okolo něj. Při změně velikosti panelu mění velikost pouze hlavní panel ve všech směrech a ostatní vždy pouze v jednom směru. O který směr se jedná, záleží na poloze daného vedlejšího panelu. Páska Turingova stroje je umístěna jako horní panel. Řídící jednotka se zobrazuje v panelu prostředním. Tlačítka přechodu se objevují v panelu spodním. Do každého z dílčích panelů je vždy vložen panel s rolovací lištou, aby bylo možno prohlížet si obsah panelu, který je větší než velikost jeho vyditelné části. Teprve na tento panel je vložen vlastní obsah, který se bude zobrazovat. 31

4.4.3. Popis činnosti třídy MujApplet 4.4.3.3. Načítání souboru s Turingovým strojem Protože applety jsou specifickým druhem aplikací i jejich načítání souborů má svá specifika. Protože simulátor bere soubory ze dvou různých zdrojů (ze své databáze a od uživatele, bylo nutné vyřešit dva rozdílné problémy. 4.4.3.3.1. Načítání souboru z databáze Jak bylo řečeno dříve, soubory s Turingovými stroji máme uloženy v adresáři tm, který se nalézá ve stejném adresáři jako balíky aplikace. Použijeme-li pro načtení souboru stejný postup jako, když se jedná o normální aplikaci, applet tento soubor nenajde, i když mu uvedeme správnou cestu, protože k jiným souborům než javovským, nemá applet obecně přístup. Jedinou možností jak appletu udat správnou cestu k souboru je říci mu, že má hledat v místě, kde se nachází jeho třídy. K tomu je důležité pro celou aplikaci vytvořit javovský archív, do kterého zahrneme i adresář, ve kterém jsou uloženy soubory, které chceme načítat. Máme-li javovský archív vytvořený, pak stačí jen do metody, která má soubory načítat, uvést tento příkaz:

br = new BufferedReader( new InputStreamReader( this.getClass().getResourceAsStream(cesta + jméno souboru) ) ); Proměná br je typu BufferedReader. Nyní lze již se souborem pracovat jako v každé jiné aplikaci pomocí proměné br. Applet je následně schopen načítat i soubory, které jsme do našeho adresáře nakopírovali i po vytvoření javovského archivu. Díky této skutečnosti stačí k rozšíření databáze Turingových strojů pouhé nakopírování souboru do adresáře tm. 4.4.3.3.2. Načítání externího souboru Pro načítání externího souboru nám poslouží třída FileDialog. Jedná se o třídu, která definuje klasické okno pro výběr souboru. Toto okno se dá jednoduše vytvořit pomocí sekvence těchto příkazů:

Frame patern = new Frame(); FileDialog fd = new FileDialog(patern,"Nejaky text",FileDialog.LOAD); fd.show(); //tato metoda nam vyberove okno zobrazi Výběr souboru pak závisí na uživateli, který daný soubor označí a svou volbu potvrdí. Který soubor uživatel chce načíst, zjistíme od dialogového okna pomocí metod

32

4.4.3. Popis činnosti třídy MujApplet getDirectory() a getFile(). Proměnnou br získáme z těchto údajů pomocí sekvence příkazů:

FileInputStream fin = new FileInputStream( fd.getDirectory() + fd.getFile() ); BufferdReader br = new BufferedReader(new InputStreamReader(fin)); Nyní by se zdálo, že po získání proměné br je možné se souborem pracovat jako v jiných aplikacích. Nicméně zůstává ještě jeden problém, kterým je povolení přístupu k souborům na disku uživatele. Jedinou možností jak zajistit, aby byl appletu povolen přístup na disk uživatele je applet podepsat. Pro podpis appletu musíte nejprve vytvořit certifikát a tento certifikát následně přiřadit k javovskému archivu appletu. Certifikát je možné vytvořit na příkazové řádce pomocí příkazu keytool[3]. Pomocí příkazu jarsigner[4] se pak celý applet podepíše. 4.4.3.4. Řízení a kontrola výpočtu výkoné jednotky simulátoru Uživatelské rozhraní by nemělo uživateli povolit provést operaci, která by v danou chvíli nebyla korektní. Z tohoto důvodu je třeba zařídit, aby tlačítka, která v dané chvíli nemohou provádět akci, nebyla aktivní, ale všechny komponenty, které akci provádět mohou, aktivní byly. Na začátku po načtení nějakého Turingova stroje do simulátoru jsou aktivní pouze tlačítka pro výběr Turingových strojů a tlačítko Zapiš na pásku. Tato tři tlačítka jsou jako jediná aktivní po celý běh simulátoru. Všechna ostatní tlačítka jsou v tuto chvíli vypnuta. Pro lepší pochopení postupu, kterým simulátor řídí výpočet, bude nejprve třeba si osvětlit funkci a význam několika metod a proměnných této třídy. Jedná se o proměné: • index • jeZapnutyNahodnyVyber • isClickedButtonDokonci Proměná index slouží simulátoru k identifikaci přechodu, kterým má v případě nedeterministické volby pokračovat výpočet Turingova stroje. Index lze nastavovat pomocí metody setIndex. Pokud stroj provádí deterministický krok, je tato proměná automaticky nastavena na nulu. Automatické nastavování se provádí jako náhodný výběr z možných přechodů, je-li však možný přechod pouze jeden, pak se vždy vybere jen ten jediný možný. Proměná jeZapnutyNahodnyVyber říká simulátoru, jestli uživatel stiskl tlačítko Náhodná simulace nebo Dokonci náhodně. V takovém případě se ve chvíli, kdy simulátor narazí na nedeterministickou volbu, místo přerušení použije již dříve generátorem náhodných čísel vygenerované číslo. 33

4.4.3. Popis činnosti třídy MujApplet Proměná isClickedButtonDokonci upozorňuje simulátor, zda uživatel stiskl tlačítko Dokonči nebo Dokonči náhodně. Bylo-li stisknuto jedno z těchto tlačítek pak se vynechává zobrazování stavu Turingova stroje během výpočtu a vykreslí se až stav konečný. 4.4.3.4.1. Popis metody setVetveni Metodě setVetveni předá výkoná jednotka simulátoru pole (ArrayList) všech možných přechodů pro danou kombinaci aktuálního stavu a páskového symbolu. Smaže všechna tlačítka, která se na příslušném panelu nacházela a pro každý nový možný přechod vytvoří tato metoda nové přechodové tlačítko. Přechodová tlačítka vytváří jako instance třídy ButtonPrechod a vkládá je na vyhrazený panel. Na konci této metody se do proměné index přiřadí generátorem náhodných čísel vybrané číslo přechodu pro další krok. Toto číslo se opravdu použije pouze v případě, jedná-li se o deterministický přechod, nebo je-li zapnutý náhodný výběr. 4.4.3.4.2. Popis metody prejdi Metoda prejdi nejprve přikáže výkoné jednoce přejít pod přechodem, který odpovídá proměné index. Zjistí zda má výsledný stav zobrazit a případně jej zobrazí. Dále zkontroluje, zda je zapnutý časovač. Není-li zapnutý, pak zapne všechna tlačítka, která lze použít, jinak nedělá nic. V této části mohou být vyvolány výjimky KonecVypoctuException, JeTuVetveniException a NullPointerException. Při výjimce KonecVypoctuException dostane zobrazovací jednotka povel zobrazit výsledný stav výpočtu, všechna tlačítka až tři, jak bylo řečeno v úvodu kapitoly, se vypnou a ohlásí se uživateli výsledek výpočtu. Při výjimce JeTuVetveniException se zobrazí aktuální stav Turingova stroje. Je-li zapnutý náhodný výběr, nic dalšího se v obsluze výjimky neprovádí. Pokud není zapnutý náhodný výběr, zakáží se všechna tlačítka použitelná pouze pro deterministické přechody a tlačítko Stop a proměná isClickedButtonDokonci se nastaví tak, jako by tlačítko Dokonči nebylo stisknuto tedy na false. Při výjimce NullPointerException obdrží uživatel zprávu, že Turingův stroj se dostal do stavu, ve kterém nemůže korektně postupovat ve výpočtu, protože pro danou kombinaci aktuálního stavu a symbolu pod čtecí hlavou neexituje žádné přechodové pravidlo. Na samotném konci metody prejdi se volá medota setVetveni, jejíž funkce je popsána výše. 4.4.3.4.3. Popis metody volané po stisku tlačítka Zapiš na pásku Tlačítko Zapiš na pásku nejprve zkontroluje, zda text, který má být zapsán na pásku Turingova stroje, neobsahuje znaky, které se nenacházejí ve vstupní abecedě Turingova stroje. Nalezne-li takový znak, oznámí uživately chybu vstupu. Je-li vstupní řetězec v pořádku, pak inicializuje Turingův stroj s tímto vstupem. Zobrazovací jednotce nařídí zobrazit pásku a řídící jednotku Turingova stroje. Následně zapne všechna tlačítka, která mohou řídit jeho výpočet.

34

4.4.3. Popis činnosti třídy MujApplet 4.4.3.4.4. Popis metod volané po stisku tlačítek Přejdi a Přejdi o délku vstupu Tlačítko Přejdi nejprve vybere text napsaný v textovém poli, které slouží pro zadání počtu kroků výpočtu, které se mají provést naráz. Provede konverzi textu na číslo a zkontroluje, zda se jedná opravdu o číslo. Není-li v textovém poli zapsáno číslo, upozorní uživatele na chybný zápis počtu kroků a neprovede nic. Je-li zápis počtu kroků v pořádku, pak začne v cyklu volat metodu prejdi a zároveň v těle cyklu snižovat počet kroků, který se má ještě provést. Je-li počet kroků roven nule, pak končí svou činnost. Tlačítko Přejdi o délku vstupu pracuje stejným způsobem jako tlačítko Přejdi, pouze počet kroků nebere z textového pole, nýbrž spočítá délku vstupní slova zapsaného na pásku Turingova stroje. 4.4.3.4.5. Popis metod volané po stisku tlačítek Simulace a Náhodná simulace Tlačítko Simulace nastaví časovač na příslušnou hodnotu uvedenou v textovém poli. Pokud není v textovém poli uvedeno číslo, upozorní uživatele na nesprávný zápis počtu milisekund a jinak neprovede nic. Je-li počet milisekund uveden ve správném tvaru, pak nastartuje odpočítávání. Následně zakáže všechna tlačítka kromě tlačítka Stop, které naopak zapne. Metoda, která se má provést po každém vypršení časového limitu, je uvedena v pomocné třídě Casovac a jedná se o metodu run. Tlačítko Náhodná simulace pracuje stejným způsobem jako tlačítko Simulace, pouze ještě nastavuje promněnou jeZapnutyNahodnyVyber na hodnotu true, čímž říká simulátoru, že má v případě nedeterministické volby použít údaj z generátoru náhodných čísel. 4.4.3.4.6. Popis metody volané po stisku tlačítka Stop Tlačítko Stop je zapnuté pouze v případě, že momentálně probíhá časová simulace výpočtu Turingova stroje. V případě stisku tohoto tlačítka se zastaví časovač a všechna ostatní tlačítka jsou zapnuta. Pouze tlačítko Stop se zase samo vypne. 4.4.3.4.7. Popis metod volané po stisku tlačítek Dokonči a Dokonči náhodně Tlačítko Dokonči nastaví proměnnou isClickedButtonDokonci na hodnotu true, čímž upozorňuje simulátor, že došlo k jeho stisknutí. Následně pak v cyklu volá metodu prejdi. Tlačítko Dokonči náhodně pracuje stejným způsobem jako tlačítko Dokonči, pouze ještě před cyklem nastavuje proměnnou jeZapnutyNahodnyVyber na hodnotu true.

35

Kapitola 5 Závěr Na Internetu je dnes dostupné pomněrně slušné množství podobných simulátorů. Simulují však většinou Turingův stroj s obousměrně nekonečnou páskou. Také většina z nich nedovoluje načtení Turingova stroje z vlastního souboru. Tvoření vlastních Turingových strojů je uživateli dovoleno pouze do textového okna, nebo pomocí zvláštního editačního prostředí. Mojí snahou bylo vytvořit simulátor, který se bude co nejvíce držet formální definice, která se vyučuje na této fakultě. Tato snaha je nejvíce patrná ve formátu zápisu Turingova stroje do souboru. Simulátor tedy může být použit jako doplněk k výuce. Nezávislost vnitřní databáze simulátoru na vlastním programu umožňuje učiteli rozšiřovat a měnit její obsah bez jakéhokoliv zásahu do programu.

36

Příloha 1 Obsah archivu Všechny soubory potřebné pro spuštění simulátoru včetně základní databáze Turingových strojů, zdrojových souborů a javovské dokumentace se nacházení v souboru archiv.jar

37

Literatura [1] Černá, Křetínský, Kučera : Automaty a formální jazyky I. Brno: FI MU, 2002. [2] http://java.sun.com/j2se/1.5.0/docs/api/ [3] http://java.sun.com/j2se/1.4.2/docs/tooldocs/solaris/keytool.html [4] http://java.sun.com/j2se/1.3/docs/tooldocs/solaris/jarsigner.html

38