A Generalization of Context Free Determinism

摘要

Nondeterministic Turing machines, under the restriction that each square be written on only a fixed number of times, recognize all and only context free languages. The deterministic subclass gives rise to a hierarchical extension of the pushdown deterministic languages. Unambiguity in terms of the machines is the same as grammatical unambiguity. (Author)