We propose one- and two-dimensional cellular automata as a generative device aimed to describe (one-way) infinite one- and two-dimensional words. Each infinite word can be described by a single infinite computation generating its growing prefixes. The finitary one-dimensional version of the model describes precisely the class of context-sensitive languages.
展开▼
