Практика 12

В этоq практике мы сосредоточимся на построении самого автомата и его тестирование. В следующем задании вам уже предстоит применить его.

Абстрактный конечный автомат

state machine

В англоязычной литературе термин известен, как FSM - Finite State Machine.

АКА - абстрактный автомат, число возможных состояний которого конечно [1]. Абстрактный автомат - математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящийся в одном состоянии из множества возможных [2].

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

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

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

Основные идеи

Перечислим основные концепции:

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

Ситуации

Когда необходимо применять автомат? Как минимум, когда у вас начинают получаться конструкции похожие на эту[6]:

switch( state ) {
    case RADIO:
        switch(event) {
            case mode:
              /* Change the state */
              state = CD;
              break;
            case next:
              /* Increase the station number */
              stationNumber++;
              break;
        }
        break;
    case CD:
        switch(event) {
            case mode:
              /* Change the state */
              state = RADIO;
              break;
            case next:
              /* Go to the next track */
              trackNumber++;
              break;
        }
        break;
}

Мы видим здесь, что система может находиться в 4 состояниях, между которыми можно как-то переключаться. Чем плох этот код, он же решает свою задачу? Основная проблема - невозможность расширения кода. Добавление нового состояния, например MP3, или кнопки pause, привёдет к необходимости вдумчиво читать код с вложенными switch блоками, анализировать к чему приведёт новое состояние и так далее. Этого можно избежать если разделить код на составляющие: собственно код, отвечающий за переходы между состояниями и код - обработчиков самих состояний.

Тогда нам нужны:

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

Задание Easy

Создайте конечный автомат с 3 состояниями. Можете пока не гнаться за абстракциями, но конструкции switch и подобные использовать запрещено. Наш простой автомат будет работать с алфавитом $A = {0, 1}$ и должен иметь три состояния q1, q2, q3. Описание состояний:

q1 это наше начальное состояние, начинаем чтение входных команд с него
q2 это наше конечное состояние, мы возвращаем True, если это последнее состояние нашей системы.

Переходы автомата:

q1 переходит в q2, если пришла 1 и остается в q1 если пришел 0.
q2 переходит в q3, если пришел 0 и остается в q2 если пришла 1.
q3 переходит в q2 при любом входе.

Программа в результате должна выдать true или false, в зависимости от того, будет ли конечное состояние автомата q2 или нет. Напишите достаточное количество тестов для проверки работоспособности системы.

Нарисуйте граф переходов, чтобы было проще понять задачу.

Пример использования

a = Automaton()
a.readCommands([1,0,0,1,0])
"""
Будут выполнены следущие переходы.

input: ["1", "0", "0", "1", "0"]

1: q1 -> q2
0: q2 -> q3
0: q3 -> q2
1: q2 -> q2
0: q2 -> q3
"""

Задание Splitter

Напишите функцию split(text: str, separator: str) -> list, которая разбивает строку на массив строк по определенному разделителю. Внутри должен использоваться абстрактный автомат. Желательно, чтобы это был тот же автомат что и из предыдущего задания, только с другим списком состояний, переходов и алфавитом.