Конечные автоматы

Конечные автоматы

На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка (Q, ∑, ∆, δ, Г), где

Q — конечное множество состояний {q₁, q₂,…, q_k};

∑ — конечный входной алфавит;

∆ — конечный выходной алфавит;δ : Q х ∑ → Q — функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние; Г : Q х ∑→∆ — функция выхода, отображающая текущее состояние и текущий вход в выходной символ.

Автоматы часто представляют в виде графов переходов, как, на­пример, на рис. 3.9. В графе переходов состояния представляются кружками, являющимися вершинами. Дуга из состояния q_i в q_j помеченная a|b, означает, что, находясь в состоянии q_i автомат при входе а перейдет в состояние q_j выдавая при этом символ b. Формально следовало бы записать

δ(q_i ,a)=qj и Г (q_i ,a)=b

Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир.

Рекомендуемые материалы

В качестве примера рассмотрим автомат, изображенный на рис. 3.9. Этот автомат преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнение до двух. В данном случае входной и выходной алфавит состоит из трех символов: 0, 1 и R. Автомат начинает работать в состоянии q_t. Сим­вол сброса (R) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

Аналогичный автомат показан на рис. 3.10. При тех же самых входах этот автомат вычисляет четность входного числа. Он начи­нает работу в состоянии q₁. Выход копирует вход до тех пор, пока входным символом не окажется символ сброса. Выходом для сим­вола сброса будет 0 в случае нечетного числа и 1 — в случае чет­ного числа.

При представлении конечного автомата сетью Петри следует об­ратить внимание на связь между сетью Петри и внешним миром, которая ранее не учитывалась. Моделирование взаимодействия с внешним миром можно реализовать многими способами. В нашей задаче мы моделируем это взаимодействие с помощью специаль­ного множества позиций. Позициями будут представлены каждый входной и выходной символы. Мы допускаем, что из внешнего мира помещается фишка в позицию, соответствующую входному символу, а затем фишка, появившаяся в позиции, соответствующей выход­ному символу, удаляется оттуда. Эта последовательность действий будет повторяться необходимое число раз. Общая схема проиллюст­рирована на рис. 3.11.

Заметим, что здесь не исключена возможность путаницы в по­нятиях, так как позиции, соответствующие входным и выходным символам, могут быть обоснованно названы входными и выходными Позициями сети. Однако их не следует путать с входными или вы-

ходными позициями переходов. Несмотря на возможную путаницу, эти термины наиболее естественны для обоих понятий.

В качестве альтернативного подхода к моделированию входов и выходов сети могут быть использованы переходы. Для определения следующего входного символа из внешнего мира следует выбирать входной переходи запускать его. Сеть Петри ответит (в конце концов) запуском соответствующего перехода из множества выходных пере­ходов, связанного с соответствующим выходом. Затем из внешнего мира будет запущен новый входной переход и т. д. Этот подход проиллюстрирован на рис. 3.12. Нетрудно показать, что оба этих подхода эквивалентны, поэтому будем использовать первый из них, в котором входные и выходные символы моделируются позициями.

Задав представление позиций, соответствующих символам входа и выхода, мы можем завершить построение модели системы конеч­ных состояний. Представим каждое состояние автомата позицией в сети Петри. Текущее состояние отмечается фишкой; все осталь­ные позиции пусты. Теперь для определения переходов из состоя­ния в состояние можно ввести переходы сети следующим образом. Для каждой пары (состояние и входной символ) мы определяем переход, входными позициями которого являются позиции, соот­ветствующие состоянию и входному символу, а выходными пози­циями — позиции, соответствующие следующему состоянию и вы­ходу.

Для конечного автомата (Q, ∑, ∆, δ, Г) мы определили сеть Петри (Р, Т, I, О) таким образом:

         P = Q∑∆,

         T = {tq,σ|q   и σ  ∑ },

         I(t_q,σ) ={q,σ},

         O(t_q,σ)  = {δ(q,σ), Г(q,σ)}

Эта сеть Петри является моделью конечного автомата.

На рис. 3.13 изображена сеть Петри, соответствующая автомату с рис. 3.9. На рис. 3.14 - cеть Петри, соответствующая автомату с рис. 3.10.

При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3.10 возникают некоторые вопросы. Преж­де всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой 6 переходов, 24 дуги и 7 или 8 по­зиций. Это верно. Однако мы показали, что сети Петри могут пред­ставлять любую систему, представимую автоматом, и это свидетель­ствует о больших возможностях сетей Петри.

Лекция "6 Валовый доход аптечных организаций" также может быть Вам полезна.

Кроме того, следует отметить, что модель сети Петри имеет опре­деленное преимущество при  композиции автоматов.  Например,

заметим, что выходной алфавит автомата с рис. 3.9 идентичен входному алфавиту автомата с рис. 3.10. Передавая выход автома­та с рис. 3.9 на вход автомата с рис. 3.10, можно построить ком­позицию автоматов, вычисляющую дополнение до двух и проверяю

щую четность. Такая композиция является автоматом с составны­ми состояниями, компоненты которых — это состояния обоих под­автоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. На рис. 3.15 показана композиция автоматов, а на рис. 3.16 — со­ставная сеть Петри.

Другое преимущество представления сети Петри связано с ины­ми формами композиции. Например, параллельная композиция позволяет компонентам композиции автоматов работать одновре­менно. В этом случае вновь получаем автомат с составными состоя­ниями, в то время как для сети Петри — это просто дублирование фишек во входах, соответствующих входным символам, и исполь­зование их во всех компонентах сети Петри. Наконец, на выходе мы просто выбираем соответствующие позиции выхода. Например, если мы хотим соединить параллельно две сети Петри (рис. 3.13 и 3.14), то в результате получим сеть Петри, подобную изобра­женной на рис. 3.17, которая вычисляет дополнение числа до двух и его четность. Если на входе появляется символ сброса, то выходом является четность.