habrahabr

Конечные автоматы в реальной жизни: где мы их используем и почему

  • среда, 30 июня 2021 г. в 00:35:31
https://habr.com/ru/company/yandex_praktikum/blog/564800/
  • Блог компании Яндекс.Практикум
  • JavaScript
  • Интерфейсы
  • Математика


Привет, меня зовут Антон Субботин, я выпускник курса «Мидл фронтенд-разработчик» в Яндекс.Практикуме. Не так давно мы с наставником курса Захаром Овчаровым провели вебинар, посвящённый конечным автоматам и их практическому применению. Вебинар получился интересным, а потому по его следам я написал статью для Medium на английском языке. Также есть запись вебинара. Однако мы с Захаром решили сделать ещё кое-что: перевести на русский и немного расширить статью, чтобы вы могли никуда не ходить и прочитать её здесь, на Хабре. Разобрались с предысторией — теперь начнём погружение в мир конечных автоматов.



Конечный автомат с счастливым и грустным Васькой

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


Для начала дадим определение: конечный автомат (finite-state machine, FSM) — это математическая абстракция, модель, которая может находиться только в одном из конечного числа состояний в каждый конкретный момент времени. Автомат умеет переходить из одного состояния в другое в ответ на данные, которые подаются на вход; изменение состояния называется переходом. FSM определяется списком его состояний, начальным состоянием и инпутами, запускающими переходы.

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

  • Состояния. Кот либо счастлив, либо грустен и не может испытывать обе эмоции одновременно.
  • Начальное состояние. Мы предположили, что Васька по умолчанию счастлив.
  • Переходы. Вы можете уйти или прийти, и состояние кота изменится.

Мы также можем изобразить Ваську-автомат на схеме, как в заголовке статьи.

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

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


FSM можно использовать для описания алгоритмов, позволяющих решать те или иные задачи, а также для моделирования практически любого процесса. Несколько примеров:

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

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

Проверка бинарного кода


Создадим наш первый автомат. Посмотрите последний пример по ссылке или пишите код по ходу чтения. Будем реализовывать допускающий автомат с конечным состоянием. Это конечный автомат, цель которого — определить, принадлежит ли некая строка определённому языку, и либо допустить, либо отклонить её. Мы уже обсуждали начальное и другие состояния и переходы, однако теперь потребуется определить ещё два параметра:

  • Алфавит. Набор символов, которые должно содержать проверяемое значение (и ни одного символа вне алфавита).
  • Конечные состояния. Подмножество существующих состояний — возможно, пустое. Когда FSM завершает свою работу, он принимает проверяемое значение, если это подмножество включает текущее состояние, и отклоняет в противном случае.

Поговорим о задаче:

  • Нам нужно создать автомат для проверки случайных значений, который будет отвечать, является ли значение бинарным кодом.
  • Мы принимаем непустые строки с символами 0 и 1 и отклоняем всё остальное.

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

Вот наш автомат, детерминированный акцептор с конечным состоянием:

/**
 * Реализация написана Захаром Овчаровым (https://www.linkedin.com/in/zakhar-ovcharov-a657a4197/)
 * с дополнениями Антона Субботина
 */

class FSM {
  /**
   * У каждого экземпляра класса будет определённый алфавит, список состояний и переходов, которые могут использоваться для проверки значений, подающихся на вход.
   * @param {String} alphabet
   * @param {String[]} states
   * @param {String} startState
   * @param {String[]} finiteStates
   * @param {Object} transitions
   */
  constructor(alphabet, states, startState, finiteStates, transitions) {
    this.alphabet = alphabet
    this.states = states
    this.startState = startState
    this.transitions = transitions
    this.finiteStates = finiteStates
    this.currentState = null
  }

  /**
   * Проверяем, относится ли символ к указанному алфавиту.
   * @param {String} symbol
   * @returns {Boolean}
   */
  _checkIsBelongAlphabet(symbol) {
    return this.alphabet.includes(symbol)
  }

  /**
   * Изменяем текущее состояние в зависимости от символа. Автомат должен прервать работу, если у текущего символа отсутствует переход к текущему состоянию.
   * @param {String} symbol
   */
  _changeState(symbol) {
    if (
      this.transitions[this.currentState] &&
      this.transitions[this.currentState][symbol]
    ) {
      this.currentState = this.transitions[this.currentState][symbol]
    } else {
      throw new Error(`No transition from ${this.currentState} by ${symbol}`)
    }
  }

