Thesis Details

Cestami řízené gramatiky

Master's Thesis Student: Adamec Ondřej Academic Year: 2014/2015 Supervisor: Křivka Zbyněk, Ing., Ph.D.
English title
Path-Controlled Grammars
Language
Czech
Abstract

This thesis deals with path-controlled grammars, which are grammars that place restrictionson the paths in a derivation tree of a context-free grammar. The goal of this thesisis to create an algorithm for conversion between the path-controlled grammars and thestate grammars, which is a di erent type of regulated grammars. Another goal is to studythe generative power of path-controlled grammars based on the conversion algorithm. Theconversion algorithm is implemented and tested on a number of path-controlled grammars.Also, its complexity is discussed. Finally, a parsing tool for path-controlled grammars isimplemented. Complexity of this tool is analyzed as well.

Keywords

path-controlled grammars, matrix grammars, state grammars, regulated grammars, formal languages, syntactic analysis.

Department
Department of Information Systems FIT BUT
Degree Programme
Information Technology, Field of Study Mathematical Methods in Information Technology
Files
Status
defended, grade C
Date
24 June 2015
Reviewer
Soukup Ondřej, Ing.
Committee
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), předseda
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (DITS FIT BUT), člen
Hrubý Martin, Ing., Ph.D. (DITS FIT BUT), člen
Rozinajová Viera, doc. Ing., Ph.D. (FIIT STU), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Citation
ADAMEC, Ondřej. Cestami řízené gramatiky. Brno, 2015. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2015-06-24. Supervised by Křivka Zbyněk. Available from: https://www.fit.vut.cz/study/thesis/14737/
BibTeX 
@mastersthesis{FITMT14737,
    author = "Ond\v{r}ej Adamec",
    type = "Master's thesis",
    title = "Cestami \v{r}\'{i}zen\'{e} gramatiky",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2015,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/14737/"
}

Theses

Back to top