Вопрос 2. Способы задания АП

Задание конечного АП состоит в описании элементов множества А одним из трёх способов: табличным, графическим и матричным.

2.1.Табличный способ

При табличном способе автомата Мили функции переходов и выходов описываются таблицами переходов и выходов соответственно или совмещенными таблицами переходов и выходов.

Пример 1

V={v1, v2} S={s0, s1, s2, s3} W={w0, w1, w2}

Используя таблицу, рассмотрим работы АП. последовательно входные сигналы v1v2v2v1v2v2. На выходе автомата появится выходные сигналы w1w2w3w2w1w1 и автомат будет переходить в состояния s0s1s1s1s2s2s2.

Порядок функционирования АП:

1. Начиная с t=0 на вход конечного автомата, установленного в состояние s0, поступают последовательно входные сигналы.

2. Тогда под действием i-ого сигнала на выходе автомата появится выходной сигнал w_i=λ(s_i-1, v_i), а сам автомат перейдёт в состояние s_i=δ(s_i-1, v_i).

При табличном способе задания автомата Мура используется одна таблица переходов, в которой каждому столбцу, кроме состояния, задаётся выходной сигнал.

На практике часто условия функционирования ЦАП может быть задано совмещенной таблицейпереходов-выходов с линейной структурой. Каждый переход определяется одной его строкой.

Автомат Мили

2.2.Графический способ

Наиболее наглядный. Автомат передается направленным графом. Вершины графа указывают состояние автомата, ветви – переходы (отображают входные сигналы, участвующие в переходе).

2.3.Матричный способ

Автомат Мили задаётся квадратной матрицей М, строки которой соответствуют исходным состояниям, а столбцы – состояниям перехода. В узлах – входной сигнал и выходной сигнал. Если не возможен переход – прочерк.

M =

Автомат Мура задаётся матрицей, в узлах которых находятся только значения входного сигнала, а выходной сигнал описывается векторами выходов.

W = ; M=