Конечный автомат (FSM – finite state machine)

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

Общее описание

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

Конечный автомат подразделяется на детерминированный и недетерминированный.

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

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

Применимость

Возможности применения конечного автомата обширны.

Простой пример – определить все ли главы в данной статье описаны в заданном порядке. Главы будут выступать состояниями, начиная с общего описания и заканчивая выводами. Если это представить графически, то это будет простой линейный граф.

Другой пример – обработать поток данных. Определяем состояния, переходы между ними, прогоняем поток данных и вот, на выходе связанные последовательности данных.

Способы задания функционирования

Широко известны два способа функционирования конечного автомата:

• Диаграмма состояний или граф переходов

• Таблица переходов

Диаграмма состояний или граф переходов – графическое представление множества состояний и переходов. Представляет собой размеченный ориентированный граф, вершины которого являются состояниями, а дуги являются переходами из одного состояния в другое.

Пример:

Таблица переходов — табличное представление состояний и переходов. Как правило, в такой таблице для каждой строки соответствует одно состояние, а для каждого столбца соответствует один допустимый входной сигнал. В ячейке на пересечении строки и столбца записывается состояние результата.

Исходное состояние	Входной сигнал a	Входной сигнал b	Входной сигнал c	Входной сигнал d
S1	S2	S1	S1	S1
S2	S2	S3	S2	S2
S3	S3	S3	S4	S3
S4	S4	S4	S4	S5

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

Реализация

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

Надеюсь, что я придумал такую задачу.

Дан поток данных в виде символов.

