Thesis Details
Omezení větných forem gramatik s rozptýleným kontextem
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.
scattered context grammars, grammatical generalization, derivation restriction, generative power
Bartík Vladimír, Ing., Ph.D. (DIFS FIT BUT), člen
Hanáček Petr, doc. Dr. Ing. (DITS FIT BUT), člen
Peringer Petr, Dr. Ing. (DITS FIT BUT), člen
Racek Stanislav, doc. Ing., CSc. (WBU in Pilsen), člen
Zbořil František, doc. Ing., Ph.D. (DITS FIT BUT), člen
@mastersthesis{FITMT6017, author = "Ji\v{r}\'{i} \v{S}im\'{a}\v{c}ek", type = "Master's thesis", title = "Omezen\'{i} v\v{e}tn\'{y}ch forem gramatik s rozpt\'{y}len\'{y}m kontextem", school = "Brno University of Technology, Faculty of Information Technology", year = 2008, location = "Brno, CZ", language = "czech", url = "https://www.fit.vut.cz/study/thesis/6017/" }