Нить-автомат
В теории автоматов поток -автомат (множественное число: автоматы) представляет собой расширенный тип автоматов с конечным числом состояний , который распознает слегка контекстно-зависимый языковой класс, расположенный выше языков, примыкающих к дереву . [1]
Формальное определение [ править ]
Потоковый автомат состоит из
- набор N состояний, [примечание 1]
- набор Σ терминальных символов,
- начальное состояние A S ∈ N ,
- конечное состояние A F ∈ N ,
- набор U компонентов пути,
- частичная функция δ: N → U ⊥ , где ты ⊥ знак равно U ∪ {⊥} для ⊥ ∉ U ,
- конечное множество Θ переходов.
Путь u 1 ... un ∈ U * — строка компонентов пути u i ∈ U ; n может быть 0, а пустой путь обозначается ε. Нить вид u 1 ... un : , A где u 1 ... un ∈ имеет U * — путь, а A ∈ N — состояние. Хранилище потоков S — это конечное множество потоков, рассматриваемое как частичная функция из U * на N , такой, dom ( S ) замыкается префиксом что .
автомата потока Конфигурация представляет собой тройку ‹ 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 }› на ‹ l , p , S ∪{ p : D , pu : C }›, где δ( C )=⊥
Можно доказать, что δ( B )= u для переходов POP и SPOP и δ( C )=⊥ для SPUSH . переходов [2]
Входная строка принимается автоматом, если существует последовательность переходов, меняющих исходную конфигурацию на конечную.
Примечания [ править ]
- ^ названные нетерминальными символами , стр.1r Виллемонте (2002)
Ссылки [ править ]
- ^ Вильмонте де ла Клержери, Эрик (2002). «Разбор слабо контекстно-зависимых языков с помощью автоматов потоков» . COLING '02 Материалы 19-й Международной конференции по компьютерной лингвистике . 1 (3): 1–7. дои : 10.3115/1072228.1072256 . Проверено 15 октября 2016 г.
- ^ Виллемонте (2002), стр.1r-2r.