Пример входных данных:

}%1VMF19C.:$A--+G-SWL5#>9XJ>TYNCU(EO'-5,2K~}?<2<3K\QX,!5FT.AX21IX^MYA9)I=+&LL{LO34K|DD~H|B2)KPLI5
\VFQOI-NLXK]*XYM[U&MMYS2U?S_2(3L%"J{)AEGGLK&V4GNMS_]U|;K<F_@B~J'Y"!YYB<YK?:8IW)}32JR<DXG)JAW~`'EI
L8S1\4%V'&/)TVCLL=;VY2_W>SVL&S5TOC;J*`>#7C/')!B&IS+HX|ZRG}V~T_W4FJ<33E8CTGOUV9Z?DEHJ'@D+>E!3RO2J^
MJ}?L{}IG~_IKWF>HHBZGKWVQUNJJ'QNNG*&N5GM;|S>X7CFZ!U1CZJMFYKPCF.CL6VLG+H1IW|ZYPBNN"AFSJJT,JV,IOSFE
K!}$25FAZCL\9?EJNKO>OW;YNSJUKMP+,SQ$OP#/Q%H4JIQ>K7<R@GUB-@GAK!42#1B6V*MOZV#Z<{YDI'AT<ZJ0LXTF{SM,\
{DW{\9]L{8@>|U/9P4/I6}[U43K\|T'_{W}^PND,/;CVFNK3+}6%5/PSC'A)X,PRN;A?M(2:TO'%6SEM}D6}1SWTOD]X\6QG8
DLZT,+N,XVGOG[BWOKJ^:UR,;IQCBH$RYQ.;TZ,IM!4GWYO8A&~R#2D<FFQ('XW^|G0;WC]#L3JUH,~C~&MYOOT$$~%V{X4VT
=&II`|GHXW$S'W$O(V&#-KOO9IS<RXQ}^PJEAS|I=Y0C$KQO9T[(2.`[G\(7CU{L.OJ[4$(-!S*S~7IF$B>UJ=S.DY30+)(]J
R/1!RZD[B1KS?X[FXTUF4Z<=Z#-X1BVC\{R6~].Z<K>^CKAGNVX*K[=.C?)WD+9W!WF|PF)I=Y`Y<RHZCR%2CROL-OGDV>X/S
OQU^O[R/P,=D-:N:O@|3RD._VJPC,[_E3`3.HL,NODKC}YS&&RNG"BBO[}LP}`CX:R`W%#BLGIG>J9^W8?.)NN/3C=)C'QK6K
MR(I~EBL/1L:J'?^.&OFNM(Z{"28FESG?V-\DRC$K6OK~A;X$SL8SV=E+O6$_VR;_$JZUPK`I&9Z3LVH~!!NW^H}'GFF(2(YS
DB`Y5D[`I2+_$LK*PPCAMLJP.V`AZGK9`~~CP8P!SQNOD#F~VX+[T.)@V`ZZYTNFVJVAJ{3AL[`!NJJ)Q=82%2SC)U3|ZPM^3
L?M_MY+D(OB<`HN,C7;EE^"2O7AFE+(WDO?!'UP+@QZ3#6G}C*0SS=C'C3HO+MTDU~`?4KU:DPBNF):F#;ZND1]3O1V8;KRZT
OOMB^TA-EZ1DF.G`E`O,JI?{WE>D.WWGR4H}9URG+L@SAL;<NT:{?JPN38PD+M\T_55`+;.FO"'ANKNU\BHYI?S-OBMLX<5%H
D62"J2:EQI?8_#:"Q$'CS8HP3-Y8GTO\E.Z[H*V=W%.!15L\(M|=SR;;91}PI_1D5%D<,/;GKQFE?AST;<D/JA7NF\`4UN=_U
+.X\}[Z,U"RZ&O1|7E7CQT?*AINZUBUGHQL%S:1P`]<DNY!5QKXQY=$S?'AZ%NUH>:^J#{EBPEIJ(7L%#^"WKRMGQ\A%$-BCZ
Q>V,\~PTRGMT9E,J,OXPSYG{_]\D<^L<VB4UOT*M7BL@H>;EZTEAQ*HX7K)YGCVQZ&'~L)Z7I*|*IQD"YJJDL]8AFUTAMO+",
J=;OAPAHD4W$VF^?LZ]EXRDZ\NSV@U|XR\2HQ_RRQKIUH91DWYI!;LG2U53`M\65DHO9:;{"]ZGQ+9_;I'F$ZWEQ<@ARO*VR*
GYTZ'I_5\2;QJF#*+^$SGH{2RO;DA#{F~:U#VW,{V!I]V$AEIG[IE[\*$+MY#D5X\B(E~"M|Q%91%LG&}{H)3Q],#{J/HV<:X
NGD(NF+OFW-MLCE(00I=Q)!B:CO(B$IJ:KU?PBQ9MZJ,7Z6CJ=/SYC>S8<9E.7Y#W6~]]VZ}|?(8X3D;*O+KP9L<;X!%3KHGX
.+0)SB~I8KSIJ@WT`G[XGP-3/-VB@C9%V{6UEAR9I@OIU5.:}F{K$H"8GHR>+'C&WB)UTR&6BE#(13}A+K5C?:NCQ8I4=C0N9
(^+''TU8H_,QE$<RZC]D3@XF[(XJCU/N@8CU&J%P@,~X8N;`0[{D^IKF8CS05ETLD)CT:1$,3FEZ:K}T<CO>,/L?II(H}GR>J
P8"WY(B%$5!`^4MU<NGRSS8|/$=PBH9K|XD5JN_YJ7PW6MWABELJ=KK>G|L"KYMUAX-(P*JA"N67EH:X&F"/<2W[RD_2_}6TP

Требуется выявлять из этого потока последовательности FINITESTATEMACHINE, пропуская неподходящие символы.

Приступим к реализации.

Базовая реализация конечного автомата будет следующая:

Показать код

trait Fsm {
  private type Transition = State => State
  private type StateFunction = PartialFunction[Event, Transition]

  private val stateFunctions = mutable.Map[Status, StateFunction]()

  def process(currentState: State, event: Event): State = {
    val stateFunction = stateFunctions(currentState.status)
    val nextState = if (stateFunction.isDefinedAt(event)) {
      stateFunction(event)(currentState)
    } else {
      stay()(currentState).withStopReason(FsmException(s"Unhandled event $event in state $currentState"))
    }
    nextState.stopReason.foreach(throw _)
    applyState(nextState, currentState)
  }

  protected final def when(statuses: Status*)(stateFunction: StateFunction): Unit = {
    statuses.foreach(register(_, stateFunction))
  }

  protected final def start(status: Status): State = State(status)

  protected final def stay(): Transition = currentState => currentState

  protected final def goto(nextStatus: Status): Transition = _ => State(nextStatus)

  protected final def stop(reason: FsmException): Transition = {
    currentState => stay()(currentState).withStopReason(reason)
  }

  private final def register(status: Status, function: StateFunction): Unit = {
    stateFunctions(status) = stateFunctions.getOrElse(status, function)
  }

  private def applyState(nextState: State, currentState: State): State = {
    val state = if (stateFunctions.contains(nextState.status)) {
      nextState
    } else {
      stay()(currentState).withStopReason(FsmException(s"Next state ${nextState.status} does not exist"))
    }
    state.stopReason.foreach(throw _)
    state
  }
}

object Fsm {
  trait Status {
    def is(pf: PartialFunction[Status, Boolean]): Boolean = Status.is(this)(pf)
  }

  object Status {
    def is(status: Status)(pf: PartialFunction[Status, Boolean]): Boolean = pf.lift(status).fold(false)(identity)
  }

  class Event

  case class State(status: Status, stopReason: Option[FsmException] = None) {
    def !(event: Event)(implicit fsm: Fsm): State = fsm.process(this, event)

    private[core] def withStopReason(reason: FsmException): State = copy(stopReason = Some(reason))
  }

  case class FsmException(message: String) extends RuntimeException(message)
}

Опишем нашу искомую последовательность в виде двух моделей.

Первая модель будет работать с символами и собирать из них слова. Вторая модель будет работать со словами и собирать из них предложения.

Описание первой модели:

Модель будет начинаться с состояния Start и заканчиваться состоянием Stop. Между этими состояниями будут состояния для каждого символа. Для удобства опишем весь английский алфавит. Событиями переходов между состояниями будут символы искомых слов. Также добавим событие Unknown для всех остальных неизвестных и неопределенных событий.

Реализация первой модели будет следующая:

Показать код

object Letters {
  object Statuses {
    case object Start extends Status
    case object Stop extends Status

    case object A extends Status
    case object B extends Status
    case object C extends Status
    case object D extends Status
    case object E extends Status
    case object F extends Status
    case object G extends Status
    case object H extends Status
    case object I extends Status
    case object J extends Status
    case object K extends Status
    case object L extends Status
    case object M extends Status
    case object N extends Status
    case object O extends Status
    case object P extends Status
    case object Q extends Status
    case object R extends Status
    case object S extends Status
    case object T extends Status
    case object U extends Status
    case object V extends Status
    case object W extends Status
    case object X extends Status
    case object Y extends Status
    case object Z extends Status
  }

  object Events {
    case object Unknown extends Event

    case object A extends Event
    case object B extends Event
    case object C extends Event
    case object D extends Event
    case object E extends Event
    case object F extends Event
    case object G extends Event
    case object H extends Event
    case object I extends Event
    case object J extends Event
    case object K extends Event
    case object L extends Event
    case object M extends Event
    case object N extends Event
    case object O extends Event
    case object P extends Event
    case object Q extends Event
    case object R extends Event
    case object S extends Event
    case object T extends Event
    case object U extends Event
    case object V extends Event
    case object W extends Event
    case object X extends Event
    case object Y extends Event
    case object Z extends Event
  }

  object LettersFsm extends Fsm {
    val start: State = start(Statuses.Start)

    when(Statuses.Start) {
      case Events.F => goto(Statuses.F)
      case Events.S => goto(Statuses.S)
      case Events.M => goto(Statuses.M)
      case _ => stay()
    }

    when(Statuses.F) {
      case Events.I => goto(Statuses.I)
      case _ => stay()
    }

    when(Statuses.I) {
      case Events.N => goto(Statuses.N)
      case Events.T => goto(Statuses.T)
      case _ => stay()
    }

    when(Statuses.N) {
      case Events.I => goto(Statuses.I)
      case Events.E => goto(Statuses.E)
      case _ => stay()
    }

    when(Statuses.I) {
      case Events.N => goto(Statuses.N)
      case _ => stay()
    }

    when(Statuses.T) {
      case Events.E => goto(Statuses.E)
      case Events.A => goto(Statuses.A)
      case _ => stay()
    }

    when(Statuses.S) {
      case Events.T => goto(Statuses.T)
      case _ => stay()
    }

    when(Statuses.A) {
      case Events.T => goto(Statuses.T)
      case Events.C => goto(Statuses.C)
      case _ => stay()
    }

    when(Statuses.C) {
      case Events.H => goto(Statuses.H)
      case _ => stay()
    }

    when(Statuses.M) {
      case Events.A => goto(Statuses.A)
      case _ => stay()
    }

    when(Statuses.H) {
      case Events.I => goto(Statuses.I)
      case _ => stay()
    }

    when(Statuses.E) {
      case _ => goto(Statuses.Stop)
    }

    when(Statuses.Stop) {
      case event => (current: State) => stop(FsmException(s"Event: $event received in finite status: ${current.status}"))(current)
    }
  }

  implicit val fsm: LettersFsm.type = LettersFsm
  val start: State = fsm.start
}

Графически это будет выглядеть следующим образом:

Так как эта модель собирает последовательности всех трех искомых слов, то выход будет с небольшим шумом.

Пример выходных данных после первой модели:

FINE
MACHINE
STE
STE
MACHITE
MACHITE
MATATATE
MACHINE
MATE
FITATACHITACHINITE
MACHINE
FITE
STE
STACHITE
FINE
MATE
STACHITE
MACHINITE
MATE
MACHITE
FITE
FITATE
MATACHITE
STE
FITATACHINITATE
STACHINE
MATE
FITATE
MACHINININE
MATATACHINININININE
MATE
FITACHITACHINE
STE
MACHITE
STATACHITATACHINITACHITATATACHINE
MACHITE
FINITE

Описание второй модели:

Модель будет начинаться с состояния Start и заканчиваться состоянием Stop. Между этими состояниями будут состояния, отражающие каждое искомое слово. Событиями переходов между состояниями будут искомые слова. Также добавим событие Unknown для всех остальных неизвестных и неопределенных слов.

Реализация второй модели будет следующая:

Показать код

object Words {
  object Statuses {
    case object Start extends Status
    case object Stop extends Status

    case object Finite extends Status
    case object State extends Status
    case object Machine extends Status
  }

  object Events {
    case object Unknown extends Event

    case object Finite extends Event
    case object State extends Event
    case object Machine extends Event
  }

  object WordsFsm extends Fsm {
    val start: State = start(Statuses.Start)

    when(Statuses.Start) {
      case Events.Finite => goto(Statuses.Finite)
      case _ => stay()
    }

    when(Statuses.Finite) {
      case Events.State => goto(Statuses.State)
      case _ => stay()
    }

    when(Statuses.State) {
      case Events.Machine => goto(Statuses.Machine)
      case _ => stay()
    }

    when(Statuses.Machine) {
      case _ => goto(Statuses.Stop)
    }

    when(Statuses.Stop) {
      case event => (current: State) => stop(FsmException(s"Event: $event received in finite status: ${current.status}"))(current)
    }
  }

  implicit val fsm: WordsFsm.type = WordsFsm
  val start: State = fsm.start
}

Графически это будет выглядеть следующим образом:

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

Пример выходных данных после второй модели:

FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE
FINITESTATEMACHINE

Как видим, выход после второй модели нам дает требуемый результат.

Для интересующихся посмотреть код проекта ссылка на github – https://github.com/dmitry-goncharov/fsmex

Выводы

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

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