Parallel Formal-Language Recognition by Cellular Automata

6 Parallel Formal-Language Recognition by Cellular Automata 

Smith (1972) studied one-dimensional r = 1 bounded CAs (BCAs)—CAs with two special boundary cells. The rightmost non-boundary cell was designated to be the accept cell. A BCA is said to accept language L if, for all words x in L, there is a time t such that the accept cell goes into an accept state, and for all words X not in L, there is no such time t. A BCA is said to accept language L in real time if, for any word x of length n, the CA can determine that x is in L within n steps. 

A second example is a bounded CA that recognizes the context-sensitive language L2 = 1 in real time. Smith s construction is illustrated in Fig- 

Many of Smith s results on language recognition have been generalized to CAs of more than one dimension by Seiferas (1977) and by Pecht (1983). 

---