Пример 3.1

Методы задания автоматов.

Чтобы задать конечный автомат S, необходимо описать все элементы множества S={X, Y, A, f, g, a⁽⁰⁾}, т.е. входной и выходной алфавиты и алфавит состояний, а такие функции переходов и выходов. Среди множества состояний необходимо выделить начальное состояние а⁽⁰⁾=а₁. Осуществляет несколько способов задания работы автомата, но наиболее часто используются следующие:

1. В виде графа переходов и выходов.

2. В виде таблиц переходов и выходов.

3. В виде матриц переходов и выходов.

Задание автомата в виде графа переходов и выходов.

Граф автомата – ориентированный связный граф. Вершины соответствуют состояниям автомата, а дуги - переходу из состояния a(t) в состояние a(t+1): a_S=f(a_m, x_j)

Изображения графов для автоматов Мура и Мили имеют отличительные особенности (рис. 3.4. и 3.5). У автомата Мура выходной сигнал записывается внутри вершины или рядом с ней, а у автоматов Мили над дугой: или у её конца, при этом входной сигнал изображается в начале дуги, или под входным сигналом. Тогда входной и выходной сигналы отделяются чертой.

На рис. 3.6. и 3.7. приведены графы эквивалентных автоматов Мура S₁ и Мили S₂, определённых на алфавитах x={x₁,x₂,x₃,x₄} и y={y₁,y₂,y₃}. Эти автоматы на любую входную последовательность, оканчивающуюся на x₁x₂(… x₁x₂), формируют выходной сигнал y₂ (… y₂), а на x₁x₂x₃ (… x₁x₂x₃) сигнал y₃ (… y₃). Говорят, что автоматы распознают последовательности x₁x₂ или x₁x₂x₃. Назовём их правильными. Если входные символы не образуют правильной последовательности или пришли не все символы правильной последовательности формируется выходной сигнал y₁.

Задание автомата в виде таблиц переходов и выходов.

Описание автоматов в виде таблиц демонстрируется рис. 3.8. и 3.9, где изображены таблицы переходов и выходов эквивалентных автоматов Мура S₂ и Мили S₂, графы которых приведены на рис. 3.6 и 3.7.

Строки этих таблиц соответствуют входным сигналам, а столбцы – состояниями, причём крайний левый столбец состояний обозначен начальным состоянием a₁. В таблице переходов внутренняя клетка, находящаяся на пересечении строки и столбца, соответствует состоянию перехода a(t+1).

Для автомата Мили таблица выходов совмещены с таблицей переходов: над чертой в клетке записывается состояние а(t+1), a под ней – выходной сигнал y(t).

Задание автомата в виде матриц переходов и выходов.

Задание автоматов в виде матриц демонстрируется на рис. 3.10 и 3.11, где изображены матрицы рассмотренных выше автоматов S₁ и S₂.

Матрица переходов является квадратной матрицей.

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

Дата добавления: 2014-01-05