Вс. Апр 14th, 2024

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

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

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

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

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

Другой вариант описания автоматных функций — графический. Он обладает большей наглядностью, чем табличный. Состояния автомата <X, Y, Q, Y, Q> задается средством нацеленного графа, который именуется диаграммой (поточнее, диаграммой Мура). Верхушки графа помечены знаками из алфавита состояний автомата Q, а каждой команде qixr → qjys соответствует ребро, идущее из верхушки qi в верхушку qj, при всем этом ребру приписывается метка xrys. Таким образом, ребро появляется в этом случае, если автомат, находящийся в состоянии qi, средством некого входного сигнала xr может быть переведен в состояние qj. Если таковой перевод вероятен при нескольких входных воздействиях (хг)(1)….. r)(п), и при всем этом формируются выходные сигналы (ys)(1),…, (ys)(п), то ребру приписывается выражение ((хr)(1), (ys)(1)) v ((хr)(2), (ys)(2)) v…v((xr)(n),(ys)(n).

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

  1. из одной верхушки не может выходить 2-ух ребер с схожим входным эмблемой (условие однозначности);
  2. если при работе автомата реализуется входная композиция qixr, то непременно существует ребро, идущее из верхушки qi помеченное эмблемой хr (условие полноты);
  3. количество вершин и ребер диаграммы является конечным.

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *