Arnold L. Rosenberg
Abstract
An operator precedence language which is not real-time definable by any multitple Turing machine is constructed. This strengthens previous results about the existence of unambiguous context-free languages (CFL's) which are not real-time definable. In contrast, a family of CFL's of increasing degree of inherent ambiguity, each real-time definable by a one-tape Turing machine, is exhibited. In fact, an unboundedly ambiguous CFL, also real-time definable by a one-tape Turing machine, is presented. These results are the basis for the assertion that real-time definability of a CFL is independent from each of the structural properties considered.
- 1 BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwissen. Kommunikalionsforsch. 1 (1961), 143-172; reprinted in Bar-Hillel, Y., Language and Information, Addison-Wesley, Reading, Mass., 1965, Ch. 9, pp. 116--150.Google Scholar
- 2 FLOYD, R.W. Syntactic analysis and operator precedence. J. ACM 10 (1963), 316--333. Google Scholar
- 3 GINSBUaO, S., AND GrmIBACH, S. Deterministic context free languages. Inform. Contr. 9 (1966), 620--648.Google Scholar
- 4 -- AND ULLIAN, J. Ambiguity in context free languages. J. ACM 13 (1966), 62-89. Google Scholar
- 5 HARVUANIS J., AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285---306.Google Scholar
- 6 ROSENBERG, A.L. Real-time definable languages. J. ACM 1 (1967), 645--662. Google Scholar
- 7 Degrees of inherent ambiguity in context-free languages. IBM Res. Rep. RC-1878, 1967.Google Scholar
Index Terms
- On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages
Recommendations
Limited Automata and Context-Free Languages
Non-Classical Models of Automata and Applications VLimited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence ...
Comparing linear conjunctive languages to subfamilies of the context-free languages
SOFSEM'11: Proceedings of the 37th international conference on Current trends in theory and practice of computer scienceLinear conjunctive grammars define the same family of languages as one-way real-time cellular automata (Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable to ...
Linear context free languages
ICTAC'07: Proceedings of the 4th international conference on Theoretical aspects of computingIn this paper, I present the class of linear context free languages (LCFLs) with a class of non-deterministic one-way two-head (read only) automata, called non-deterministic linear automata (NLA). At the begining of the work of an NLA, the reading heads ...
Comments