Введение

иное представление о дереве автомата

Дерево автомат – это тип конечного автомата. Деревья автоматы работают с древовидными структурами, а не со строками, как более традиционные конечные автоматы. В данной статье рассматриваются разветвленные деревья автоматы, которые соответствуют регулярным языкам деревьев. Как и в случае с классическими автоматами, конечные деревья автоматы (FTA) могут быть детерминированными или недетерминированными. В зависимости от способа обработки входного дерева, конечные деревья автоматы могут быть двух типов: (а) снизу вверх, (б) сверху вниз. Это важный вопрос, поскольку, хотя недетерминированные (ND) автоматы сверху вниз и снизу вверх эквивалентны по выразительной силе, детерминированные автоматы сверху вниз строго менее мощны, чем их детерминированные аналоги снизу вверх, поскольку свойства дерева, определяемые детерминированными автоматами сверху вниз, могут зависеть только от свойств путей. (Детерминированные автоматы снизу вверх обладают такой же выразительной силой, как и недетерминированные деревья автоматы.)

Признаваемость

Для автомата, работающего снизу вверх, основной терм t (то есть дерево) принимается, если существует редукция, начинающаяся с t и заканчивающаяся q(t), где q – конечное состояние. Для автомата, работающего сверху вниз, основной терм t принимается, если существует редукция, начинающаяся с q(t) и заканчивающаяся t, где q – начальное состояние. Древесный язык L(A), принимаемый или распознаваемый автоматом на деревьях A, является множеством всех основных термов, принимаемых A. Множество основных термов является распознаваемым, если существует автомат на деревьях, который его принимает. Линейный (то есть сохраняющий аритет) древесный гомоморфизм сохраняет распознаваемость.

Полная информация и сокращение

Недетерминированный конечный деревоавтомат считается полным, если для каждой возможной комбинации символов и состояний существует хотя бы одно правило перехода. Состояние q является достижимым, если существует основной терм t, для которого существует редукция из t в q(t). НКДА считается приведенным, если все его состояния достижимы.

Лемма насоса

Каждый достаточно большой основной терм t в распознаваемом языке деревьев L может быть вертикально трипартирован таким образом, что произвольное повторение ("накачивание") средней части сохраняет полученный терм в L. Для языка всех конечных списков булевых значений из вышеприведенного примера, все термы высотой больше k=2 могут быть накачаны, поскольку они должны содержать вхождение, например, (, (,) ) , (,(,)) , (,(,(,))) , (,(,(,(,)))) , все принадлежат этому языку.

Закрытие

Класс распознаваемых языков деревьев замкнут относительно объединения, дополнения и пересечения.