  /**
   * Проверяем значение по указанным параметрам. Принимаем значение, если finiteStates содержит последнее текущее состояние, и отклоняем, если это не так.
   * @param {String} value
   * @returns {String}
   */
  test(value) {
    this.currentState = this.startState

    for (let symbol of value) {
      if (this._checkIsBelongAlphabet(symbol)) {
        this._changeState(symbol)
      } else {
        return false
      }
    }

    return this.finiteStates.includes(this.currentState)
  }
}

У нас получился автомат на основе классов, способный проверять случайные значения на соответствие своим определениям. Чтобы использовать его, мы должны создать экземпляр со всеми необходимыми параметрами. Давайте разберёмся.

  • Алфавит. Это очень просто. Мы принимаем только символы 0 и 1.
  • Состояния. Это тоже легко. Значение либо бинарное, либо нет. Мы называем состояния q0 («значение — не бинарный код») и q1 («значение — бинарный код»).
  • Начальное состояние. Мы не принимаем пустую строку, поэтому начальное состояние — q0.
  • Конечные состояния отмечают значение как принятое. В нашем случае единственное подходящее состояние — q1.
  • Переходы. См. диаграмму:



Схема акцептора бинарного кода

Помните, что переходы происходят в каждой итерации, и у любого состояния имеются переходы для символов 0 и 1. Это можно интерпретировать так:

  • Если текущее состояние — q0, а текущий символ — 0 или 1, выполнить переход в состояние q1.
  • Если текущее состояние — q1, а текущий символ — 0 или 1, выполнить переход в то же состояние.
  • Если текущий символ не равен 0 или 1, отклонить проверяемое значение независимо от текущего состояния.

Теперь давайте создадим экземпляр FSM и протестируем его:

// Параметры по порядку: алфавит, состояния, начальное состояние, конечное состояние, переходы
// Нужно определить переходы как объект, в котором:
// 1. Ключ — это состояние,
// 2. Значение — это объект, в котором:
// 2.1. Ключ — это символ, 
// 2.2. Значение — это целевое состояние.
const fsm = new FSM('01', ['q0', 'q1'], 'q0', ['q0'], {
  q0: {
    0: 'q0',
    1: 'q0'
  },
  q1: {
    0: 'q1',
    1: 'q1'
  }
})

console.log(fsm.test('111')) // true
console.log(fsm.test('0111')) // true
console.log(fsm.test('1112')) // false, 2 не относится к алфавиту '01'

Использование и тестирование


Получилось! Обратите внимание: нам не нужно указывать все возможные символы для каждого состояния — когда автомат встречает не прописанный в алфавите символ, он заканчивает работу.

Сложная форма


Пример с проверкой бинарного кода — довольно тривиальный. Вряд ли вам часто придётся решать такие задачи, если придётся вообще. Давайте рассмотрим ещё один пример — создадим форму с несколькими состояниями в UI-ориентированном FSM. Код автомата доступен на CodeSandbox, вы можете перейти к нему или попробовать написать его самостоятельно.

Для начала создайте новый проект в React:

create-react-app questionnaire

Структура проекта должна выглядеть так:



App.js и index.js не требуют изменений. FSM.js будет содержать новую реализацию FSM, напишем её:

/**
 * Здесь содержится функция, в основе которой — FSM. Чтобы создать экземпляр, необходимо передать в неё начальное состояние и набор переходов, а функцию subscribe можно использовать для реакции на изменение состояния.

 * @param {String} initialState
 * @param {Object} transitions
 * @returns
 */
export const FSM = (initialState, transitions) => {
  const subscriptions = []
  const subscriptionsRelatedToTriggers = {}

  const machine = {
    state: initialState,

    /**
     * Укажите коллбэк, который будет вызываться после изменения состояния. При желании вы можете передать триггер для вызова коллбэка (только в случае, если состояние изменяется в ответ на триггер).

     * @param {Function} f
     * @param {String} trigger
     */
    subscribe(f, trigger = null) {
      if (trigger) {
        const subscriptionsByTrigger =
          subscriptionsRelatedToTriggers[trigger] || []
        subscriptionsByTrigger.push(f)
        subscriptionsRelatedToTriggers[trigger] = subscriptionsByTrigger
        return
      }

      subscriptions.push(f)
    },

    /**
     * Проверяем текущее состояние на переход по триггеру. Если триггер срабатывает, выполняем переход и запускаем коллбэки подписок.

     * @param {String} trigger
     */
    send(trigger) {
      const currentState = this.state
      const nextState =
        transitions[currentState] && transitions[currentState][trigger]
          ? transitions[currentState][trigger]
          : this.state

      if (nextState !== currentState) {
        this.state = nextState
        subscriptions.forEach((f) => f(this.state))
        const subscriptionsByTrigger = subscriptionsRelatedToTriggers[trigger]
        if (subscriptionsByTrigger) {
          subscriptionsByTrigger.forEach((f) => f(this.state))
        }
      }
    }
  }

  return machine
}

