Вычислительные свойства сетей клеточных автоматов

Abstract

У статті описується новий метод аналізу поведінки клітинного автомату. Запропоновано ізоморфне відображення клітинного автомату у кінцевий автомат із виходом. Для побудованого кінцевого автомату знайдений регулярний вираз, який визначає реглярну мову кінцевого автомату із виходом.

In this paper a new analysis technique of cellular automaton behavioris developed. Isomorphs mapping of cellular automaton to a finite-state machine is proposed. Regular expression for developed finite-state machine is found, which defines a regular language of this finite-state machine with outs.