×

Look-ahead on pushdowns. (English) Zbl 0625.68063

The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars.

MSC:

68Q45 Formal languages and automata
68N20 Theory of compilers and interpreters
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aho, A.V., Indexed grammars, an extension of context-free grammars, J. assoc. comput. Mach., 15, 647-671, (1968) · Zbl 0175.27801
[2] Aho, A.V., Nested stack automata, J. assoc. comput. Mach., 16, 383-406, (1969) · Zbl 0184.28603
[3] Culik, K.; Cohen, R., LR-regular grammars—an extension of LR(k) grammars, J. comput. system sci., 7, 66-96, (1973) · Zbl 0253.68014
[4] Damm, W., The IO- and OI-hierarchies, Theor. comput. sci., 20, 95-207, (1982) · Zbl 0478.68012
[5] Damm, W.; Goerdt, A., An automata-theoretic characterization of the OI-hierarchy, Inform. control., 71, 1-32, (1986) · Zbl 0628.68061
[6] Engelfriet, J., Top-down tree transducers with regular look-ahead, Math. systems theory, 10, 289-303, (1977) · Zbl 0369.68048
[7] Engelfriet, J., On tree transducers for partial functions, Inform. process. lett., 7, 170-172, (1978) · Zbl 0379.94066
[8] Engelfriet, J., (), 1986 (original manuscript: Recursive automata, 1982)
[9] Engelfriet, J., Iterated pushdown automata and complexity classes, (), 365-373
[10] Engelfriet, J.; Rozenberg, G., Fixed point languages, equality languges, and representation of recursively enumerable languages, J. assoc. comput. Mach., 27, 499-518, (1980) · Zbl 0475.68047
[11] Engelfriet, J.; Schmidt, E.M.; Engelfriet, J.; Schmidt, E.M., IO and OI, J. comput. system sci., J. comput. system sci., 16, 67-99, (1977/1978) · Zbl 0371.68020
[12] Engelfriet, J.; Vogler, H., Pushdown machines for the macro tree transducer, Theor. comput. sci., 42, 251-368, (1986) · Zbl 0619.68065
[13] Engelfriet, J.; Vogler, H., Macro tree transducers, J. comput. system sci., 31, 71-146, (1985) · Zbl 0588.68039
[14] Engelfriet, J.; Vogler, H.; Engelfriet, J.; Vogler, H., Characterization of high level tree transducers, (), 171-178, see also
[15] Ginsburg, S., ()
[16] Greibach, S.A., A note on pushdown store automata and regular systems, (), 263-268 · Zbl 0183.01703
[17] Greibach, S.A., Full AFLs and nested iterated substitution, Inform. control, 16, 7-35, (1970) · Zbl 0188.03102
[18] Harrison, M.A., ()
[19] Hopcroft, J.E.; Ullman, J.D., Introducion to automata theory, languages, and computation, () · Zbl 0196.01701
[20] Jarzabek, S.; Krawczyk, T., LL-regular grammars, Inform. process. lett., 4, 31-37, (1975) · Zbl 0314.68026
[21] Maibaum, T.S.E., A generalized approach to formal languages, J. comput. system sci., 8, 409-439, (1974) · Zbl 0361.68113
[22] Maslov, A.N., The hierarchy of indexed languages of an arbitrary level, Soviet. math. dokl., 15, 1170-1174, (1974) · Zbl 0316.68042
[23] Maslov, A.N., Multilevel stack automata, Problems inform transmission, 12, 38-43, (1976)
[24] Mehlhorn, K., Parsing macro grammars top down, Inform. control, 40, 123-143, (1979) · Zbl 0409.68044
[25] Nijholt, A., LL-regular grammars, Internat. J. comput. math., 8, 303-318, (1980) · Zbl 0452.68083
[26] Nijholt, A., The equivalence problem for LL- and LR-regular grammars, J. comput. system sci., 24, 149-161, (1982) · Zbl 0482.68070
[27] Nijholt, A., From LL-regular to LL(1) grammars: transformations, covers and parsing, RAIRO inform. théor., 16, 387-406, (1982) · Zbl 0498.68052
[28] Nijholt, A., ()
[29] Parchmann, R.; Duske, J.; Specht, J., On deterministic indexed languages, Inform. control, 45, 48-67, (1980) · Zbl 0438.68035
[30] Parchmann, R.; Duske, J.; Specht, J., Closure properties of deterministic indexed languages, Inform. control, 46, 200-218, (1980) · Zbl 0453.68053
[31] Parchmann, R.; Duske, J.; Specht, J., Indexed LL(k) grammars, Acta cybernet., 7, 33-53, (1984) · Zbl 0577.68077
[32] Poplawsky, D.A., On LL-regular grammars, J. comput. system sci., 18, 218-227, (1979) · Zbl 0411.68060
[33] Scott, D., Some definitional suggestions for automata theory, J. comput. system sci., 1, 187-212, (1967) · Zbl 0164.32103
[34] Sebesta, R.W.; Jones, N.D., Parsers for indexed grammars, Internat. J. comput. inform. sci., 7, 345-359, (1978) · Zbl 0402.68059
[35] Wand, M., An algebraic formulation of the chomsky-hierarchy, (), 209-213
[36] Watt, D.A., Rule splitting and attribute-directed parsing, (), 363-392
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.