|
|
New Versions of Classical Automata and Grammars
Soukup, Ondřej ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
Tato diplomová práce se zabývá zkoumáním nových verzí automatů a gramatik a je proto rozdělena do dvou částí. První část definuje a studuje čisté více zásobníkové automaty a navíc zavádí úplná uspořádání nad jejich zásobníky nebo zásobníkovými symboly. Práce dokazuje, že zavedená omezení snižují vyjadřovací sílu automatů. Ve druhé části práce jsou definovány a popsány nové derivační módy gramatik s rozptýleným kontextem, které zobecňují relaci přímé derivace. Je dokázáno, že jejich použití nesnižuje vyjadřovací sílu gramatik.
|
|
|
Parsing Based on Scattered Context Grammars
Horníček, Ondřej ; Solár, Peter (referee) ; Zámečníková, Eva (advisor)
This work deals with new possibilities in parsing based on advanced formal models, specifically using scattered context grammars in syntactic analysis. Context-sensitive language was created for comparing different methods of syntactic analysis, where these grammars are used. In conclusion is discussed possible use in practise, paralell parsing, pros and cons and further investigation.
|
|
|
A Restriction of Sentetial Forms of of Scattered Context Grammars
Šimáček, Jiří ; Masopust, Tomáš (referee) ; Meduna, Alexandr (advisor)
This work introduces and discusses generalized scattered context grammars that are based upon sequences of productions whose left-hand sides are formed by nonterminal strings, not just single nonterminals. It places two restrictions on the derivations in these grammars. More specifically, let k be a constant. The first restriction requires that rewriting all symbols occurs within the first k symbols of the first continuous block of nonterminals in the sentential form during every derivation step. The other restriction defines the derivations over sentential forms containing no more than k occurrences of nonterminals. As its main result, the thesis demonstrates that both restrictions decrease the generative power of these grammars to the power of context-free grammars.
|
|
| |
guest ::
