Some Power-Decreasing Derivation Restrictions in Grammar Systems
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose format
RIS BIB ENDNOTESome Power-Decreasing Derivation Restrictions in Grammar Systems
Publication date: 23.03.2011
Schedae Informaticae, 2010, Volume 19, pp. 23 - 34
Authors
Some Power-Decreasing Derivation Restrictions in Grammar Systems
In this paper, we place some left restrictions on derivations in CD grammar systems with phrase- structure grammars, controlled by the regular languages. The rst restriction requires that every production is always applied within the rst k nonterminals in every sentential form, for some k 1. The second restriction says how many blocks of non-terminals can be in each sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in each sentential form. We demonstrate that under these restrictions, the grammar systems generate di erent families of languages. Indeed, under the rst restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enumerable languages. In the end, the family of languages generated by grammar systems under the third restriction is equal to the family of languages generated by programmed grammars with context-free rules without -rules of nite index.
Baker B.S.; Context-sesitive grammars generating context-free languages, in: Au- tomata, Languages and Programming, M. Nivat (ed.), North-Holland, Amsterdam 1972, pp. 501{506.
Book R.V.; Terminal context in context-sensitive grammars, SIAM Journal of Computing 1, 1972, pp. 20{30.
Dassow J., Fernau H., Paun Gh.; On the Leftmost Derivation in Matrix Gram- mars, International Journal of Foundations of Computer Science 10(1), 1999, pp. 61{80.
Dassow J., Paun Gh.; Regulated Rewriting in Formal Language Theory, Springer- Verlag, Berlin 1989.
Fernau H.; Regulated Grammars under Leftmost Derivation, Grammars 3(1), 2000, pp. 37{62.
Fernau H., Holzer M., Freund R.; External Versus Internal Hybridization for Co- operating Distributed Grammar Systems, Technical Raport TR 185{2/FR{1/96, Technische Universitat Wien (Austria), 1996.
Frazier M., Page C.D.; Pre x Grammars: An Alternative Characterization of the Regular Languages, Information Processing Letters 51(2), 1994, pp. 67{71.
Ge ert V.; Context-Free-Like Forms for the Phrase-Structure Grammars, Proceedings of the Mathematical Foundations of Computer Science, Springer-Verlag, New York 1988, pp. 309{317.
Ginsburg S., Greibach S.; Mappings which preserve context-sensitive languages, Information and Control 9, 1966, pp. 563{582.
Hibbard T.N.; Context-Limited Grammars, Journal of the ACM 21, 1974, pp. 446{453.
Matthews G.; A note on symmetry in phrase structure grammars, Information and Control 7, 1964, pp. 360{365.
Matthews G.; Two-way languages, Information and Control 10, 1967, pp. 111{ 119.
Meduna A.; Matrix Grammars under Leftmost and Rightmost Restrictions, Mathematical Linguistics and Related Topics, Romanian Academy of Sciences, Bucharest 1994, pp. 243{257.
Meduna A.; On the Number of Nonterminals in Matrix Grammars with Left- most Derivations, New Trends in Formal Languages: Control, Cooperation, and Combinatorics, Springer-Verlag, New York 1997, pp. 27{39.
Meduna A.; Automata and Languages: Theory and Applications, Springer- Verlag, London 2000.
Rozenberg G., Salomaa A.; Handbook of Formal Languages, Vol. 1, Springer- Verlag, Berlin 1997.
Information: Schedae Informaticae, 2010, Volume 19, pp. 23 - 34
Article type: Original article
Titles:
Some Power-Decreasing Derivation Restrictions in Grammar Systems
Some Power-Decreasing Derivation Restrictions in Grammar Systems
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
Brno University of Technology, Faculty of Information Technology, Czech Republic
Department of Geoinformatics, Faculty of Science, Palacký University, 17. listopadu 50, 771 46 Olomouc, Czechia
Published at: 23.03.2011
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 1990
Number of downloads: 976