One-Way Bounded Cellular Acceptors.
Charles R. Dyer · 1978
The formal language recognition capabilities of one-dimensional one-way bounded cellular automata are studied. In particular, their relationships to real-time two-way bounded cellular acceptors, real-time iterative acceptors, real-time on-line multitape Turing acceptors, and one-way multihead finite acceptors are investigated. It is shown that the Dyck, linear, standard, and bracketed context-free languages are accepted in real-time by one-way bounded cellular acceptors. (Author)