The structure of index sets and reduced indexed grammars. (English) Zbl 0701.68071

Summary: The set of index words attached to a variable in derivations of indexed grammars is investigated. Using the regularity of these sets it is possible to transform an indexed grammar in a reduced form and to describe the structure of left sentential forms of an indexed grammar.


68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] 1. A. V. AHO, Indexed Grammars, J.A.C.M., Vol. 15, 1968, pp. 647-671. Zbl0175.27801 MR258547 · Zbl 0175.27801
[2] 2. J. DUSKE and R. PARCHMANN, Linear Indexed Languages, Theoret. Computer Sci, Vol. 32, 1984, pp. 47-60. Zbl0545.68067 MR761160 · Zbl 0545.68067
[3] 3. J. ENGELFRIET and H. VOGLER, Look-Ahead on Pushdowns, Inform. and Comput., Vol. 73, 1987, pp. 245-279. Zbl0625.68063 MR888261 · Zbl 0625.68063
[4] 4. S. A. GREIBACH, A Note on Pushdown Store Automata and Regular Systems, Proc. Amer. Math. Soc., Vol. 18, 1967, pp. 263-268. Zbl0183.01703 MR209086 · Zbl 0183.01703
[5] 5. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[6] 6. T. S. E. MAIBAUM, Pumping Lemmasfor Term Languages, J. Comput. System Sci., Vol. 17, 1978, pp. 319-330. Zbl0388.68071 MR516842 · Zbl 0388.68071
[7] 7. R. PARCHMANN, J. DUSKE and J. SPECHT, On Deterministic Indexed Languages, Inform. and Control, Vol. 45, 1980, pp. 48-67. Zbl0438.68035 MR582145 · Zbl 0438.68035
[8] 8. R. PARCHMANN, J. DUSKE and J. SECHT, Indexed LL (k)-Grammars, Acta Cybernetica, Vol. 7, 1984, pp. 33-53. Zbl0577.68077 MR773714 · Zbl 0577.68077
[9] 9. R. W. SEBESTA and N. D. JONES, Parsers for Indexed Grammars, Internat. J. Comput. and Inform. Sci., Vol. 7, 1978, pp. 345-359. Zbl0402.68059 MR511369 · Zbl 0402.68059
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.