Поточный автомат

В теории автоматов потоковый автомат (множественное число: автоматы) является расширенный тип конечных автоматов, который распознает умеренно контекстно-зависимый языковой класс над смежными с деревом языками.

A потоковый автомат состоит из

• набора N состояний,
• набора Σ терминальных символов,
• начального состояния A S ∈ N,
• конечное состояние A F ∈ N,
• множество U компонентов пути,
• частичная функция δ: N → U, где U = U ∪ {⊥} для ⊥ ∉ U,
• конечное множество Θ переходов.

A путь u1... u n ∈ U - строка компонентов пути u i ∈ U; n может быть равно 0, а пустой путь обозначен ε. поток имеет вид u 1... u n : A, где u 1... u n ∈ U - путь, а A ∈ N - состояние. Хранилище потоков S - это конечный набор потоков, рассматриваемый как частичная функция от U до N, так что dom (S) закрыто на префикс.

A автомат потока конфигурация представляет собой тройку ‹l, p, S›, где l обозначает текущую позицию во входной строке, p - активный поток, а S - хранилище потоков, содержащее p. Первоначальная конфигурация - ‹0, ε, {ε: A S }›. Конечная конфигурация : ‹n, u, {ε: A S, u: A F }›, где n - длина входной строки, а u сокращает δ (A S). Переход в наборе Θ может иметь одну из следующих форм и изменяет текущую конфигурацию автомата следующим образом:

• SWAP B → a C: потребляет входной символ a и изменяет состояние активного потока:

изменяет конфигурацию с ‹l, p, S∪ {p: B}› на ‹l + 1, p, S∪ {p: C}›

• SWAP B → ε C: аналогично, но не требует ввода:

меняет ‹l, p, S∪ {p: B}› на ‹l, p, S∪ {p: C} ›

• PUSH C: создает новый подпоток и приостанавливает его родительский поток:

изменяет‹ l, p, S∪ {p: B} ›на‹ l, pu, S ∪ {p: B, pu: C} ›где u = δ (B) и pu∉dom (S)

• POP [B] C: завершает активный поток, возвращая управление его родителю:

заменяет ‹l, pu, S∪ {p: B, pu: C}› на ‹l, p, S∪ {p: C}›, где δ (C) = ⊥ и pu∉dom (S)

• SPUSH [C] D: возобновляет приостановленный подпоток активного потока:

изменяет ‹l, p, S∪ {p: B, pu: C}› на ‹l, pu, S∪ {p: B, pu: D} ›где u = δ (B)

• SPOP [B] D: возобновляет родительский элемент активного потока:

изменяет‹ l, pu, S∪ {p: B, pu: C} ›to‹ l, p, S∪ {p: D, pu: C} ›где δ (C) = ⊥

Можно доказать, что δ (B) = u для PO P и SPOP переходы, и δ (C) = ⊥ для SPUSHпереходов.

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