Original title: Převody mezi CF gramatikami a zásobníkovými automaty
Translated title: Conversions between CF Grammars and Pushdown Automata
Authors: Makovský, Benjamin ; Goldefus, Filip (referee) ; Masopust, Tomáš (advisor)
Document type: Master’s theses
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce navrhuje a řeší implementaci transformací bezkontextových gramatik a převody mezi bezkontextovými gramatikami a zásobníkovými automaty. Obsahuje seznámení s modely, které se používají v moderní teorii formálních jazyků. V práci jsou uvedeny všechny potřebné algoritmy pro transformace a vzájemné převody mezi bezkontextovými gramatikami a zásobníkovými automaty. Je představen objektový návrh reprezentující gramatiku a automat v programu. Je popsáno řešení zadávání definice gramatiky a automatu, řešení vykreslování automatu na obrazovku a vytvoření grafického uživatelského rozhraní aplikace. Výsledný program je zpracován jako Java applet, který je umístěn na veřejných internetových stránkách www.convertcfg.php5.cz. This work suggests and solves the implementation of the transformation of context-free grammars and the conversions between context-free grammars and pushdown automata. It makes acquainted with the models used in modern theory of formal languages. In the work are indicated all algorithms necessary for transformations and mutual conversions between context-free grammars and pushdown automata. Proposed is an object representing the grammar and the automaton in the programme. Described is the assigning of definitions of grammar and of the automaton, the solution of drawing the automaton on the screen and the creation of graphical user interface of the application. The resulting programme is developed as Jawa applet which is available on public internet pages www.convertcfg.php5.cz.
Keywords: Alphabet; context-free grammar; language; nonterminal and terminal symbol; production rule; pushdown automaton; state; transition relation.; Abeceda; bezkontextová gramatika; jazyk; neterminální a terminální symbol; přechodová funkce.; přepisovací pravidlo; stav; zásobníkový automat

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/53917

Permalink: http://www.nusl.cz/ntk/nusl-590090


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses