Grammars, derivation modes and properties of indexed and type-0 languages. (English) Zbl 0636.68096

The authors introduce an extension of a context-free grammar which in addition to the usual context-free productions \(A\to \alpha\) can contain also so-called index productions of the form Af\(\to B\) and \(A\to Bf\), where A and B are nonterminals and f belongs to a given set of indices. With these indices it is possible to distribute the information over context-free productions.
It is shown in the paper that the so-called V-mode of derivation yields exactly the class of indexed languages and R-mode, respectively, the class of type-0 languages. A normal-form transformation, similar to the Chomsky normal form, is carried out. Moreover, using the notion of a generalized Dyck grammar, the authors give new homomorphic characterizations for indexed languages and type-0 languages.
Reviewer: M.Linna


68Q45 Formal languages and automata
Full Text: DOI


[1] Aho, A. V., Indexed Grammars, J. ACM, 15, 647-671 (1968) · Zbl 0175.27801
[2] Bachmann, P., Theoretical investigations of functional grammars, Elektron. Informationsverarb. Kybernet., 15, 497-506 (1979) · Zbl 0436.68047
[3] Culik, K., A purely homomorphic characterization of recursively enumerable sets, J. ACM, 26, 345-350 (1979) · Zbl 0395.68076
[4] Duske, J.; Parchmann, R.; Specht, J., A homomorphic characterization of indexed languages, Elektron. Informationsverarb. Kybernet., 15, 187-195 (1979) · Zbl 0421.68071
[5] Duske, J.; Parchmann, P., Linear indexed languages, Theoret. Comput. Sci., 32, 47-60 (1984) · Zbl 0545.68067
[6] Engelfrict, J.; Rozenberg, G., Equality languages, fixed-point languages and representations of recursively enumerable languages, Proc. 19th Ann. IEEE Symp. on Foundations of Computer Science, 123-126 (1978)
[7] Ginsburg, S.; Greibach, S. A.; Harrison, M. A., One-way stack automata, J. ACM, 14, 389-418 (1967) · Zbl 0171.14803
[8] Ginsburg, S.; Spanier, E. H., Control set on grammars, Math. Systems Theory, 2, 159-177 (1968) · Zbl 0157.33604
[9] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[10] Hayashi, T., On derivation trees of indexed grammars, Publ. Res. Inst. Math. Sci., 9, 61-92 (1973) · Zbl 0319.68043
[11] Lukaszewicz, L., On functional grammars, (Winkowski, J., Proc. Mathematical Foundations of Computer Science 1978. Proc. Mathematical Foundations of Computer Science 1978, Lecture Notes in Computer Science, 64 (1978), Springer: Springer Berlin), 333-344
[12] Parchmann, R.; Duske, J.; Specht, J., On deterministic indexed languages, Inform. and Control, 45, 48-67 (1980) · Zbl 0438.68035
[13] Parchmann, R.; Duske, J.; Specht, J., Closure properties of deterministic indexed languages, Inform. and Control, 46, 200-218 (1980) · Zbl 0453.68053
[14] Parchmann, R.; Duske, J.; Specht, J., Indexed LL \((k)\) grammars, Acta Cybernet., 7, 33-53 (1985) · Zbl 0577.68077
[15] Parchmann, R., Balanced context-free languages and indexed languages, Elektron. Informationsverarb. Kybernet., 20, 543-556 (1984) · Zbl 0597.68059
[16] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.