Древоходной автомат

( Древовидный автомат TWA) — это тип конечного автомата , который работает с древовидными структурами , а не со строками. Концепция была первоначально предложена Ахо и Ульманом . ^[1]

Следующая статья посвящена древовидным автоматам. Другое понятие древесного автомата, тесно связанное с обычными древовидными языками , см. в разделе «Автомат ветвления» .

Определение

Предполагается, что все деревья являются двоичными с метками из фиксированного алфавита Σ.

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

Более формально, (недетерминированный) обходящийся по дереву автомат над алфавитом Σ представляет собой кортеж А знак равно ( Q , Σ, я , F , р , δ) где Q — конечное множество состояний, его подмножества I , F и R — множества начальных, принимающих и отвергающих состояний соответственно, а δ ⊆ ( Q × { root , left , right , Leaf } × Σ × { up , left , right } × Q) — отношение перехода.

Пример

Простым примером автомата обхода по дереву является TWA, который выполняет поиск в глубину (DFS) во входном дереве. Автомат $A$ имеет три состояния, $Q=\{q_{0},q_{\mathit {left}},q_{\mathit {right}}\}$ . $A$ начинается в корне в состоянии $q_{0}$ и спускается в левое поддерево. Затем он рекурсивно обрабатывает дерево. В любое время $A$ входит в узел $v$ в штате $q_{\mathit {left}}$ , это означает, что левое поддерево $v$ только что обработан, поэтому он переходит к правому поддереву $v$ . Если $A$ входит в узел $v$ в штате $q_{\mathit {right}}$ , это означает, что все поддерево с корнем $v$ было обработано и $A$ идет к родителю $v$ и меняет свое состояние на $q_{\mathit {left}}$ или $q_{\mathit {right}}$ , в зависимости от того, $v$ левый или правый ребенок.

Характеристики

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

Как показали Боянчик и Колкомбет , ^[2] детерминированные TWA строго слабее недетерминированных ( ${\mathit {DTWA}}\subsetneq {\mathit {TWA}}$ )
Детерминированные TWA закрыты при дополнении (но неизвестно, справедливо ли то же самое для недетерминированных ^[3])
Набор языков, распознаваемых TWA, строго содержится в обычных древовидных языках ( ${\mathit {TWA}}\subsetneq {\mathit {REG}}$ ), т.е. существуют регулярные языки, которые не распознаются ни одним древовидным автоматом, см. Боянчик и Колкомбет. ^[4]

См. также

Автоматы-камешки , расширение ходящих по деревьям автоматов.

Ссылки

^ Ахо, А; Ульман, Дж (1971). «Переводы на контекстно-свободную грамматику» . Информация и контроль . 19 (5): 439–475. дои : 10.1016/S0019-9958(71)90706-6 .
^ Боянчик, Миколай; Колкомбет, Томас (2006). «Древоходные автоматы не могут быть определены» (PDF) . Теоретическая информатика . 350 (2–3): 164–173. дои : 10.1016/j.tcs.2005.10.031 .
^ Боянчик, Миколай (2008). Мартин-Виде, Карлос; Отто, Фридрих; Фернау, Хеннинг (ред.). «Деревоходящие автоматы» (PDF) . Теория и приложения языка и автоматов . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer: 1–2. дои : 10.1007/978-3-540-88282-4_1 . ISBN 978-3-540-88282-4 .
^ Боянчик, Миколай; Колкомбет, Томас (2008). «Древоходные автоматы не распознают все обычные языки» (PDF) . СИАМ Дж. Компьютер. 38 (2): 658–701. дои : 10.1137/050645427 .

Внешние ссылки

Миколай Боянчик: Древоходящие автоматы . Краткий опрос.

[1] Ахо, А; Ульман, Дж (1971). «Переводы на контекстно-свободную грамматику» . Информация и контроль . 19 (5): 439–475. дои : 10.1016/S0019-9958(71)90706-6 .

[2] Боянчик, Миколай; Колкомбет, Томас (2006). «Древоходные автоматы не могут быть определены» (PDF) . Теоретическая информатика . 350 (2–3): 164–173. дои : 10.1016/j.tcs.2005.10.031 .

[3] Боянчик, Миколай (2008). Мартин-Виде, Карлос; Отто, Фридрих; Фернау, Хеннинг (ред.). «Деревоходящие автоматы» (PDF) . Теория и приложения языка и автоматов . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer: 1–2. дои : 10.1007/978-3-540-88282-4_1 . ISBN 978-3-540-88282-4 .

[4] Боянчик, Миколай; Колкомбет, Томас (2008). «Древоходные автоматы не распознают все обычные языки» (PDF) . СИАМ Дж. Компьютер. 38 (2): 658–701. дои : 10.1137/050645427 .

[1]

[2]

[3]

[4]