|
|
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.
|
|
|
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.
|
|
|
Non-Returning Turing Machines
Surovič, Marek ; Vrábel, Lukáš (referee) ; Meduna, Alexandr (advisor)
This work introduces a restricted variant of the Turing machine which cannot move left, thus return on its tape. Other properties, such as the potentially infinite symbol tape or the ability to rewrite symbols on the tape, remain unchanged. By introducing this restriction we limit the expressive power of the Turing machine to the point, where a non-returning Turing machine is equivalent to a finite automaton and can be transformed into one. A transformation algorithm is presented and described in detail.
|
|
|
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.
|
|
|
Non-Returning Turing Machines
Surovič, Marek ; Vrábel, Lukáš (referee) ; Meduna, Alexandr (advisor)
This work introduces a restricted variant of the Turing machine which cannot move left, thus return on its tape. Other properties, such as the potentially infinite symbol tape or the ability to rewrite symbols on the tape, remain unchanged. By introducing this restriction we limit the expressive power of the Turing machine to the point, where a non-returning Turing machine is equivalent to a finite automaton and can be transformed into one. A transformation algorithm is presented and described in detail.
|
|
|
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 ::
