%%%  Vzor pro použití makra pro diplomovou práci
%%%  (c) Miloą Kudělka, David Skoupil, březen 1998
%%%  Vzorový soubor revidován a doplněn v září 2001
%%%  (c) 2001 Vilém Vychodil, <vilem.vychodil@upol.cz>
%%%
%%%  Po přeložení programem CSLaTeX (třikrát) je potřeba použít
%%%  program DVIPS a takto získaný PostScriptový soubor vytisknout
%%%  na PostScriptové tiskárně nebo pomocí programu GhostScript.
%%%
%%%  Rovněž je možné použít program DVIPDFM a vytvořit z dokumentu
%%%  soubor ve formátu PDF včetně hypertextových odkazů.

%%% Deklarace hlavičky dokumentu, použijte písmo velikosti 12 bodů.
\documentclass[12pt]{article}

\usepackage{czech}
\usepackage[cp1250]{inputenc}
\usepackage{enumerate}
\usepackage[figures]{updiplom}
\usepackage{graphicx}

\DeclareGraphicsRule{.JPG}{eps}{*}{`jpeg2ps #1} 

\usepackage{epsfig}
\usepackage{mflogo} 

%%% Parametry pro vytvoření úvodních stránek. Makrem \subtitle je možné
%%% vytvořit druhý řádek v názvu diplomové práce.
\title{Simulátor konečných automatů a gramatik.}

\author{Jiří Vrtal}

\year{2012}

\date{7. ledna 2012}

%%% Pomocí \docinfo je možné vytvořit název pro PDF dokument, zpravidla je
%%% dobré použít předcházející název, ale bez diakritiky. Možné je však zvolit
%%% úplně jiný výstižný název. Při tvorbě PostScriptu bude příkaz ignorován.
\docinfo{Jiří Vrtal}{simulatorkonecnychautomatu}

%%% Vytvoření anotace. Pouze jeden odstavec!
\annotation{Cílem práce je vytvoření aplikace pro demonstraci kroků výpočtu konečného automatu a kroků odvození slova ze zadané gramatiky.}

%%% Text poděkování. Pouze jeden odstavec!
\thanks{Děkuji všem, kteří přispěli k výsledné podobě této práce. Zvláště pak vedoucímu bakalářské práce Mgr. Petru Osičkovi za její vedení a cenné rady.}

%-------------------------------------------------------------------------------
\begin{document}
%%% Vytvoření úvodních stránek, obsahu a seznamu tabulek a obrázků.
\maketitle

\newpage
%%% Text diplomové práce.
\section{Úvod}
\subsection{Zadání bakalářské práce}
Cílem práce je vytvoření aplikace pro demonstraci kroků výpočtu konečného automatu a kroků odvození slova ze zadané gramatiky. Aplikace by měla umět převést zadaný nedeterministický konečný automat na deterministický konečný automat, zadanou regulární gramatiku na konečný automat a naopak. Uživatel by měl mít možnost jednoduše editovat přechodovou funkci zadaného konečného automatu a množinu pravidel u zadané gramatiky.

\newpage
\section{Základní pojmy}
V této části jsou uvedeny základní definice nutné pro práci s aplikací. Všechny definice jsou převzaty z \cite{martinek}.
\newline
\newline
\noindent{\bf{Def{}inice 2.1}}
\textit{Abecedou} nazveme libovolnou konečnou neprázdnou množinu. Její prvky nazýváme \textit{symboly}.
\newline
\newline
\noindent{\bf{Def{}inice 2.2}}
\textit{Řetězem (slovem)} {\it v} nad abecedou $X$ rozumíme libovolnou konečnou posloupnost symbolů z $X$.
\newline
Číslo {\it n} nazýváme délkou řetězu {\it v} a píšeme $\vert v \vert = n$.
\newline
\textit{Prázdným řetězem} nazýváme řetěz délky 0, který značíme $\varepsilon$.
\newline
\newline
\noindent{\bf{Def{}inice 2.3}}
Množinu všech řetězů nad abecedou $X$ značíme $X^*$ a nazýváme ji \textit{uzávěrem množiny} $X$. Jestliže z $X^*$ odebereme prázdný řetěz, dostaneme \textit{pozitivní uzávěr množiny} $X$, který značíme $X^+$. 
\newline
\newline
\noindent{\bf{Def{}inice 2.4}}
\textit{Jazykem} $L$ nad abecedou $X$ nazýváme libovolnou podmnožinu množiny $X^*$. Říkáme, že jazyk $L$ je 
\newline - \textit{prázdný}, jestliže $L$ = 0,
\newline - \textit{konečný}, jestliže obsahuje konečně mnoho slov,
\newline - \textit{nekonečný}, jestliže obsahuje nekonečně mnoho slov. 
\newline
\subsection{Gramatika}
Gramatika je soustava pravidel, podle kterých se vytváří právě všechny řetězy daného jazyka.
\newline
\newline
\noindent{\bf{Def{}inice 2.5}} 
\textit{Gramatikou} nazýváme uspořádanou čtveřici $G=(N, \Sigma, P, S)$, kde
\begin{itemize}
\item $N$ je abeceda se symboly zvanými \textit{neterminály},
\item $\Sigma$ je abeceda se symboly zvanými \textit{terminály}, splňující podmínku $ N \cap \Sigma = \emptyset$,
\item $P$ je konečná množina \textit{pravidel} a platí $P \subseteq (N \cup \Sigma)^\ast N(N \cup
\Sigma)^\ast$. Její prvky tvaru $(\alpha, \beta)$ píšeme jako
$\alpha \to \beta$,
\item $S$ je \textit{počáteční symbol (neterminál)} a platí $S \in N$.
\end{itemize}
Gramatika umožňuje odvození všech slov patřících do daného jazyka. Odvozování probíhá tak, že na předem daný počáteční symbol aplikujeme příslušné přepisovací pravidlo, na získaný řetězec se znovu aplikuje vhodné pravidlo z množiny přepisovacích pravidel, a to tak dlouho dokud se nevygeneruje požadované slovo skládající se pouze z terminálních symbolů. Jazyk generovaný gramatikou se skládá ze všech terminálních řetězů, jež lze odvodit z počátečního symbolu pomocí pravidel dané gramatiky.
\subsubsection{Chomského hierarchie gramatik}
Lingvista Noam Chomsky rozdělil gramatiky do čtyř skupin na základě různých omezení tvaru pravidel.
\newline
Chomského hierarchie rozlišuje tyto typy gramatik:
\begin{itemize}
\item \textbf{typ 0} 
\newline Libovolná gramatika je gramatikou typu 0; na tvar pravidel se nekladou žádné omezující požadavky. 
\item \textbf{typ 1} 
\newline Gramatika $G$ je typu 1 (nebo též \textit{kontextová}), jestliže pro každé její pravidlo $\alpha \to \beta \in P$ platí, $\alpha=\gamma_1  A \gamma_2$  a $\beta=\gamma_1  \delta \gamma_2$  ,kde $\gamma_1 ,\gamma_2$  $\in (N \cup \Sigma)^\ast$, A $\in $N$, \delta \in (N \cup \Sigma)^+$. Jestliže se v množině pravidel vyskytuje pravidlo $S\to \varepsilon$, pak se $S$ nesmí vyskytovat na pravé straně žádného pravidla gramatiky $G$. 
\item \textbf{typ 2} 
\newline Gramatika $G$ je typu 2 (nebo též \textit{bezkontextová}), jestliže pro každé její pravidlo $\alpha \to \beta \in P$ platí, $\alpha \in$ $N$ a $\beta \in (N \cup \Sigma)^+$. Jestliže se v množině pravidel vyskytuje pravidlo $S\to \varepsilon$, pak se $S$ nesmí vyskytovat na pravé straně žádného pravidla gramatiky $G$.
\item \textbf{typ 3}
\newline Gramatika $G$ je typu 3 (nebo též \textit{regulární}), jestliže pro každé její pravidlo $\alpha \to \beta \in P$ platí, $\alpha \in$ $N$ a $\beta \in \Sigma \cup \Sigma \cdot N$. Jestliže se v množině pravidel vyskytuje pravidlo $S\to \varepsilon$, pak se $S$ nesmí vyskytovat na pravé straně žádného pravidla gramatiky $G$.
\end{itemize}
\subsubsection{Příklad regulární gramatiky}
Uvažujme regulární gramatiku $G=(N, \Sigma, P, S)$, kde
\newline $ N = \{S,A,B\}$,
\newline $ \Sigma = \{a,b\}$,
\newline a $P$ obsahuje pouze pravidla:
%\begin{itemize}
\newline $S \to aA$  
\newline $A \to aB|a$
\newline $B \to aA|b$ 
%\end{itemize}
\newline Pak je v gramatice $G$ pro slovo $aaaab$ následující odvození:
\newline $S \Rightarrow aA \Rightarrow aaB \Rightarrow aaaA \Rightarrow aaaaB \Rightarrow aaaab.$
\newpage Jazyky generované regulárními gramatikami jsou právě jazyky rozpoznatelné konečným automatem.
\newline 
Pokud je pro každé slovo nejvýše jeden postup generování, gramatika je jednoznačná.
\subsection{Konečné automaty}
Konečný automat je teoretický výpočetní model, reprezentující jednoduchý výpočetní stroj, který se vždy nachází v jednom ze svých stavů. Z těchto stavů přechází pomocí přechodových funkcí do stavů následujících při současném čtení vstupních symbolů. Množina stavů je konečná, konečný automat nemá žádnou další paměť, automat zná pouze aktuální stav, ve kterém se nachází, a přechodové funkce pro všechny stavy. Konečný automat se skládá z konečně-stavové řídící jednotky, vstupní pásky a čtecí hlavy, která se po pásce pohybuje. Na pásce jsou zapsány symboly vstupní abecedy, které tvoří vstupní slovo. Před začátkem výpočtu se automat nachází v počátečním stavu a čtecí hlava je nastavena na levém krajním políčku pásky. Automat poté v každém kroku na základě přečteného symbolu z pásky a aktuálního stavu, ve kterém se nachází, provede přechod do nového stavu a čtecí hlava se posune o jedno políčko doprava. Činnost konečného automatu končí v okamžiku, kdy byl proveden poslední možný krok výpočtu, tj. když byl přečten poslední symbol vstupního slova nebo pokud se automat "zasekne" tzn. v okamžiku kdy pro aktuální stav a čtený symbol nemá přechodovou funkci. Jazyky rozpoznatelné konečnými automaty jsou právě jazyky generované regulárními gramatikami.\cite{bartunek,martinek}.
\subsubsection{Deterministický konečný automat}
\noindent
{\bf{Def{}inice 2.6}} Konečný automat definujeme jako
uspořádanou pětici $(Q, \Sigma, \delta, q_0, F)$, kde
\begin{itemize}
\item $Q$ je konečná neprázdná množina s prvky nazývanými {\it stavy},
\item $\Sigma$ je abeceda nazývaná {\it vstupní abeceda},
\item $\delta:Q \times \Sigma \to Q$ je {\it přechodová funkce},
\item $q_0$ je prvek z množiny $Q$ a je nazýván {\it počáteční stav},
\item $F \subseteq Q$ je množina {\it koncových stavů}.
\end{itemize}
\subsubsection{Nedeterministický konečný automat}
\noindent {\bf{Def{}inice 2.7}} Nedeterministický konečný
automat definujeme jako uspořádanou pětici $(Q, \Sigma, \delta, q_0,
F)$, kde
\begin{itemize}
\item $Q$ je konečná neprázdná množina s prvky nazývanými {\it stavy},
\item $\Sigma$ je abeceda nazývaná {\it vstupní abeceda},
\item $\delta:Q \times \Sigma \to 2^Q$ je {\it přechodová funkce},
\item $q_0$ je prvek z množiny $Q$ a je nazýván {\it počáteční stav},
\item $F \subseteq Q$ je množina {\it koncových stavů}.
\end{itemize}
\subsection{Vztah nedeterministických a deterministických automatů}
Deterministický konečný automat má konečné množství stavů a každý přechod je jednoznačný tj. neexistuje více možností přechodu z daného uzlu do jiných uzlů. Nedeterministický konečný automat tuto podmínku nerespektuje, je zde tedy více možností, kam z daného uzlu při daném vstupu přejít. Je dokázáno, že oba druhy automatů jsou stejně výpočetně silné a lze je mezi sebou převést.\cite{jancar}
\subsubsection{Převod nedeterministického automatu na deterministický}
Ke každému nedeterministickému konečnému automatu $A=(Q, \Sigma, \delta, q_0, F)$ lze sestrojit ekvivalentní deterministický konečný automat
A’= (Q’, $\Sigma$, {$\delta$}’, {$q_0$}’, F’), tedy $L(A)$=$L$(A’) \cite{martinek}.
\newline Postup převodu:
\begin{itemize}
\item[-] Q’ je množina všech podmnožin stavů z $Q$, tj. Q’=\{$M|M$ $\subseteq Q$ \}=$P(Q)$.
\item[-] {$q_0$}’ = $\{q_0\}$.
\item[-] F’ je množina všech stavů z Q’, které obsahují (jako množiny) některý stav z $F$, tj. F’=\{$K$ $\in$ Q’$|K$ $\cap$ $F$ $\ne \emptyset$ \}.  
\item[-] Přechodová funkce {$\delta$}’ je definována následovně: Pro všechna $K$,$\widetilde{K}$ $\in$ Q’ a všechna $a$ $\in \Sigma$ klademe {$\delta$}’($K,a$)= $\widetilde{K}$, právě když 
\begin{displaymath}
\bigcup_{q \in K}
\delta(q,a)
= \widetilde{K}.
\end{displaymath}
\end{itemize}
\subsection{Vztah konečných automatů a regulárních gramatik}
\begin{itemize} 
\item Jazyky rozpoznávané konečnými automaty jsou generovány regulárními gramatikami.
\item Jazyk rozpoznatelný konečným automatem je jazykem typu 3 viz Chomského hierarchie.
\item Každý jazyk typu 3 je rozpoznatelný nějakým konečným automatem.
\end{itemize}
\subsubsection{Převod regulární gramatiky na konečný automat}
Ke každé regulární gramatice $G=(N, T, P, S)$ existuje konečný automat $A=(Q, \Sigma, \delta, q_0, F)$ takový, že $L(A)$ = $L(G)$. Regulární gramatika $G$ se převede na konečný automat $A$, který rozpoznává stejný jazyk. Automat $A$ se vytváří podle následujících pravidel\cite{jancar2}:
\begin{itemize}
\item Stavy $Q$ automatu $A$ se ztotožní s neterminálními symboly $N$ gramatiky $G$. Ke stavům automatu $A$ se přidá ještě stav $K$ takový, že tento stav neodpovídá žádnému neterminálnímu symbolu v $G$, tj. $Q = N\cup\{K\},
\newline K\neq N$.
\item Počáteční stav $q_0$ je shodný s počátečním symbolem $S$ gramatiky $G$.
\item Abeceda $\Sigma$ bude shodná s terminálními symboly $T$.
\item Koncové stavy $F$ jsou určeny takto:
\begin{itemize}
\item[-] $F=\{S,K\}$ když $(S\to \varepsilon)\in P$,
\item[-] $F=\{K\}$ když $(S\to \varepsilon)\notin P$.
\end{itemize}
\item Přechodová funkce $\delta$ se vytváří podle následujících pravidel:
\begin{itemize}
\item[-] $\delta(B,a)=C$ pokud $B\to aC \in P$,
\item[-] $\delta(B,a)=K \wedge K \in F$ pokud $B\to a \in P$,
\item[-] $\delta(K,\ast)=\emptyset$, tj. $q_0\in F$, pokud $S\to \varepsilon \in P$. 
\end{itemize}   
\end{itemize} 
\subsubsection{Převod konečného automatu na regulární gramatiku}
Ke každému konečnému automatu $A=(Q, \Sigma, \delta, q_0, F)$ existuje taková regulární gramatika $G=(N, T, P, S)$, že $L(G)$ = $L(A)$. Největší důraz je kladen k převodu přechodové funkce automatu na přepisovací pravidla gramatiky. Gramatika se tvoří následujícím způsobem\cite{jancar2}:
\begin{itemize}
\item Neterminální symboly gramatiky budou stavy automatu, tj. $N=Q$,
\item Množina terminálních symbolů bude abeceda automatu, tj. $T=\Sigma$,
\item Počáteční symbol gramatiky bude počáteční stav automatu, tj. $S=q_0$,
\item Přepisovací pravidla gramatiky pak budou mít následující tvar:
\begin{itemize}
\item[-] $B\to aC \in P$ když $\delta(B,a)=C$,
\item[-] $B\to a \in P$ když $\delta(B,a)=K \wedge K \in F$,
\item[-] $S\to \varepsilon \in P$ když $q_0\in F$,
\end{itemize}
\end{itemize}
kde $a \in \Sigma$ a $B, C, K \in Q$.
\subsection{Reprezentace automatu}
Nejpoužívanějším a nejvíce názorným způsobem reprezentace konečných automatů je grafická reprezentace pomocí stavového diagramu (viz obrázek 1). Stavový diagram je tvořen množinou vrcholů (uzlů), z nichž každý představuje určitý stav automatu, a orientovanými hranami mezi těmito vrcholy. Hrany jsou ohodnoceny symboly vstupní abecedy. Jestliže z vrcholu $0$ do vrcholu $1$ vede hrana s ohodnocením $a$, pak konečný automat ze stavu $0$ po přečtení symbolu $a$ přejde do stavu $1$.   
\begin{figure}[ht]
	\epsfxsize=14cm
	\centerline{\epsfbox{./obr/form7.eps}}
	\caption{Reprezentace automatu}
\label{reprezentaceautomatu}
\end{figure}

\newpage
\section{Uživatelská příručka}
Uživatelská příručka je určena běžným uživatelům této aplikace. Obsahuje popis úkonů proveditelných v aplikaci a rovněž detailně popisuje uživatelské rozhraní. Pro bezproblémové využití této aplikace je nezbytná znalost problematiky konečných automatů a gramatik.

\medskip
Aplikace je primárně určena k podpoře výuky a zvládnutí učiva při studiu teoretické informatiky zvláště problematice konečných automatů, vztahy mezi deterministickými a nedeterministickými konečnými automaty a jejich vztahům k regulární gramatice. Tato aplikace umožní uživatelům ověřit si již získané znalosti této látky.

\subsection{Systémové požadavky}
Jedná se o 32-bitovou aplikaci určenou pro operační systém Microsoft Windows. Doporučená minimální hardwarová konfigurace: procesor Intel Pentium III nebo kompatibilní, 256 MB operační paměti, 100 MB volného místa na pevném disku.
 
\subsection{Popis instalace}
Instalaci programu uživatel provede vložením CD do mechaniky a spuštěním instalačního souboru setup.exe z adresáře {\tt SETUP}. Následně se postupuje podle pokynů instalátoru.

\subsection{Odinstalace programu}
Pro odinstalování programu z počítače postupujeme opět standardním způsobem. Volbou {\tt Start->Ovládací panely->Přidat nebo odebrat programy->Simulátor konecnych automatu->Odebrat}.
Poté budeme vyzváni, zda chceme program skutečně odinstalovat. Potvrzením dojde k odinstalování programu.

\subsection{Ovládání aplikace}
\subsubsection{Hlavní formulář aplikace}
Po spuštění aplikace se zobrazí hlavní formulář, který je zobrazen na (obrázku 2).
Součástí hlavního formuláře je standartní menu s nabídkou pro obsluhu aplikace a okno se záložkami.
\begin{figure}[ht]
	\epsfxsize=14cm
	\centerline{\epsfbox{./obr/form1.eps}}
	\caption{Hlavní formulář aplikace}
\label{hlavniformular}
\end{figure}
\subsubsection{Standartní menu}
\begin{itemize}
\item Soubor
\begin{description}
\item [Nový] - po stisknutí této položky se vynulují všechny zadané údaje. Tato položka má klávesovou zkratku Ctrl + N.
\item [Otevřít] - po výběru této položky se zobrazí okno pro otevření automatu nebo gramatiky ze souboru. Soubory mají příponu dle typu .automat nebo .gramatika. Tato položka má klávesovou zkratku Ctrl + O. 
\item [Uložit] - po výběru této položky se zobrazí okno pro uložení automatu nebo gramatiky do souboru.Okno lze vyvolat klávesovou zkratkou Ctrl + S.
\item [Konec] - Položka uzavře aplikaci. Stejnou funkci má i klávesová zkratka Alt + F4.
\end{description}
\item Algoritmy
\begin{description}
\item [Převod gramatika $\to$ automat] - algoritmus pro převedení zadané gramatiky na automat. Výsledek převodu je znázorněn pomocí stavového diagramu, který je představován orientovaným grafem.
\item [Převod NFA $\to$ DFA] - algoritmus převádějící zadaný automat do deterministického tvaru. V záložce "Deterministický automat" po zadání testovaného slova do textboxu  "Zadej testované slovo" ověří, zda automat přijme vstupní slovo. Do listboxu "Použitá pravidla" zároveň vypíše posloupnost kroků výpočtu konečného automatu. V průběhu výpočtu automatu je zvýrazněna šipka mezi stavy. Pro krokování je možno kliknout v listboxu použitých pravidel na jakýkoliv přechod a v grafu je zvýrazněn adekvátní přechod. Pokud se při čtení zadaného slova dostane automat do stavu, ze kterého nemá zadanou přechodovou funkci, vypíše nepřečtenou část vstupního slova do textboxu "Nepřečtené slovo na pásce".
\item [Převod automat $\to$ gramatika] - algoritmus převádí automat zadaný v záložce "Automat" na regulární gramatiku. 
\end{description}
\end{itemize}
\subsubsection{Okno se záložkami}
\begin{itemize}
\item Záložka "Automat" umožňuje uživateli zadávat a editovat přechodovou funkci konečného automatu.
\item Záložka "Deterministický automat" zobrazuje výsledek převodu nedeterministického automatu na deterministický a zároveň slouží k demonstraci kroků výpočtu konečného automatu.
\item Záložka "Gramatika" umožňuje zadávání a editaci množiny pravidel regulární gramatiky. Umožňuje také odvození slova ze zadané gramatiky.
\end{itemize}
\subsubsection{Funkčnost v záložce "Automat"}
Konečný automat je znázorněn pomocí stavového diagramu, který je představován orientovaným grafem. V této záložce lze zadávat automat deterministický i nedeterministický. Automat můžeme načíst ze souboru po stisknutí položky v menu {\tt Soubor->Otevřít} nebo můžeme automat zadat ručně. Stav automatu se zadává dvojklikem levého tlačítka myši na plochu v záložce "Automat". Jména stavů jsou čísla, která jsou generována automaticky. Typ stavu je určen barvou zadaného stavu dle legendy stavů. Editace stavu se provádí přes dialogové okno (viz.obrázek 3), které se zobrazí po stisknutí pravého tlačítka myši do editovaného stavu a zvolení typu stavu v groupboxu a potvrzení stiskem tlačítka $OK$. Stavy můžeme odebírat nebo posunovat, hrany se posunují se stavy.
\begin{figure}[ht]
	\epsfxsize=4cm
	\centerline{\epsfbox{./obr/form4.eps}}
	\caption{Editace stavu}
\label{editaceStavu}
\end{figure}
%\newline
Přechodová funkce automatu se zadává stisknutím a podržením levého tlačítka myši nad "výchozím" stavem a přetažením myši nad "koncový" stav, kde se po uvolnění myši zobrazí dialogové okno pro zadání znaku přechodové funkce (viz obrázek 4). Pro vytvoření "smyčky", která představuje přechodový stav, kde je "výchozí" stav stejný jako "koncový", musíme stisknout a podržet levé tlačítko myši nad "výchozím" stavem, pohnout kurzorem myši mimo vybraný stav a opět se nad tento stav vrátit a tlačítko myši uvolnit. 
\begin{figure}[ht]
	\epsfxsize=6cm
	\centerline{\epsfbox{./obr/form3.eps}}
	\caption{Přidávání znaku}
\label{pridavaniZnaku}
\end{figure}
Znak přechodové funkce je možno zadat pouze symboly označovanými malými latinskými písmeny: a, b, c,...
Po zadání znaku a potvrzení se zobrazí hrana přechodové funkce včetně terminálu odpovídajícího přechodu přechodové funkce. Pro zadání "prázdného" přechodového znaku textové políčko nevyplňujeme. Editaci přechodové funkce můžeme provést pomocí dialogového okna, které se zobrazí po stisknutí pravého tlačítka myši nad hranou přechodové funkce (viz obrázek 5).
\begin{figure}[ht]
	\epsfxsize=4cm
	\centerline{\epsfbox{./obr/form2.eps}}
	\caption{Přechodová funkce}
\label{prechodovaFunkce}
\end{figure}
\subsubsection{Funkčnost v záložce "Deterministický automat"}
Po spuštění algoritmu "Převod NFA $\to$ DFA" se v záložce "Deterministický automat" zobrazí výsledek převodu zadaného nedeterministického automatu na deterministický (viz obrázek 6). V této záložce je prováděna demonstrace kroků výpočtu konečného automatu ze zadaného slova. Vypočtený automat nelze upravovat, pouze je umožněn posun stavů.
\newpage
\begin{figure}[ht]
	\epsfxsize=12cm
	\centerline{\epsfbox{./obr/form6.eps}}
	\caption{Deterministický automat}
\label{deterministickyAutomat}
\end{figure}
\subsubsection{Demonstrace kroků výpočtu konečného automatu}
Po zadání testovaného slova do $textboxu$, stiskneme tlačítko {\tt "Otestuj slovo"}. Na ploše je zvýrazněna červenou barvou přechodová hrana odpovídající pravidlu použitému při čtení aktuálního znaku vstupního slova. Současně jsou tyto pravidla vypsána do $listboxu$ {\tt "Použitá pravidla"}. Pro ještě větší přehlednost je umožněno po skončení výpočtu vybrat kliknutím myši v uvedeném $listboxu$ libovolné pravidlo a v grafickém zobrazení automatu je zvýrazněna odpovídající hrana. 

\medskip
Po skončení výpočtu je v $textboxu$ {\tt "Výsledek"} vypsán výsledek výpočtu, a to {\tt Accepted} pro slovo, které konečný automat přijal, a {\tt Rejected} pro slovo, které zadaný konečný automat nepřijal. Pokud se automat během svého výpočtu dostane do stavu, ze kterého nemá přechodovou funkci pro aktuální znak na pásce, vypíše zbytek nepřečtené pásky do $textboxu$ {\tt "Nepřečtené slovo na pásce"}. V takovém případě automat slovo nepřijímá.    
\subsubsection{Funkčnost v záložce "Gramatika"}
Po přepnutí do záložky "Gramatika" je umožněno pomocí textboxů zadávat a editovat množinu pravidel regulární gramatiky (viz obrázek 7). Je zde také umožněno odvození slova ze zadané gramatiky. Regulární gramatiku můžeme načíst ze souboru po stisknutí položky v menu {\tt Soubor->Otevřít} nebo můžeme gramatiku zadat ručně. Zadáme do textboxů pravidla regulární gramatiky. Neterminální symboly budou označovány velkými písmeny latinské abecedy, tj. A, B, C,... Terminální symboly jsou označovány malými písmeny latinské abecedy, tj. a, b, c,... Levý $textbox$ slouží pro zadání levé části pravidla, pravý $textbox$ pro zadání pravé části pravidla. Celé pravidlo je přidáno stiskem tlačítka {\tt "Přidat pravidlo"}. Přidané pravidlo se zobrazí v $listboxu$ {\tt "Pravidla gramatiky"}. Jednotlivá pravidla lze označit kliknutím na pravidlo. Označené pravidlo lze odebrat stisknutím tlačítka {\tt "Odebrat pravidlo"}. Pro spuštění jednotlivých algoritmů je nezbytné zadat počáteční neterminál. Stiskem tlačítka {\tt "Ulož počáteční neterminál"} se uloží neterminál zadaný v $textboxu$ vedle tlačítka. 
\begin{figure}[ht]
	\epsfxsize=12cm
	\centerline{\epsfbox{./obr/form8.eps}}
	\caption{Zadávání gramatiky}
\label{zadavaniGramatiky}
\end{figure}
\subsubsection{Demonstrace kroků odvození slova ze zadané gramatiky}
Pro demonstraci kroků odvození slova ze zadané gramatiky vložíme do $textboxu$ slovo z daného jazyka a stiskneme tlačítko pro odvození slova. Do $listboxu$ {\tt "Odvození slova"} jsou vypsány kroky odvození zadaného slova z gramatiky. Pro lepší orientaci jsou v sousedním $listboxu$ vypsána použitá pravidla gramatiky při odvozování slova.    
% deklarujeme obrázek s popisem
% parametr v hranatých závorkách určuje preferované umístění
% (lze jich vypsat i více, LaTeX si jednu vybere)
% h - právě zde
% t - nahoře na stránce
% b - dole na stránce
% p - na samostatné stránce

%%% vložit obrazek s barvama
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\section{Programátorská příručka}
\subsection{Použité technologie}
Aplikace je určena pro operační systém Microsoft Windows a je vytvořena v programovacím jazyce C\# ve vývojovém prostředí Microsoft Visual Studio 2010 na platformě .NET Framework 3.5, která je potřebná pro spuštění aplikace. Aplikace vyžaduje knihovnu C5.dll \cite{knihovnaC5}, která je součástí instalačního balíčku. Pro ukládání dat je použit jazyk XML.

\medskip
Platforma .NET je kolekce technologií od firmy Microsoft určená pro vývoj aplikací v systému Windows. Platforma se využívá jak k vývoji, tak k následnému spouštění aplikací v prostředí Windows. Cílem platformy je zjednodušit tvorbu aplikací a správu softwarových instalací. Platforma obsahuje sadu knihoven potřebných pro běh aplikace, společné datové typy, konektivitu s databázemi a  zajišťuje nezávislost na operačním systému. V této platformě můžeme programovat v různých programovacích jazycích, .NET Framework automaticky podporuje třídy, metody, vlastnosti, konstruktory, události, polymorfismus atd.
%Bez ohledu na to v jakém jazyce byla aplikace napsána se vždy překládá do %mezijazyka Common Intermediate Language (CIL).
%\medskip
%Jazyk C\# je moderní objektově orientovaný programovací jazyk od firmy %Microsoft. Vychází z jazyků C (z tohoto jazyka převzal syntaxi), C++ a Java. %Bývá hojně využíván k vývoji formulářových, databázových i webových aplikací.
%Jeho významnou vlastností je technologie {\tt IntelliSense}, která poskytuje %automatické doplňování příkazů a také kontextově závislé seznamy obsahující kód %a skriptovací prvky.

%\newpage
\subsection{Architektura aplikace}
Architektura výsledné aplikace je rozdělena do tří vrstev, které na sebe hierarchicky navazují. V první vrstvě je definována gramatika a automat. Obě třídy mají atributy, které odpovídají definicím regulární gramatiky a konečného automatu a slouží k jejich uložení. V této vrstvě je rovněž řešeno grafické zobrazení konečného automatu. Druhá vrstva obsahuje jednotlivé algoritmy převodů mezi nedeterministickým a deterministickým automatem, převod mezi automatem a gramatikou a naopak. Ve třetí vrstvě je řešeno uživatelské rozhraní aplikace a ovládání aplikace. 
\subsection{Popis tříd}
\subsubsection{Třída NFA}
Třída popisuje automat. Slouží k uložení automatu v programu. Jednotlivé stavy jsou reprezentovány samostatnou třídou {\tt Stavy} popsanou níže. Ve třídě
{\tt NFA} jsou uloženy v seznamu {\tt List$<$Stavy$>$}. Přechody mezi stavy jsou reprezentovány samostatnou třídou {\tt Hrany}, které jsou ve třídě {\tt NFA}  uloženy v seznamu {\tt List$<$Hrany$>$}. 
\begin{itemize}
\item {\bf Metody:}
 \begin{itemize}
    \item \verb|public void AddTransNfa(state from,state to,|
           \verb|input @in)| - Přidá přechod mezi stavy.
    \item \verb|public Set<state> Move(Set<state> states,|
           \verb|input inp)| - Vrací množinu stavů automatu.
\end{itemize}
\end{itemize}

\subsubsection{Třída Stavy}
Tato třída reprezentuje v aplikaci stav automatu, který se zobrazuje na plochu pro zadávání automatu. Obsahuje i definice barev stavu pro jednotlivé typy stavů. Tato třída dědí ze systémové třídy {\tt UserConrol}.
\begin{itemize}
\item {\bf Metody:}
 \begin{itemize}
    \item \verb|public Stavy()| - Konstruktor.    
    \item \verb|public void SetAktualniColor()| - Nastaví aktální barvu pozadí stavu.
    \item \verb|public void SetCircle()| - Nastaví tvar stavu.    
 \end{itemize}
\end{itemize}

\subsubsection{Třída Hrany}
Přechod automatu je reprezentován strukturou {\tt Hrany} obsahující dva stavy {\tt Stavy} a přechodový znak. Všechny přechody jsou uloženy v seznamu {\tt
List$<$Hrany$>$}.
\begin{itemize}
\item {\bf Metody:}
 \begin{itemize}
    \item \verb|public Hrany(Stavy startStav, Stavy finalStav,|
           \verb|List<string> prechody)| - Konstruktor.    
    \item \verb|public bool Kontrolahrany(Point bod)| - Zjistí, zda je myš nad hranou.    
 \end{itemize}
\end{itemize}
\subsubsection{Třída Tabule}
Tato třída dědí ze systémové třídy {\tt UserConrol}. Představuje plochu pro zadávání automatu. Kreslení na plochu je prováděno v metodě OnPaint.
\begin{itemize}
\item {\bf Proměnné:}
 \begin{itemize}
    \item \verb|List<Stavy> seznamStavu| - Seznam obsahující stavy vykreslené na ploše.    
    \item \verb|List<Hrany> seznamHran| - Seznam hran vykreslených na ploše.
    \item \verb|NFA aktualNFA| - Automat na ploše.
 \end{itemize}
\item {\bf Metody:}
\begin{itemize}
\item \verb|private void KresleniHrany(Hrany hrany)| - Překresluje hrany.
\item \verb|protected override void OnPaint(PaintEventArgs e)| - Zajistí vykreslení prvků na plochu.
\item \verb|public void PrevodGrafu()| - Převede automat z plochy do algoritmů.
\item \verb|public NFA VytvorDfaAutomat(DFA automat, Tabule tab)| - Převede deterministický automat pro vykreslení na plochu.
\end{itemize}
\end{itemize}
\subsubsection{Třída Xml}
Slouží k ukládání automatu a gramatiky do souboru a zpětného načtení automatu nebo gramatiky ze souboru.
\begin{itemize}
\item {\bf Metody:}
\begin{itemize}
\item \verb|private XmlDocument GrammarToXml(Grammar gramatika)| - Převede gramatiku do XML dokumentu.
\item \verb|public bool SaveGrammar(Grammar gramatika,|
       \verb|string fileName)| - Uloží gramatiku do souboru.
\item \verb|public bool SaveAutomat(NFA automat, string fileName)| - Uloží automat do souboru.
\item \verb|private NFA XmlToAutomat(XmlDocument doc)| - Vytvoří automat z XML dokumentu.
\item \verb|private Grammar XmlToGrammar(XmlDocument doc)| - Vytvoří gramatiku z XML dokumentu.
\item \verb|public Grammar OpenGrammar(string nazev)| - Načte gramatiku ze souboru.
\item \verb|public NFA OpenAutomat(string nazev)| - Načte automat ze souboru.
\item \verb|private XmlDocument FaToXml(NFA automat)| - Převede automat do XML dokumentu.
\end{itemize}
\end{itemize}
\subsubsection{Třída Form1}
Tato třída představuje hlavní okno aplikace. Dědí ze systémové třídy {\tt Form}.
Provádí nejvíce činností v rámci běhu aplikace. Jsou na něm použity různé prvky formuláře s jejich specifickými vlastnosti.
\begin{itemize}
\item {\bf Metody:}
 \begin{itemize}
    \item \verb|private void btnPridatPravidlo_Click(object sender,|
           \verb|EventArgs e)| - Přidání pravidla včetně kontroly zadávaných hodnot.
    \item \verb|private void PrevodGramatikaAutomat()| - Vytvoří ze zadané gramatiky automat.
    \item \verb|private void PrevodAutomatGramatika()| - Vytvoří ze zadaného automatu gramatiku. 
    \item \verb|private void PrevodNfa_Dfa()| - Vytvoří ze zadaného nedeterministického automatu deterministický automat.
	 \item \verb|private List<string> PrintDerivaceSlova(string slovo,| 	
			  \verb|List<List<PrepisPravidlo>> list)| - Odvození slova ze zadané gramatiky. Nejdříve se ze zadané gramatiky generující regulární jazyk vygenerují slova daného jazyka. Vygenerovaná slova se porovnávají regulárním jazykem se zadaným slovem. Poté se prochází slova, která se shodují se zadaným slovem a používá se historie jejich generování.     
\end{itemize}
\end{itemize} 
\subsubsection{Třída Grammar}
Třída reprezentuje v aplikaci gramatiku. Proměnné této třídy gramatiku definují. Abecedy terminálů a neterminálů jsou uloženy v seznamech {\tt List$<$char$>$}. Množina pravidel je uložena v seznamu {\tt List$<$TransitGrammar$>$}, {\tt TransitGrammar} je struktura definující pravidla gramatiky.
\begin{itemize}
\item {\bf Metody:}
 \begin{itemize}
    \item \verb|public Grammar(List<char> terminal, List<char> neterminal,|
           \verb|char pocatecniSymbol)| - Konstruktor.
\end{itemize}
\end{itemize}

\subsubsection{Třída Prevod}
Třída definuje převod nedeterministického automatu na deterministický.
\begin{itemize}
\item {\bf Metody:}
 \begin{itemize}
    \item \verb|public static DFA Prevod_Nfa_Dfa(NFA nfa)| - Z daného automatu vytvoří automat deterministický.    
    \item \verb|static Set<state> EpsilonPrechod(NFA nfa,|
           \verb|Set<state> states)| - Vytvoří množinu stavů dosažitelných z jednotlivých stavů přes epsilon přechody.    
\end{itemize}
\end{itemize}

\newpage
\begin{conclusions-cz}
Výsledkem této bakalářské práce je aplikace, umožňující vizuálním způsobem zadávat a pozorovat jednotlivé kroky výpočtu konečného automatu a kroky odvození slova ze zadané gramatiky, která může sloužit například pro lepší pochopení problematiky při jejím studiu.


\end{conclusions-cz}

%%% Vytvoření seznamu literatury.
\newpage
\begin{thebibliography}{99}
\bibitem{martinek} Pavel Martinek \emph{Základy teoretické informatiky} UPOL, 2006.
\bibitem{jancar} P.Jančar \emph{Teoretická informatika} VŠB, Ostrava, 2007.
\bibitem{cerna} I.Černá, A.Kučera \emph{Automaty a formální jazyky I} FIMU, 2002.
\bibitem{mares} J.Mareš \emph{Jazyky, gramatiky a automaty} ČVUT, 2004.
\bibitem{bartunek} P.Bartůněk \emph{Knihovna operací nad konečnými automaty} VUT, 2010.  
\bibitem{knihovnaC5} \emph{C5 Generic Collection Library}  \url{http://www.itu.dk/research/c5/}
\bibitem{jancar2} \emph{Úvod do teorie konečných automatů a formálních jazyků} ZCU v Plzni, 2001
\bibitem{chytil} M.Chytil \emph{Automaty a gramatiky} SNTL, Praha, 1984.
\bibitem{programujeme} J.Glynn, K.Watson, Ch.Nagel \emph{C\# 2008 Programujeme profesionálně} Computer Press, 2009.
\end{thebibliography}

%%% Přílohy.
\newpage
\appendix

\section{Popis obsahu přiloženého CD}
Součástí této práce je i CD. Jeho obsahem jsou tři adresáře a jeden soubor.
\begin{itemize}
\item {Adresář {\tt Setup} obsahuje instalační soubor setup.exe} 
\item{Adresář {\tt doc} obsahuje dokumentaci této práce ve spustitelné podobě a zdrojové kódy dokumentace v Texu.}
\item{Třetí adresář {\tt src} obsahuje zdrojový kód programu.}
\item{V souboru {\tt readme.txt} je popsáno, jak lze aplikaci spustit.}
\end{itemize}


\end{document}
