Katedra informatiky
Přírodovědecká fakulta
Univerzita Palackého
17. listopadu 1192/12
771 46 Olomouc

POSUDEK
BAKALÁŘSKÉ DIPLOMOVÉ PRÁCE

Název bakalářské práce: Simulátor konečných automatů a gramatik
Diplomant:  Jiří Vrtal
Autor posudku: RNDr. Arnošt Večerka							oponent 

Posudek: 

V úvodní kapitole jsou na začátku základní pojmy. Jsou zde definice z oblasti formálních jazyků a dále je zde definice gramatik. V ní je chyba v popisu pravidel gramatiky. Místo  má správně být .
Následuje popis, jak probíhá odvození slov jazyka. V souvislosti s gramatikou je obvyklejší používat pojem věta jazyka než slovo. Navíc uvedený slovní popis odvození je poměrně vágní. Lepší by bylo tento proces popsat s použitím operace derivace . 
Úvodní část pokračuje na straně 9 přehledem Chomského hierarchie gramatiky. V ní je v definici bezkontextové gramatiku uvedeno, že pravá strana pravidla je řetězec z množiny . To není definice bezkontextové gramatiky, je to jen její speciální tvar bez tzv. -ových pravidel. Bezkontextová gramatika je definována tak, že pravá strana pravidla nemá žádné omezení, je tedy řetězcem z množiny . Například http://www.cs.odu.edu/~toida/nerzic/390teched/cfl/cfg.html.
Po úvodní části se diplomant zabývá konečnými automaty a převodem nedeterministického konečného automatu na ekvivalentní deterministický konečný automat. Za nimi následuje popisu převodů mezi regulárními gramatikami a konečnými automaty. Zde v části 2.4.1 na straně 12 je poněkud nesrozumitelně popsáno vytváření přechodové funkce, kde není zřejmé, co znamená .
Ve třetí kapitole je popsáno ovládání programu uživatelem. Popis je celkem přehledný. Některé termíny zde používané by ale možná byly přijatelné v programátorském popisu, pro uživatelskou příručku vhodné nejsou. Jde o termíny:
	textbox, textboxu, textboxů - např. str. 16, 6. řádek, celkem 10 výskytů
	listbox, listboxu - např. str. 15, spodní řádek 
	groupboxu - str. 16, 4. řádek zdola
Dále pro uživatele může být matoucí zpráva "Nepřečtené slovo na pásce" (str. 16, 6. řádek, str. 18, 9. řádek zdola), když vstupní slovo se podle uživatelské dokumentace zadává to textového pole.
Poslední, 4. kapitola je programátorská dokumentace. 
Po formální stránce je textová část práce udělána pečlivě. Jsou v ní jen typografické prohřešky - častější výskyt jednopísmenových předložek na konci řádku.
Vlastní aplikace vypadá přehledně. Jako první jsem zkusil vložit regulární gramatiku popisující celá čísla. Ze zprávy o chybě vyplynulo, že jediné terminální symboly, které aplikace připouští, jsou malá písmena. To se mi zdá zcela zbytečné a navíc nepříjemné omezení. Takto se dá demonstrovat jen činnost automatů rozpoznávající syntetické řetězce z písmen. Reálnější případy, jako je rozpoznávání čísel, aplikace neumožňuje.
Jako další byla zadána jednoduchá gramatika:
	Aa
	Ab
Po zadání vstupního slova ab a spuštění procesu odvození se neobjevil žádný výstup. Bylo by vhodné, kdyby se aspoň objevila zpráva, že zadané vstupní slovo nebylo rozpoznáno.
Automat, který aplikace z této gramatiky vygenerovala, je na následujícím obrázku. 
		
Tento automat neodpovídá definici konečného automatu, která je mimo jiné uvedená přímo v bakalářské práci v části 2.2 na straně 10, neboť je v něm přechod označený prázdným řetězcem . Z definice je zřejmé, že v konečném automatu je možný přechod z jednoho stavu do druhého jen odebráním symbolu ze vstupního slova, je-li pro tento symbol v automatu příslušný přechod. V sestaveném automatu stav 2 měl být koncový a neměl zde být přechod ze stavu 2 do stavu 1.
Dále popis přechodu ze stavu 0 do stavu 1 je nečitelný. 
Poněkud nedomyšlený je algoritmus převodu automatgramatika. Pro vložený automat, který je na následujícím obrázku
	,
volba Převod automatgramatika vygenerovala složitou gramatiku s některými viditelně zbytečnými pravidly obsahující nadbytečné neterminální symboly A a B:
	SaA
	Sa
	SbB
	Sb
Nepříjemnou vlastností aplikace je skutečnost, že po sestavení automatu nelze vloženou gramatiku editovat. Snažil jsem se tuto skutečnost obejít tím způsobem, že jsem gramatiku uložil do souboru, abych ji mohl znovu načíst, s předpokladem, že po novém načtení ji bude možné editovat. Načíst se ji ale po uložení nepodařilo, jak ukazuje následující zpráva. 
	
V nabídce aplikace je volba "Nápověda". Když jsem nápovědu chtěl použít, žádnou jsem zde nenašel.
Až na uvedené nedostatky je aplikace podařená a diplomant nepochybně jejímu sestavení věnoval nepochybně hodně času. 

Navrhuji hodnocení velmi dobře.

Datum 22.1.2012

.................................................
Podpis