Thesis Details

Kanonické derivace programovaných gramatik

Bachelor's Thesis Student: Zemek Petr Academic Year: 2007/2008 Supervisor: Meduna Alexander, prof. RNDr., CSc.

English title

Canonical Derivations in Programmed Grammars

Language

Czech

Abstract

This work studies canonical derivations (with focus on leftmost derivations) in programmed grammars and left restriction range. It is shown that if we introduce n-limited derivations in programmed grammars as they were defined for state grammars, we get an infinite hierarchy of language families resulting from n-limited programmed grammars, so the left restriction range affects the generative power of n-limited programmed grammars. This result is significant for syntactical analysis based on programmed grammars.

Keywords

Programmed grammar, canonical derivations, leftmost derivations, n-limited derivations, state grammar, unrestricted state grammar, infinite hierarchy of language families.

Department

Department of Information Systems FIT BUT

Degree Programme

Information Technology

Files

Thesis text 1.2 MB

Status

defended, grade A

Date

12 June 2008

Reviewer

Masopust Tomáš, RNDr., Ph.D.

Committee

Zbořil František V., doc. Ing., CSc. (DITS FIT BUT), předseda
Kolář Dušan, doc. Dr. Ing. (DIFS FIT BUT), člen
Martinek David, Ing. (DIFS FIT BUT), člen
Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT), člen
Orság Filip, Ing., Ph.D. (DITS FIT BUT), člen
Sojka Petr, doc. RNDr., Ph.D. (FI MUNI), člen

Citation

ZEMEK, Petr. Kanonické derivace programovaných gramatik. Brno, 2008. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2008-06-12. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/6572/

BibTeX

@bachelorsthesis{FITBT6572,
    author = "Petr Zemek",
    type = "Bachelor's thesis",
    title = "Kanonick\'{e} derivace programovan\'{y}ch gramatik",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2008,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/6572/"
}

Theses