论文部分内容阅读
S. Wolfram initiated the use of formal languages and automata theory in study of cellular automata (CAs). By means of extensive experiments with computer, he classified all CAs into four classes and conjectured that the limit languages of the third class of CAs, which produce chaotic aperiodic behavior, are not regular. Using symbolic dynamics and formal languages, we prove that the limit language of the elementary CA of rule 122 is neither regular nor context-free.
S. Wolfram initiated the use of formal languages and automata theory in study of cellular automata (CAs). By means of extensive experiments with computer, he classified all CAs into four classes and conjectured that the limit languages of the third class of CAs, which produce chaotic aperiodic behavior, are not regular. Using symbolic dynamics and formal languages, we prove that the limit language of the elementary CA of rule 122 is neither regular nor context-free.