Thesis Details

O vymazávacích pravidlech v řízených gramatikách

Master's Thesis Student: Zemek Petr Academic Year: 2009/2010 Supervisor: Meduna Alexander, prof. RNDr., CSc.
English title
On Erasing Rules in Regulated Grammars
Language
Czech
Abstract

This work discusses the effect of erasing rules to the generative power of regulated grammars, which is a big open problem in the theory of regulated rewriting. It studies the possibility of removal of erasing rules from regulated grammars by aggregation of current, up-to-date results concerning this elimination and by presentation of a new condition, called k-limited erasing, under which all erasing rules can be always removed from regularly controlled context-free grammars without affecting their generative power. This result partially solves the abovementioned problem. Moreover, a new algorithm for elimination of erasing rules from context-free grammars is presented. This algorithm does not require any predetermination of so called epsilon-nonterminals (in contrast to the standard algorithm used in textbooks). In the conclusion, a significance of these results concerning syntactical analysis is discussed.

Keywords

context-free grammar, regulated grammars, regularly controlled context-free grammar, removal of erasing rules, limited erasing

Department
Department of Information Systems FIT BUT
Degree Programme
Information Technology, Field of Study Information Systems
Files
Status
defended, grade A
Date
24 June 2010
Reviewer
Koutný Jiří, Ing.
Committee
Kolář Dušan, doc. Dr. Ing. (DIFS FIT BUT), předseda
Fučík Otto, doc. Dr. Ing. (DCSY FIT BUT), člen
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT), člen
Květoňová Šárka, Ing., Ph.D. (DIFS FIT BUT), člen
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT), člen
Mišovič Milan, prof. RNDr., CSc. (Mendelu), člen
Citation
ZEMEK, Petr. O vymazávacích pravidlech v řízených gramatikách. Brno, 2010. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2010-06-24. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/9183/
BibTeX 
@mastersthesis{FITMT9183,
    author = "Petr Zemek",
    type = "Master's thesis",
    title = "O vymaz\'{a}vac\'{i}ch pravidlech v \v{r}\'{i}zen\'{y}ch gramatik\'{a}ch",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2010,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/9183/"
}

Theses

Back to top