Глава 1. Определение конечного автомата

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

Теория автоматов - это раздел дискретной математики, который посвящен автоматным моделям реальных устройств, предназначенных для обработки дискретной информации с помощью заданного алгоритма, без учета их физических или технических характеристик.

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

Переход автомата из одного состояния в другое и выдача выходного сигнала происходят дискретно и мгновенно в определенные моменты времени. Эти моменты времени следуют один за другим через фиксированный промежуток времени - такт.

Введем следующие понятия и обозначения. Входной алфавит А - это конечное множество A = {а_1, а₂,...,а_s}, элементы которого называются входными сигналами (символами). Выходной алфавит В= {b₁, b₂,..., b_k } - это множество выходных сигналов (символов). Будем считать, что в каждый момент времени t= 1, 2, 3,... на вход автомату подается некоторый сигнал из множества A, а на выходе появляется соответствующий сигнал из множества В. Тогда, учитывая описанный выше потактовый принцип работы абстрактного автомата, входной сигнал в момент времени t будем обозначать через х(t), а в следующий момент - через х(t+1). Соответствующие выходные сигналы обозначим через у(t) и у(t+1). Иногда входной и выходной алфавиты совпадают. Множество состояний - это конечное множество V= { v_1,v₂,...,v_r }. Состояние автомата в момент времени t будем обозначать через q(t).

Рис.1

На рис. 1 изображена структура абстрактного автомата. За один такт его работы происходят следующие события. В момент времени t (начало t- го такта) в функциональный блок синхронно поступают два сигнала: х(1) - по входному каналу и q(t- 1) - из памяти автомата. В функциональном блоке эти сигналы мгновенно перерабатываются в два новых сигнала у(t) и q(t). Сигнал у(t) направляется в выходной канал, а сигнал q(t) - в память автомата. После этого наступает момент времени t +1, который служит одновременно окончанием t -го такта и началом следующего (t + 1)-го такта. Поскольку первый такт начинается в момент времени t = 1, то сигнал q (0), поступающий в этот момент из памяти автомата в функциональный блок, характеризует начальное состояние автомата, которое обычно считается известным заранее (например, можно считать, что автомат стартует с «чистой» памятью). Пару сигналов (х(t), q (t - 1)) можно сравнить со «стимулом» в момент времени t, а пару (у(t). q(t)) - с мгновенной «реакцией» автомата на этот «стимул».

В приведенном выше описании одного такта работы автомата сказано, что в функциональном блоке сигналы х(t) и q(t-1) мгновенно перерабатываются в новые сигналы у(t) и q(t). Поэтому между парой х(t) и q(t-1), с одной стороны, и парой у(t) и q(t), с другой стороны, существует зависимость.

