|
|
Deep Pushdown Automata of Finite Index
Poncová, Vendula ; Horáček, Petr (referee) ; Meduna, Alexandr (advisor)
This thesis introduces several modifications of deep pushdown automata considering the reduced number of states or non-input symbols. It is shown that the power of deep pushdown automata of finite index is not affected by a limitation of non-input symbols to one, thus these automata characterize an infinite hierarchy of language families resulting from programmed grammars of finite index. Based on a principle of these automata, it is established the normal form of deep pushdown automata. Finally, I introduce generalized deep pushdown automata. They expand the topmost possible non-input symbol in the pushdown. These automata and their reduced forms are equivalent to state grammars.
|
|
|
Parsing of Regulated Grammars
Šrajer, Roman ; Čermák, Martin (referee) ; Křivka, Zbyněk (advisor)
This thesis studies regulated grammars, their fundamentals and expressing power regarding Chomsky hierarchy of languages. Programmed grammars are investigated in more depth considering a few types of leftmost derivations. A variant of deterministic syntax analysis of programmed grammars is introduced. This analysis works similarly as LL(k) parsing. Transformations of matrix grammars into programmed grammars without changing their expressing power are introduced. The syntax analysis by regularly controlled grammars partly using programmed grammars are presented. In the end, cooperating distributed grammars with left permitting grammars as components are mentioned. Their deterministic syntax analysis uses predictive table or exhaustive exploration of the whole state space.
|
|
|
Parsing Based on Programmed Grammars
Pačes, Jan ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This thesis is researching methods of parsing based on programmed grammars. It modifies known algorithm of table driven non-recursive predictive parser for context-free grammars and applies it on programmed grammars. It studies strength of this method, focusing on some languages which are not context-free.
|
|
|
Canonical Derivations in Programmed Grammars
Zemek, Petr ; Masopust, Tomáš (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
Canonical Derivations in Programmed Grammars
Zemek, Petr ; Masopust, Tomáš (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
Parsing Based on Programmed Grammars
Pačes, Jan ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This thesis is researching methods of parsing based on programmed grammars. It modifies known algorithm of table driven non-recursive predictive parser for context-free grammars and applies it on programmed grammars. It studies strength of this method, focusing on some languages which are not context-free.
|
|
|
Deep Pushdown Automata of Finite Index
Poncová, Vendula ; Horáček, Petr (referee) ; Meduna, Alexandr (advisor)
This thesis introduces several modifications of deep pushdown automata considering the reduced number of states or non-input symbols. It is shown that the power of deep pushdown automata of finite index is not affected by a limitation of non-input symbols to one, thus these automata characterize an infinite hierarchy of language families resulting from programmed grammars of finite index. Based on a principle of these automata, it is established the normal form of deep pushdown automata. Finally, I introduce generalized deep pushdown automata. They expand the topmost possible non-input symbol in the pushdown. These automata and their reduced forms are equivalent to state grammars.
|
|
|
Parsing of Regulated Grammars
Šrajer, Roman ; Čermák, Martin (referee) ; Křivka, Zbyněk (advisor)
This thesis studies regulated grammars, their fundamentals and expressing power regarding Chomsky hierarchy of languages. Programmed grammars are investigated in more depth considering a few types of leftmost derivations. A variant of deterministic syntax analysis of programmed grammars is introduced. This analysis works similarly as LL(k) parsing. Transformations of matrix grammars into programmed grammars without changing their expressing power are introduced. The syntax analysis by regularly controlled grammars partly using programmed grammars are presented. In the end, cooperating distributed grammars with left permitting grammars as components are mentioned. Their deterministic syntax analysis uses predictive table or exhaustive exploration of the whole state space.
|
guest ::
