Linear indexed languages. (English) Zbl 0545.68067

Summary: In this paper one characterization of linear indexed languages based on controlling linear context-free grammars with context-free languages and one based on homomorphic images of context-free languges are given. By constructing a generator for the family of linear indexed languages, it is shown that this family is a full principal semi-AFL. Furthermore a Parikh theorem for linear indexed languages is stated which implies that there are indexed languages which are not linear.


68Q45 Formal languages and automata
Full Text: DOI


[1] Aho, A.V., Indexed grammars, J. ACM, 15, 647-671, (1968) · Zbl 0175.27801
[2] Berstel, J., Transductions and contex-free languages, (1979), Teubner Stuttgart
[3] Ginsburg, S.; Spanier, E.H., Control sets on grammars, Math. systems theory, 2, 169-177, (1968) · Zbl 0157.33604
[4] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[5] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[6] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[7] Khabbaz, N.A., A geometric hierarchy of languages, J. comput. system. sci., 8, 142-157, (1974) · Zbl 0294.68029
[8] R. Parchmann, Balanced context-free languages and indexed languages, Elektron. Informationsverarbeit. u. Kybernetik, to appear. · Zbl 0597.68059
[9] Salomaa, A., Formal languages, (1973), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.