Моделирование систем: Учебное пособие (Структуры функциональных математических моделей систем. Общие вопросы математического моделирования систем), страница 19

З а м е ч а н и е 4.13. В терминологии алфавитов работа  автомата состоит в преобразовании входного слова в выходное слово (а также в получении слова состояний).  

        На рис. 4.1 приведена схема  функционирования  некоторого конечного автомата в течении первых трех тактов, заданными  множествами  X= (x₁, x₂ ), Z = (z₀ , z₁, z₂) , Y = (y₁, y₂) и некоторыми функциями y и  j.

Рис. 4.1

Рассмотрим теперь компоненты математической модели, описывающие динамику автомата. Такая модель задается двумя рекуррентными формулами, позволяющими по заданному значению z₀ , получить последовательности значений z(t) и y(t) для нулевого, первого, второго и последующих тактов.

Для конечного автомата первого рода, называемого также автоматом Мили, такие формулы  имеют вид:

z(t+1) = j[z(t), x(t)] ,    t =0,1,2,3…                                            (4.11)

y(t) = y[z(t), x(t)] ,    t =0,1,2,3…                                           (4.12)      

Первое из этих соотношений задает  функцию переходов, определяющую состояние автомата z(t+1) в момент дискретного времени t+1 в зависимости от состояния автомата z(t) и значения входного сигнала x(t) в момент времени t. Второе соотношение задает функцию выходов, определяющую зависимость выходного сигнала автомата y(t) от состояния автомата и входного сигнала x(t) в момент времени t.

Для F-автомата второго рода:

z(t+1) = j[z(t), x(t)]  ,         t=0,1,2,3…                                         (4.13)

y(t) = y[z(t), x(t-1)] ,       t=1,2,3…                                            (4.14)

Имеется частный случай  автомата второго рода, у которого  функция выходов не зависит от входного сигнала. Функция выхода для такого автомата задается рекуррентной формулой  вида

y(t)=y[z (t)]  ,  t=0,1,2,3…                                               (4.15)

Такой автомат называется автоматом Мура.

З а м е ч а н и е 4.14. В литературе приводятся несколько различных видов формул (4.11)-(4.14), отличающиеся нумерацией моментов времени, использующихся в левых и правых частях рекуррентных формул.

Существуют автоматы, имеющее только одно состояние. Такие автоматы считаются автоматами без памяти. Они называются также комбинационными или логическими схемами. Работа логической схемы заключается в том, что она ставит в соответствие каждому входному сигналу определенный выходной сигнал, т. е. реализует логическую функцию вида

y(t) = y[x(t)]   , t=0,1,2,….

Если алфавиты  X и  Y  состоят из двух букв, то такая  функция называется булевой.

Формализованная математическая схема, описывающая конечный автомат как совокупность трех конечных множеств, двух отображений и одного элемента множества вида

F = < X ,Y, Z , j , y , z₀  >

неудобна для реализации моделирования процесса функционирования автомата.

В связи с этим используются другие, менее формализованные способы задания автомата. Обычно используются три способа задания F-автоматов: 1) табличный, 2) графический ,  3) матричный.

Табличный способ задания конечного автомата.

Способ основан на использовании таблиц переходов и выходов. Строки таких таблиц соответствуют входным сигналам автомата, а столбцы - его состояниям.  Используются также совмещенные таблицы переходов и выходов. Общий вид таких таблиц приведен в [3].

Рассмотрим идею задания таблиц на примере.

Пусть F-автомат характеризуется следующими  тремя  множествами:

X = (x₁ ,x₂ ) , Y  (y₁ , y₂ ), Z (z₀ , z₁ , z₂ )  (z₀ –начальное состояние) . 

Автомат характеризуется следующей совмещенной таблицей переходов и выходов (табл.4.1)

         Таблица 4.1

Z       X	z0	z1	z2
x1	z2 y1	z0 y1	z0 y2
x2	z0 y1	z2 y2	z1 y1