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 t...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.展开更多
基金the Special Funds for the Major State Basic Research Projects.
文摘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.
