Thesis Details

One-Sided Random Context Grammars

Ph.D. Thesis Student: Zemek Petr Academic Year: 2014/2015 Supervisor: Meduna Alexander, prof. RNDr., CSc.
Czech title
Jednostranné gramatiky s nahodilým kontextem

This thesis introduces the notion of a one-sided random context grammar as a context-free-based 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 one-sided 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 lesser-known areas that are needed to fully grasp some of the upcoming topics.

The second part forms the heart of the thesis. It formally defines one-sided 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 parsing-related 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.


formal language theory, regulated grammars, random context grammars, one-sided random context grammars, permitting grammars, forbidding grammars, generative power, reduction, normal forms, leftmost derivations, generalized versions, LL versions

Degree Programme
Computer Science and Engineering, Field of Study Computer Science and Engineering
12 September 2014
ZEMEK, Petr. One-Sided Random Context Grammars. Brno, 2014. Ph.D. Thesis. Brno University of Technology, Faculty of Information Technology. 2014-09-12. Supervised by Meduna Alexander. Available from:
    author = "Petr Zemek",
    type = "Ph.D. thesis",
    title = "One-Sided Random Context Grammars",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2014,
    location = "Brno, CZ",
    language = "english",
    url = ""
Back to top