Обратите внимание, что мы удалили алфавит и состояния. Теперь у нас есть только два параметра, которые нужно определить:

  • Начальное состояние. Работа FSM должна где-то начинаться.
  • Переходы. Объединяем их с состояниями — так мы создаём более ёмкий экземпляр, при этом обеспечивая ту же функциональность.

Конечные автоматы универсальны — их можно определить любым подходящим для задачи способом. Пока у нас есть состояния, переходы и начальное состояние, всё в порядке.

Наша реализация обязывает использовать метод send для изменения состояния. Мы также добавили метод subscribe. Это очень полезно, если мы хотим, чтобы автомат реагировал на изменение состояния.

Давайте протестируем код на нашем примере с Васькой. Создайте файл test.js:

import { FSM } from './FSM'

const machine = FSM('happy', {
  happy: {
    leave: 'sad'
  },
  sad: {
    come: 'happy'
  }
})

console.log(machine.state) // happy, it's the initial state
machine.send('leave')
console.log(machine.state) // sad, we left
machine.send('come')
console.log(machine.state) // happy again, we came back!

Теперь запустите его с помощью node test.js (убедитесь, что вы находитесь в каталоге файлов). Вывод на консоли должен выглядеть так:

happy
sad
happy

Автомат определённо работает! Наконец, давайте отреагируем на изменение настроения Васьки:

import { FSM } from './FSM'

const machine = FSM('happy', {
  happy: {
    leave: 'sad'
  },
  sad: {
    come: 'happy'
  }
})

machine.subscribe((state) => {
  if (state === 'sad') {
    console.log(`I can't let you be ${state}, Vasya. I'm going back!`)
    machine.send('come')
  }
})
console.log(machine.state) // счастливый — начальное состояние
machine.send('leave')
console.log(machine.state) // снова счастлив, мы не можем бросить Ваську!

Запустите автомат снова.

happy
happy

Васька теперь всегда счастлив, потому что мы не бросаем его. Если после перехода состояние — грустное, срабатывает триггер возвращения, и кот снова счастлив.

Похоже, всё работает нормально. Переходим к реальной задаче: создадим анкету с несколькими состояниями, которые нужны для управления интерфейсом. Допустим, мы хотим узнать имя и профессию пользователя. Если пользователь — студент, мы спросим, в каком университете он учится. В противном случае спросим, где он работает. Пользователь может вернуться с этапа Education / Work обратно к этапу Personal, на котором мы спрашиваем имя. Наконец, он может отправить анкету при выборе любого из вариантов занятости.

Небольшая диаграмма, чтобы стало понятнее:


Автомат, определяющий нашу анкету

Когда стало ясно, какие состояния у нас есть и как они соотносятся друг с другом, мы можем приступить к работе над проектом. Первое: нужно установить дополнительные зависимости:

npm i animate.css react-transition-group

После завершения установки добавляем директорию /components с компонентами внутри. Также мы создаём файл questionnaireMachine.js в директории /src. Теперь структура проекта выглядит так:



Файл questionnaireMachine.js создаёт и экспортирует экземпляр Questionnaire FSM:

import { FSM } from './FSM'

export const machine = FSM('initial', {
  initial: {
    start: 'personal'
  },
  personal: {
    next: 'occupation'
  },
  occupation: {
    back: 'personal',
    education: 'education',
    work: 'work'
  },
  education: {
    back: 'occupation',
    send: 'loading'
  },
  work: {
    back: 'occupation',
    send: 'loading'
  },
  loading: {
    success: 'success'
  },
  success: {
    reset: 'initial'
  }
})

Questionnaire FSM


Следующим шагом будет создание презентационного слоя проекта — самой анкеты. Мы разделим его на три отдельных компонента:

  • Анкета. Основной компонент, определяющий последовательность вопросов.
  • Карточка. Многоразовый компонент для отображения части анкеты.
  • Прелоадер. Простая анимированная точка.

Начнём с компонента анкеты:

Показать код 
import React, { useEffect, useState } from 'react'

