Может ли состояние в конечном автомате генерировать событие?

Я предпочитаю этот способ визуализации FSM в программном обеспечении.

         Start

           |

       =Initial=   <---------------------------------
     --------------                                 |
    | Transition 1 | --------->     =State 2=       |
     --------------              ---------------    |
    | Transition 2 | -------    |  Transition   | --|
     --------------        |     ---------------    |
                           |                        |
                           |                        |
                           |                        |
                           --->     =State 3=       |
                                 ---------------    |
                                |  Transition   | ---
                                 ---------------

В этом сценарии состояние Initial будет выполняться по некоторому пути, который затем может перейти в состояние Transition 1 или Transition 2. Transition 1 запускается State 2, а Transition 2 запускается State 3. Состояние Initial может генерировать событие, указывающее, что оно примет переход Transition 1, и тогда ваша структура сможет выполнить этот переход.

Вы также заметите, что у меня нет конца в этом FSM. Нужен конец или замкнутая петля.

С точки зрения вычислительной теории единственная функция «чистого» конечного автомата состоит в том, чтобы преобразовать строку ввода в выбор «один из N» (в большинстве иллюстраций это выбор «один из двух» (принятие или отклонение). , но большие конечные значения работы N концептуально одинаковы). Два чистых конечных автомата эквивалентны, если для любой последовательности входных символов они будут возвращать один и тот же результат «один из N». Шагом вперед по сравнению с чистым конечным автоматом является преобразователь с конечным числом состояний, в котором каждое ребро может вызвать отправку произвольного количества символов в выходной поток, который не влияет на какие-либо будущие переходы между состояниями. Две такие машины эквивалентны, если для любой последовательности входных символов они будут генерировать одну и ту же последовательность выходных символов и возвращать один и тот же результат «один из N».

Имея два чистых конечных автомата или два чистых преобразователя с конечным числом состояний, можно за разумное ограниченное время определить, эквивалентны ли они (если два преобразователя, меньший из которых имеет N состояний, будут давать одну и ту же последовательность выходов для любого входа последовательность до 2N символов, они будут создавать одну и ту же выходную последовательность для любой входной последовательности для любой входной последовательности любой длины). Тот же подход можно использовать, если машинам состояний разрешено генерировать «события», которые, в свою очередь, могут влиять на их входы, но две машины считаются эквивалентными только в том случае, если они генерируют одну и ту же последовательность событий, и если предполагается, что все комбинации входов быть возможным независимо от генерируемых событий. С другой стороны, если есть какое-то событие, которое может каким-то образом повлиять на ввод конечного автомата, но не представляет интереса для пользователя автомата, или если определенные последовательности событий будут означать, что определенные последовательности входов не могут произойти , может быть очень сложно (или даже практически невозможно) определить, эквивалентны ли две машины, которые могут различаться в том, что не волнует пользователя, в том, что его интересует.

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

Существует множество различных определений и моделей конечных автоматов.

В аппаратном дизайне говорят о машинах Мили и машинах Мура, которые различаются тем, какие из различных проводов ведут обратно к входам...

В программном обеспечении FSM определены менее строго. Весь компьютер в некотором смысле представляет собой одну большую конечную машину. Много кода реализует конечный автомат как простой оператор switch и может также отправлять или не отправлять события самому себе.

Популярным определением программных конечных автоматов является конечный автомат UML (что хорошо, потому что он также поставляется с предпочтительным форматом изображения). ">http://en.wikipedia.org/wiki/UML_state_machine

Конечные автоматы UML могут иметь действие entry() и действие exit() для каждого состояния. В зависимости от реализации эти действия могут публиковать дополнительные события.

Итак, «Может ли FSM вызвать переход»? Зависит от определения или реализации. В общем конечно!