Дерево-автомат
Древовидный автомат — это тип конечного автомата . Древовидные автоматы имеют дело с древовидными структурами , а не со строками более традиционных конечных автоматов.
В следующей статье рассматриваются автоматы ветвящегося дерева, которые соответствуют регулярным языкам деревьев .
Как и в случае с классическими автоматами, автоматы с конечным деревом (FTA) могут быть как детерминированными , так и нет. В зависимости от того, как автомат обрабатывает входное дерево, автоматы конечного дерева могут быть двух типов: (а) снизу вверх, (б) сверху вниз. Это важный вопрос, поскольку, хотя недетерминированные (НД) нисходящие и НД восходящие автоматы деревьев эквивалентны по выразительной силе, детерминированные нисходящие автоматы строго менее эффективны, чем их детерминированные восходящие аналоги, потому что свойства дерева заданные детерминированными автоматами дерева сверху вниз, могут зависеть только от свойств пути. (Детерминированные автоматы восходящего дерева столь же эффективны, как автоматы дерева ND.)
Восходящий конечный древовидный автомат над F определяется как кортеж ( Q , F , Qf , ∆), где Q — множество состояний, F — ранжированный алфавит (т. е . алфавит, символы которого имеют ассоциированную арность ) . , Q f ⊆ Q — множество конечных состояний, а ∆ — множество правил перехода вида f ( q 1 ( x 1 ),..., q n ( x n )) → q (f ( x 1 ,..., x n )), для n -арных переменных f ∈ F , q , q i ∈ Q и x i , обозначающих поддеревья. То есть члены Δ являются правилами перезаписи от узлов, чьи дочерние корни являются состояниями, к узлам, чьи корни являются состояниями. Таким образом, состояние узла выводится из состояний его потомков.
Для n = 0, то есть для постоянного символа f , приведенное выше определение правила перехода читается как f () → q ( f ()); часто для удобства опускаются пустые скобки: f → q ( f ). Поскольку эти правила перехода для постоянных символов (листьев) не требуют состояния, не требуются явно определенные начальные состояния. Восходящий древовидный автомат запускается на основном терме над F , начиная со всех его листьев одновременно и двигаясь вверх, связывая состояние выполнения из Q с каждым подтермом. Термин принимается, если его корень связан с принимающим состоянием из Qф . [1]
Автомат конечного дерева сверху вниз над F определяется как кортеж ( Q , F , Q i , ∆ ) с двумя отличиями от автоматов дерева снизу вверх. Во- первых, Q i ⊆ Q , множество его начальных состояний, заменяет Q f ; во-вторых, его правила перехода ориентированы обратно: q ( f ( x1 , ... , xn ) ) → f ( q1 ( x1 ) ,... , qn ( xn)), для n -арных f ∈ F , q , q i ∈ Q , и x i переменных, обозначающих поддеревья. То есть члены Δ здесь переписывают правила от узлов, чьи корни являются состояниями, к узлам, дочерними корнями которых являются состояния. Нисходящий автомат стартует в некоторых своих начальных состояниях от корня и движется вниз по ветвям дерева, индуктивно связывая по ходу состояние с каждым подтермом. Дерево считается принятым, если таким образом можно пройти через каждую ветку. [2]
