Original title:
Kanonické derivace programovaných gramatik
Translated title:
Canonical Derivations in Programmed Grammars
Authors:
Zemek, Petr ; Masopust, Tomáš (referee) ; Meduna, Alexandr (advisor) Document type: Bachelor's theses
Year:
2008
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
V této práci jsou studovány kanonické derivace (se zaměřením na nejlevější derivace) v programovaných gramatikách a rozsah levého omezení. Je ukázáno, že zavedením n-limitovaných derivací v programovaných gramatikách tak, jako byly zavedeny pro stavové gramatiky, dostaneme nekonečnou hierarchii jazykových tříd vyplývající z n-limitovaných programovaných gramatik, takže rozsah levého omezení ovlivňuje generativní sílu n-limitovaných programovaných gramatik. Tento výsledek má význam pro syntaktickou analýzu založenou na programovaných gramatikách.
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:
canonical derivations; infinite hierarchy of language families.; leftmost derivations; n-limited derivations; Programmed grammar; state grammar; unrestricted state grammar; kanonické derivace; n-limitované derivace; nejlevější derivace; nekonečná hierarchie jazykových tříd.; neomezená stavová gramatika; Programovaná gramatika; stavová gramatika
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/55422