Formal Languages and Finite Cellular Automata
Formal Languages and Finite Cellular Automata
复制标题
形式语言和有限元胞自动机
作者：
M. Nordahl
.一维元胞自动机规则与特定的边界条件可以被认为是同时作用于所有有限格，这给出了一个形式语言之间的映射。正则语言总是映射到正则语言，上下文无关映射到上下文无关，上下文敏感映射到上下文敏感，递归集映射到递归集。特别地，有限格上的有限时间集是正则语言。有限格（周期集）上的限制集被证明是既不是一个定期的，也不是一个明确的上下文无关的语言，某些添加剂的规则与混乱的行为，并为规则，可以模拟这些添加剂的规则之一，通过有限的块变换。讨论了有限格和无限格上的元胞自动机之间的关系。
. A one-dimensional cellular automaton rule with specified boundary conditions can be considered as acting simultaneously on all finite lattices, which gives a mapping between formal languages. Reg ular languages are always mapped to regular languages, context-free to context-free, context-sensitive to context-sensitive, and recursive sets to recursive sets. In particular, the finite time sets on finite lattices are regular languages. The limit set on finite lattices (the periodic set) is shown to be neither a regular nor an unambiguous context-free language for certain additive rules with chaotic behavior, and for rules that can simulate one of these additive rules through a finite blocking transformation. The relation between cellular automata on finite and infinite lattices is discussed.