import { Card } from '../Сard'
import { Loader } from '../Loader'
import { machine } from '../../questionnaireMachine'

import './style.css'

export const Questionnaire = () => {
  const [uiState, setUiState] = useState(machine.state)

  useEffect(() => {
    machine.subscribe((state) => setUISstate(state))
  }, [])

  return (
    <div className="questionnaire">
      <Card
        active={uiState === 'initial'}
        next={{ action: () => machine.send('start'), content: 'Start' }}
        subtitle="Thank you for taking part in our survey"
        title="Survey"
      />

      <Card
        active={uiState === 'personal'}
        next={{ action: () => machine.send('next'), content: 'Next' }}
        subtitle="Tell us about you!"
        title="Personal"
      >
        <div className="input-group">
          <label htmlFor="name" className="label">
            Name
          </label>
          <input type="text" placeholder="Floppa" id="name" className="input" />
        </div>
      </Card>

      <Card
        active={uiState === 'occupation'}
        prev={{ action: () => machine.send('back'), content: 'Back' }}
        subtitle="Do you work or study?"
        title="Occupation"
      >
        <div className="input-group">
          <label htmlFor="occupationStudent" className="label-radio">
            <input
              type="radio"
              name="occupation"
              id="occupationStudent"
              className="input-radio"
              onChange={() => machine.send('education')}
            />
            <span className="label-radio__toggler"></span>
            <span className="label-radio__content">Student</span>
          </label>
        </div>
        <div className="input-group">
          <label htmlFor="occupationWorker" className="label-radio">
            <input
              type="radio"
              name="occupation"
              id="occupationWorker"
              className="input-radio"
              onChange={() => machine.send('work')}
            />
            <span className="label-radio__toggler"></span>
            <span className="label-radio__content">Worker</span>
          </label>
        </div>
      </Card>

      <Card
        active={uiState === 'work'}
        next={{
          action: () => {
            machine.send('send')
            setTimeout(() => machine.send('success'), 1500)
          },
          content: 'Send survey'
        }}
        prev={{ action: () => machine.send('back'), content: 'Back' }}
        subtitle="Wow! What's your job?"
        title="Work"
      >
        <div className="input-group">
          <label htmlFor="job" className="label">
            Job
          </label>
          <input type="text" placeholder="Caracal" id="job" className="input" />
        </div>
      </Card>

      <Card
        active={uiState === 'education'}
        next={{
          action: () => {
            machine.send('send')
            setTimeout(() => machine.send('success'), 1500)
          },
          content: 'Send survey'
        }}
        prev={{ action: () => machine.send('back'), content: 'Back' }}
        subtitle="That's great! What's your future profession?"
        title="Education"
      >
        <div className="input-group">
          <label htmlFor="profession" className="label">
            Profession
          </label>
          <input
            type="text"
            placeholder="Meme"
            id="profession"
            className="input"
          />
        </div>
      </Card>

      {uiState === 'loading' && <Loader />}

      <Card
        active={uiState === 'success'}
        prev={{
          action: () => machine.send('reset'),
          content: 'Take another survey'
        }}
        subtitle="Thank you for your response! Want another survey?"
        title="We got it!"
      />
    </div>
  )
}

.questionnaire {
  position: fixed;
  top: 50%;
  left: 50%;
  width: 30em;
  height: 30em;
  transform: translate(-50%, -50%);
}

Первое: нам нужно подписаться на изменения состояния конечного автомата. Каждый раз, когда состояние меняется, мы обновляем uiState. Это нужно для вычисления свойства active компонента карточки — именно оно позволяет экземпляру компонента карточки решать, показывать себя или нет.

Теперь займёмся компонентом карточки:

import React from 'react'
import { CSSTransition } from 'react-transition-group'

import './style.css'

export const Card = ({ active, children, next, prev, subtitle, title }) => {
  return (
    <CSSTransition in={active} timeout={300} classNames="swipe" unmountOnExit>
      <div className="card">
        <header className="card__header">
          <h2 className="card__title">{title}</h2>
          <p className="card__subtitle">{subtitle}</p>
        </header>
        <div className="card__main">{children}</div>
        <div className="card__actions">
          {prev && (
            <button
              className="card__action card__action_prev"
              onClick={prev.action}
            >
              {prev.content}
            </button>
          )}
          {next && (
            <button
              className="card__action card__action_next"
              onClick={next.action}
            >
              {next.content}
            </button>
          )}
        </div>
      </div>
    </CSSTransition>
  )
}

