Автомат на батарейках

Сложность
Средний 50%

Автомат на батарейках

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

Выталкивающий автомат — это пятерка A = (T, P, Q, M, S0), такая что:

  • T — терминальный словарь,
  • P - словарь стека (содержащий, в частности, начальный символ пустого стека, обозначаемый ⊥),
  • Q — конечное множество состояний,
  • M — множество переходов,
  • S0 ∈ Q — начальное состояние.

Словарь стека содержит все символы, которые могут появиться в стеке, и не обязательно отличается от терминального словаря (мы можем иметь T ∩ P ≠ ∅).

Переход от автомата к стеку аналогичен переходу конечного автомата, за исключением того, что он дополнительно определяет манипулирование стеком. Переход M имеет вид
(состояние, symbol_read, top_stack) → (new_state, action_on_stack), например:

  • state и new_state — это состояния Q,
  • symbol_lu является либо терминальным символом T, либо , что означает, что автомат не смотрит на слово,
  • top_stack является либо символом P, либо , что означает, что автомат не смотрит на вершину стека,
  • action_on_stack:
    "поместить символ на вершину стека", или
    «вставьте символ в верхнюю часть стека, затем сложите последовательность символов» или
    «сложить ряд символов», или
    "ничего не делать".

Работа автомата A = (T, P, Q, M, S0) определяется как
следующий :

  • Конфигурация автомата характеризуется тройкой: (S, m, p), где S ∈ Q, m ∈ T* и p ∈ P* то есть текущее состояние S, последовательность m терминальных символов (соответствующая концу анализируемого слова) и последовательность p символов стека (соответствующая текущему состоянию стека).

Конфигурация (S0, m0, p0) выводится за один шаг из конфигурации (S, m, p)
(обозначается (S, m, p) ⇒ (S0, m0, p0)) если: (S, u, v) → (S0, action_sur_pile) является переходом M, m = u.m0 (слово m должно быть анализируемый начинается с символа u), символ наверху стека p — это v. p0 — это стек, полученный после выполнения действия action_on_stack над стеком p.

Слово w принимается автоматом выталкивания A, если (S0, w, ⊥) ⇒ (S, ε, ⊥), где ⊥ — пустой символ выталкивания. Язык L(A), принимаемый выталкивающим автоматом A, представляет собой множество слов, принимаемых A.

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

Стековые автоматы, которые мы определили, принимают слово, когда есть производное, ведущее к конфигурации, в которой стек пуст, а слово полностью прочитано. По этой причине они называются автоматами выталкивания, принимающими пустой стек. Другое определение автоматов выталкивания - это автоматы выталкивания, принимающие конечное состояние. Такой автомат дополнительно задает множество конечных состояний F ⊆ Q. Слово принимается, если есть производное, ведущее к конфигурации, в которой состояние является окончательным (стек не обязательно должен быть пустым).

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

Существуют контекстно-свободные языки, которые не принимает ни один детерминированный автомат выталкивания вниз. Таким образом, языки, принимаемые детерминированными стековыми автоматами, образуют подкласс контекстно-свободных языков: класс детерминированных контекстно-свободных языков.

Пример

Вот пример недетерминированного выталкивающего автомата. Рассмотрим выталкивающий автомат, распознающий язык слов, образованных на {a, b} и содержащий одинаковое количество слов a и b: A = (T, P, Q, M, q), такой что: T = {a, b}, P = {a, b}, Q = {q} и следующую матрицу перехода M

Автомат на батарейках

Операция этого автомата над словом w = aabbabba такова:

Автомат на батарейках

Что касается конечных автоматов, мы можем дать автоматам с выталкиванием вниз представление график. Дуги имеют следующую информацию:

  • символ прочитан, символ выскочил; сложенный символ.

Например, дуга а, А; ε будет читать символ a при условии, что он может извлечь символ A из вершины стека. Обратите внимание, что ε или λ означает «ничего не делать».

Делиться
ru_RURU