jwl@ernie.Berkeley.EDU (James Wilbur Lewis) (02/06/88)
In article <5409@burdvax.PRC.Unisys.COM> dowding@macbeth.PRC.Unisys.COM (John Dowding) writes: > >Is there a name for the class of automata that only move >left-to-right through the input string? Well, the complement of this class of automata are referred to as "two-way automata" (as in 2DFA, 2NFA, 2PDA, etc..), so "one-way automata" would probably be OK (but redundant for most of these classes of machines). There are classes of machines characterized as "one-way stack automata". > What >properties does the class of languages accepted by this class of >automata have? Well, to phrase it slightly differently: 2DFA's and 2NFA's both accept exactly the regular languages. 2DPDA's are known to accept non-CF languages (e.g. {0^n1^n2^n | n >= 1}). Any language accepted by a 2DPDA is recognizable in linear time on a computer. As of 1979 (my edition of Hopcroft and Ullman), the existence of a CFL not accepted by a 2DPDA was an open question. I don't know anything about "1TM"s.... -- Jim Lewis U.C. Berkeley