Пример 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. количество вершин и ребер диаграммы является конечным.

Любому неструктурному алгоритму может быть построен эквивалентный ему структурный алгоритм.

Энтропия сложного опыта, состоящего из нескольких независимых, равна сумме энтропии отдельных опытов.

Пример 4.17

Способы представления алгоритмов

Строчная словесная запись алгоритма

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