Показать код 
.card {
  position: absolute;
  display: flex;
  flex-direction: column;
  width: 100%;
  height: 100%;
  padding: 3em 2em 2em;
  border-radius: 1.5em;
  background-color: #fff;
}

.card__header {
  margin-bottom: 2em;
  padding-bottom: 1em;
  border-bottom: 1px solid #f5f5f5;
}

.card__title {
  margin: 0 0 1em;
}

.card__subtitle {
  margin: 0;
}

.card__main {
  flex-grow: 1;
}

.card__action {
  padding: 1em 1.5em;
  border-radius: 1.5em;
  border: 0;
  color: #fff;
  font-size: 1em;
  cursor: pointer;
  transition: background-color 0.3s ease, box-shadow 0.3s ease;
}

.card__action_next {
  background-color: #4a90e2;
}

.card__action_prev {
  background-color: #bbb;
}

.card__action:not(:last-child) {
  margin-right: 1em;
}

.card__action:hover {
  box-shadow: 0 0 0.5em 0 #00000042;
}

.card__action_prev:hover {
  background-color: #4a90e2;
}

.swipe-enter {
  z-index: 1;
  transform: translateY(10vh) scale(0.9);
}

.swipe-enter-active {
  transform: translateY(0) scale(1);
  transition: transform 0.3s;
}

.swipe-exit {
  z-index: 10;
}

.swipe-exit-active {
  transform: translateY(100vh);
  transition: transform 0.3s;
}

Кнопки в нижней части компонента используют указанные действия как listener для события клика. Вот почему мы здесь передаём функции, изменяющие состояние FSM: так компонент анкеты сможет обновить uiState и отобразить нужную карточку.

Последняя мелочь — компонент прелоадера. Здесь нет ничего интересного, просто анимированная точка:

import React from 'react'

import './style.css'

export const Loader = () => {
  return (
    <div className="loader">
      <span className="loader__element animate__animated animate__bounce animate__infinite"></span>
    </div>
  )
}

.loader {
  position: fixed;
  z-index: 1;
  top: 50%;
  left: 50%;
  transform: translate(-50%, -50%);
}

.loader__element {
  display: block;
  width: 1em;
  height: 1em;
  border-radius: 50%;
  background: #fff;
}

Наконец, добавляем анкету в компонент приложения. Корневой компонент со стилями:

import { Questionnaire } from './components/Questionnaire'
import 'animate.css'
import './styles.css'

export default function App() {
  return <Questionnaire />
}

@import url('https://fonts.googleapis.com/css2?family=Open+Sans:wght@400;700&display=swap');

* {
  font-family: 'Open Sans', sans-serif;
  box-sizing: border-box;
}

body {
  margin: 0;
  background: #4a90e2;
}

.input-group:not(:last-child) {
  margin-bottom: 1em;
}

.label {
  display: block;
  margin-bottom: 0.75em;
  padding-left: 1.25em;
  font-size: 0.875em;
}

.input {
  width: 100%;
  padding: 1em;
  border-radius: 1.5em;
  border: 0.125em solid transparent;
  outline: 0;
  background-color: #f0f4fd;
  font-size: 1em;
}

.input::placeholder {
  color: #d8d8d8;
  opacity: 1;
}

.input:focus {
  border-color: #4a90e2;
}

.input-radio {
  display: none;
}

.label-radio {
  display: inline-flex;
  align-items: center;
  cursor: pointer;
}

.label-radio__toggler {
  width: 1em;
  height: 1em;
  margin-right: 0.5em;
  border-radius: 50%;
  border: 0.125em solid #bbb;
  transition: border-color 0.3s ease;
}

.label-radio:hover .label-radio__toggler {
  border-color: #4a90e2;
}

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

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

И ещё кое-что. Несмотря на то, что написать собственный FSM с нуля — очень полезный опыт, для рабочих задач я рекомендую использовать готовые библиотеки, например XState. Там есть и подробная документация, и все необходимые инструменты для работы (их, возможно, даже больше, чем нужно).

Заключение


Вот и всё! Мы поговорили о том, что такое конечные автоматы и где их можно использовать. Попробовали написать автомат с нуля и решили с его помощью две задачи. FSM — штука, полезная в разных областях, отличный подход к решению многих проблем и техника, которую обязательно стоит изучить и взять на вооружение. Надеюсь, статья была для вас полезной. Буду рад, если вы поделитесь мнением и опытом в комментариях.