Пример 9.2.

По заданному табличному представлению автомата построить систему его команд.

Пусть конечный автомат имеет алфавиты X = {a, b}, Y = {а, b, с}, Q = {1, 2, 3}, а автоматные функции задаются таблицами:

Представленные две таблицы можно объединить в одну, условившись в каждую клетку на первую позицию ставить значение Y(q_r, x_k), а через запятую на вторую позицию помещать значение Q(q_r, x_k). В результате получится следующая «сводная» таблица:

Видно, что таблица стала весьма напоминать таблицу, задающую функциональную схему машины Тьюринга (см. п.7.3.3). Из нее легко просматриваются команды преобразования, осуществляемые данным автоматом:

Пусть на начальном такте автомат находится в состоянии q₀ = 1 и на его вход в последующие такты подается последовательность abb. Пользуясь перечнем команд можно установить, что автомат преобразует эту последовательность в bсс и при этом окажется в состоянии 3.

Другой вариант описания автоматных функций - графический. Он обладает большей наглядностью, чем табличный. Состояния автомата <X, Y, Q, Y, Q> задается посредством ориентированного графа, который называется диаграммой (точнее, диаграммой Мура). Вершины графа помечены символами из алфавита состояний автомата Q, а каждой команде q_ix_r → q_jy_s соответствует ребро, идущее из вершины q_i в вершину q_j, при этом ребру приписывается метка x_ry_s. Таким образом, ребро возникает в том случае, если автомат, находящийся в состоянии q_i, посредством некоторого входного сигнала x_r может быть переведен в состояние q_j. Если такой перевод возможен при нескольких входных воздействиях (х_г)⁽¹⁾..... (х_r)^(п), и при этом формируются выходные сигналы (y_s)⁽¹⁾,..., (y_s)^(п), то ребру приписывается выражение ((х_r)⁽¹⁾, (y_s)⁽¹⁾) v ((х_r)⁽²⁾, (y_s)⁽²⁾) v...v((x_r)⁽ⁿ⁾,(y_s)⁽ⁿ⁾.

Для диаграмм, представляющих конечный автомат, справедливы следующие утверждения:

1. из одной вершины не может выходить двух ребер с одинаковым входным символом (условие однозначности);

2. если при работе автомата реализуется входная комбинация q_ix_r, то обязательно существует ребро, идущее из вершины q_i помеченное символом х_r (условие полноты);

3. количество вершин и ребер диаграммы является конечным.

Контрольные вопросы и задания

Пример А.1

Перевод дробных чисел из одной системы счисления в другую

Пример 10.1

Вернуться в оглавление: Теоретические основы информатики