ABSTRACT
This paper develops necessary conditions for languages to be stack generable, stack decidable, and non-erasing stack generable. The result for stack generable languages shows that the languages {an3¦n≥ 0} and {an bn2 cn ¦n≥0) are not stack generable. It also shows that the language {am bm2 cn ¦m, n&ge1} υ{am bn2 cn ¦m, n≥1} is inherently ambiguous as a stack language. In addition, it shows that the infiniteness problem for stack generable languages is solvable.
The necessary conditions for stack decidable and non-erasing stack generable languages show that {an bn2 ¦n≥1} υ{an b2n2 c¦n≥1} is not stack decidable and that {an bn2 ¦n≥0}is not non-erasing stack generable. These examples show that these two families of languages are not closed under reversal.
Two unsolvability results are also obtained. The question of whether a stack generable language is inherently ambiguous as a stack language is undecidable. The question of whether the reversal of a non-erasing stack generable language is also non-erasing stack generable is undecidable.
- 1.Y. Bar-Hillel, M. Perles and E. Shamir, On formal properties of simple phrase structure grammars, Z. Phonetik Sprachwiss. Kommunikat 14 (1961), 143-172.Google Scholar
- 2.J. R. Buchi, On a decision method in restricted second order arithmetic, Proc. Int. Cong. Logic, Method and Philos. Sci. 1960, Stanford Univ. Press, Stanford, Cal., 1962.Google Scholar
- 3.S. Ginsburg and S. A. Greibach, Deterministic context free languages, Information and Control 9 (1966), 620-648.Google ScholarCross Ref
- 4.S. Ginsburg, S. A. Greibach and M. A. Harrison, One-way stack automata, J. Assoc.Comput. Mach. 14 (1967), 389-418. Google ScholarDigital Library
- 5.S. A. Greibach, A note on undecidable properties of formal languages, Math. Systems Theory 2 (1968),1-6.Google ScholarCross Ref
- 6.J. E. Hopcroft and J. D. Ullman, An approach to a unified theory of automata, Bell System Tech. J. 46 (1967), 1793-1827. Also, IEEE Conf. Record of Eighth Annual Symp. on Switching and Automata Theory, Austin, Texas, October, 1967.Google Scholar
- 7.W. F. Ogden, A helpful result for proving inherent ambiguity, Math. Systems Theory 2 (1968), 191-194.Google ScholarCross Ref
- 8.W. F. Ogden, Intercalation theorems for pushdown store and stack languages, Doctoral dissertation, Stanford University, Stanford, Cal., 1969.Google Scholar
- 9.D. Scott, Some definitional suggestions for automata theory, J. Computer Syst. Sci. 1 (1967), 187-212.Google ScholarDigital Library
Index Terms
- Intercalation theorems for stack languages
Recommendations
Intercalation theorems for tree transducer languages
STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computingWe develop intercalation lemmas for the computations of the top-down tree transducers defined by Rounds [15] and Thatcher [17]. These lemmas are used to prove necessary conditions for languages all of whose strings are of exponential length to be tree ...
Checking automata and one-way stack languages
A checking automaton is equivalent to a one-way nonerasing stack automaton which, one it enters its stack, never again writes on its stack. The checking automaton languages (cal) form a full AFL closed under substitution. If L@?a^* is an infinite cal, ...
Checking automata and one-way stack languages
SWAT '68: Proceedings of the 9th Annual Symposium on Switching and Automata Theory (swat 1968)A checking automaton is equivalent to a one-way nonerasing stack automaton which, once it enters its stack, never again writes on its stack. The checking automaton languages (cal) form a full AFL closed under substitution. If L ⊆ a* is an infinite cal, ...
Comments