PhD. Theses
OneSided Random Context GrammarsDissertation:  2014 

Student:  Zemek Petr, Ing. 

Supervisor:  Meduna Alexander, prof. RNDr., CSc. 
Department:  Department of Information Systems FIT BUT 
Status:  defended 

Date:  20140912 

Files:  
Keywords 
formal language theory, regulated grammars, random context grammars,
onesided random context grammars, permitting grammars, forbidding
grammars, generative power, reduction, normal forms, leftmost
derivations, generalized versions, LL versions  Abstract


This thesis introduces the notion of a onesided random context grammar as a contextfreebased regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules.
A left random context rule can rewrite a nonterminal if each of its
permitting symbols occurs to the left of the rewritten symbol in the
current sentential form while each of its forbidding symbols does not
occur there. A right random context rule is applied analogically except
that the symbols are examined to the right of the rewritten symbol.The
thesis is divided into three parts. The first part gives a motivation
behind introducing onesided random context grammars and places all the
covered material into the scientific context. Then, it gives an overview
of formal language theory and some of its lesserknown areas that are
needed to fully grasp some of the upcoming topics.The second
part forms the heart of the thesis. It formally defines onesided random
context grammars and studies them from many points of view. Generative
power, relations to other types of grammars, reduction, normal forms,
leftmost derivations, generalized and parsingrelated versions all
belong between the studied topics.The final part of this thesis
closes its discussion by adding remarks regarding its coverage. More
specifically, these remarks concern application perspectives,
bibliography, and open problem areas.  ISO 690 Citation 

ZEMEK, Petr. OneSided Random Context Grammars. Brno, 2014. Available from: http://www.fit.vutbr.cz/study/DP/PD.php?id=238. PhD. Thesis. Brno University of Technology, Faculty of Information Technology. 20140912. Supervisor Meduna Alexander. 
BibTeX 

@PHDTHESIS{
author = {Petr Zemek},
title = {OneSided Random Context Grammars},
school = {Brno University of Technology,
Faculty of Information Technology},
year = {2014},
location = {Brno, CZ},
url = {http://www.fit.vutbr.cz/study/DP/PD.php?id=238}
}