Определение. Автомат называется детерминированным, если для любых t и t' из равенств х(t) = х(t') и q(t- 1) =q(t'- 1) следуют равенства у(t)= у(t'),q(t) = q(t').

Свойство детерминированности автомата означает, что принципы его функционирования с течением времени не меняются. Образно говоря, реакция детерминированного автомата на один и тот же стимул всегда одинакова и не зависит от момента времени. У недетерминированных автоматов сигналы у(t) или q(t) определены неоднозначно. Детерминированные автоматы лучше, чем недетерминированные, подходят для описания реальных устройств. Далее мы будем рассматривать только детерминированные автоматы.

Пример 1. Пусть A = {а _{1 ,} а₂,а₃}- входной алфавит, В= {b₁, b₂, b₃ } - выходной алфавит, а V= { v_1,v₂ } - множество состояний автомата.

Рассмотрим правила его функционирования:

(а₁, v₁)®(b_1, v₁), (а _1,v₂) ® (b_1, v₂),

(а₂, v₁)®(b_2, v₁), (а _2,v₂) ® (b_1, v₁),

(а₃, v₁)®(b_3, v₂), (а _3,v₂) ® (b_3, v₂).

Например, запись (а₃, v₁)®(b_3, v₂) означает следующее: если в начале такта автомат находится в состоянии v₁ и на вход ему подается сигнал а₃, то в конце такта на выходе автомата окажется сигнал b₃. и автомат перейдет в состояние v₂. Анализируя всю систему правил, можно узнать, как данный автомат обрабатывает ту или иную последовательность входных сигналов. Например, требуется выяснить, какие сигналы y (1), у(2), у(3) будут последовательно появляться на выходе автомата, если на вход ему подать последовательно х (1) = а₂, х(2) = а₁, х (3) = а₃. Возможны два варианта: в начальный момент t = 1 автомат находится в состоянии v₁ или v₂. Рассмотрим каждый из них отдельно.

Пусть автомат стартует в состоянии v₁ т.е. q (0) =v₁. Тогда согласно правилу(а₂, v₁)®(b_2, v₁), получаем y (1) =b₂, q (1) = v₁. Далее используем правило (а₁, v₁)®(b_1, v₁)и получаем y (2) = b₁, q(2) = v₁. Наконец, применяя правило (а₃, v₁)®(b_3, v₂), получаем y (3) =b₃, q(3) = v₂. Таким образом, выходная последовательность будет иметь вид b₂, b₁, b₃. Заметим, что параллельно мы установили порядок, в котором менялись состояния автомата (включая стартовое состояние) - v₁, v₁, v₁, v₂.

Пусть теперь автомат стартует в состоянии v₂, т.е. q (0) = v₂. Тогда, исходя из правила (а _2,v₂) ® (b_1, v₁),, получаем у(1) = b₁, q(1)= v_1. Затем используем правило (а₁, v₁)®(b_1, v₁)и получаем у(2) = b_1,, q(2) = v₁. Наконец, применяя правило (а₃, v₁)®(b_3, v₂), получаем y (3) =b_3,, q(3) = v₂. Последовательность выходных сигна­лов в данном случае имеет видb₁, b₁, b₃, а последовательность со­стояний автомата (включая стартовое) – v₂, v₁, v₁, v₂.

Если символам а _{1 ,} а₂, а₃, b₁, b₂, b₃ и состояниям v₁, v₂ придать какой-либо содержательный смысл, то с помощью автомата можно будет моделировать поведение реального объекта. Рассмотрим несколько идеализированную семью, в которой муж может находиться в двух состояниях:

v₁ = «муж сердит»,

v₂ = «муж счастлив».

Жена воздействует на мужа тремя способами:

а ₁ = «жена молчит»,

а₂ = «жена ругается»,

а₃ = «жена готовит любимое блюдо мужа».

Муж по-разному реагирует на эти воздействия:

b₁ = «муж молчит»,

b₂ = «муж хмурится»,

b₃= «муж улыбается».

Теперь каждое правило из описания данного автомата приобрело вполне конкретное содержание. Например, запись (а _2,v₂) ® (b_1, v₁) означает, что если жена начнет ругаться, когда муж счастлив, то муж рассердится, но будет молчать. Правило (а₃, v₁)®(b_3, v₂) можно перевести так: если жена начнет готовить любимое блюдо мужа, когда тот сердит, то он станет счастливым и будет улыбаться.

Выше мы установили, что последовательности входных сигналов а₂, а_1, а₃ соответствует последовательность выходных сигналов b_2,b_1,b₃ и состояний автомата (включая стартовое) -v_1,v_1,v_1,v₂. Теперь этот факт можно интерпретировать следующим образом: если муж сердит, а жена ругается, то муж в ответ хмурится, оставаясь сердитым; если после этого жена умолкает, то муж тоже молчит, хотя и продолжает сердиться; наконец, когда жена начинает готовить любимое блюдо мужа, он становится счастливым и начинает улыбаться. Подобных сценариев можно придумать много. Таким образом, данный автомат моделирует поведение мужа, которое зависит от его внутреннего состояния и действий со стороны жены.

Определение. Функцией выходов автомата называется функция f, которая каждой паре (a_i, v_j), где a_iÎA, v_jÎV, ставит в соответствие вы­ходной сигнал f (a_i, v_j)ÎВ.

Функция выходов указывает, какой сигнал будет направлен на выход автомата, если он находился в состоянии v_j, и на вход ему по­ступил сигнал a_i.

Определение. Функцией переходов автомата называется функция g,которая каждой паре (a_i, v_j), где a_iÎA, v_jÎV, ставит в соответствие состояние g (a_i, v_j)ÎV.

Функция переходов указывает, в каком состоянии окажется авто­мат, если он находился в состоянии v_j, и на вход ему поступил сигнал a_i.

Используя эти функции, можно в иной форме задать правила функ­ционирования автомата из примера 1. Так, запись (а₃, v₁)®(b_3, v₂)можно заменить двумя равенствами f (a₃, v₁) = b₃, g (a₃, v₁) =v₂. Пример 1 показывает, что функции выходов и переходов - это необязательно числовые функции, поскольку входные и выходные сигналы не обязательно являются числами. Заметим также, что двух этих функций вполне достаточно, чтобы полностью описать работу детерминированного автомата.

Определение. Конечным автоматом (или автоматом Мили) называется система из пяти компонент (А, В, V, f, g), где А и В - это входной и выходной алфавиты автомата, V - множество его состояний, f - функция выходов, а g - функция переходов автомата, причем все множества A, В и V конечны.

Дата добавления: 2015-11-30