Some power - decreasing derivation restrictions in grammar systems

• Autorzy: Meduna A. , Čermák M. , Masopust T.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we place some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by the regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k greather than 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 different families of languages. Irideed, under the first restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enu-merable 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 e-rules of finite index.

Słowa kluczowe

EN

grammar systems; derivation restriction; generative power

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2010
• Tom: Vol. 19
• Strony: 23--34
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Meduna A.

autor

Čermák M.

autor

Masopust T.

• Brno University of Technology, Faculty of Information Technology, Božetechova 2, 612 66 Brno, Czech Republic,

Bibliografia

• [1] Baker B.S.; Context-sensitive grammars generating context-free languages, in: Automata, Languages and Programming, M. Nivat (ed.), North-Holland, Amsterdam 1972, pp. 501-506.
• [2] Book R.V.; Terminal context in context-sensitive grammars, SIAM Journal of Computing 1, 1972, pp. 20-30.
• [3] Dassow J., Fernau H., Paun Gh.; On the Leftmost Derivation in Matrix Grammars, International Journal of Foundations of Computer Science 10(1), 1999, pp. 61-80.
• [4] Dassow J., Paun Gh.; Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin 1989.
• [5] Fernau H.; Regulated Grammars under Leftmost Derivation, Grammars 3(1), 2000, pp. 37-62.
• [6] 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 Universität Wien (Austria), 1996.
• [7] Frazier M., Page C.D.; Prefix Grammars: An Alternative Characterization of the Regular Languages, Information Processing Letters 51(2), 1994, pp. 67-71.
• [8] Geffert 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.
• [9] Ginsburg S., Greibach S.; Mappings which preserve context-sensitive languages, Information and Control 9, 1966, pp. 563-582.
• [10] Hibbard T.N.; Context-Limited Grammars, Journal of the ACM 21, 1974, pp. 446-453.
• [11] Matthews G.; A note on symmetry in phrase structure grammars, Information and Control 7, 1964, pp. 360-365.
• [12] Matthews G.; Two-way languages, Information and Control 10, 1967, pp. 111-119.
• [13] Meduna A.; Matrix Grammars under Leftmost and Rightmost Restrictions, Mathematical Linguistics and Related Topics, Romanian Academy of Sciences, Bucharest 1994, pp. 243-257.
• [14] Meduna A.; On the Number of Nonterminals in Matrix Grammars with Leftmost Derivations, New Trends in Formal Languages: Control, Cooperation, and Combinatorics, Springer-Verlag, New York 1997, pp. 27-39.
• [15] Meduna A.; Automata and Languages: Theory and Applications, Springer-Verlag, London 2000.
• [16] Rozenberg G., Salomaa A.; Handbook of Formal Languages, Vol. 1, Springer-Verlag, Berlin 1997.