Дерево-автомат - Tree automaton
Дерево автомат представляет собой тип государственной машины . Древовидные автоматы имеют дело с древовидными структурами , а не со строками более обычных конечных автоматов.
Следующая статья посвящена автоматам ветвящихся деревьев, которые соответствуют регулярным языкам деревьев .
Как и классические автоматы, конечные древовидные автоматы (FTA) могут быть либо детерминированным автоматом, либо нет. В зависимости от того, как автомат обрабатывает входное дерево, конечные древовидные автоматы могут быть двух типов: (а) снизу вверх, (б) сверху вниз. Это важный вопрос, поскольку, хотя недетерминированные (ND) нисходящие и восходящие древовидные автоматы ND эквивалентны по выразительной мощности, детерминированные нисходящие автоматы строго менее мощны, чем их детерминированные восходящие аналоги, потому что свойства дерева определяемые детерминированными автоматами дерева сверху вниз, могут зависеть только от свойств пути. (Детерминированные восходящие древовидные автоматы так же мощны, как и ND-деревья.)
Определения
Снизу вверх конечное дерево автомат над F определяется как кортеж ( Q , F , Q F , А), где 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 f .
Сверху вниз конечное дерево автомат над F определяется как кортеж ( Q , F , Q я , А), с двумя различиями с снизу вверх дерева автоматов. Во-первых, Q i ⊆ Q , множество его начальных состояний, заменяет Q f ; во-вторых, его правила перехода ориентированы наоборот: q ( f ( x 1 , ..., x n )) → f ( q 1 ( x 1 ), ..., q n ( x n )), для n - произвольные f ∈ F , q , q i ∈ Q и переменные x i, обозначающие поддеревья. То есть члены Δ здесь представляют собой правила перезаписи из узлов, корни которых являются состояниями, в узлы, дочерние корни которых являются состояниями. Нисходящий автомат запускается в некоторых из своих начальных состояний в корне и движется вниз по ветвям дерева, индуктивно ассоциируя состояние с каждым подтермом. Дерево считается приемлемым, если через него можно пройти каждую ветвь.
Древовидный автомат называется детерминированным (сокращенно DFTA ), если никакие два правила из Δ не имеют одинаковой левой части; в противном случае это называется недетерминированным ( NFTA ). Недетерминированные нисходящие древовидные автоматы обладают той же выразительной способностью, что и недетерминированные восходящие автоматы; правила перехода просто меняются местами, и конечные состояния становятся начальными состояниями.
Напротив, детерминированные автоматы с нисходящим деревом менее мощны, чем их аналоги с восходящим принципом, потому что в детерминированном дереве-автомате нет двух правил перехода с одинаковой левой стороной. Для древовидных автоматов правила перехода - это правила перезаписи; а для нисходящих узлов левая сторона будет родительскими узлами. Следовательно, детерминированный нисходящий древовидный автомат сможет проверять только те свойства дерева, которые истинны во всех ветвях, потому что выбор состояния для записи в каждую дочернюю ветвь определяется в родительском узле, не зная содержимого дочерних ветвей. .
Примеры
Автомат снизу вверх, принимающий логические списки
Использование раскраски для различения членов F и Q и использование ранжированного алфавита F = { false , true , nil , cons (.,.)}, С cons, имеющей арность 2, и всеми другими символами, имеющими арность 0, восходящее дерево автомат, принимающий множество всех конечных списков логических значений, можно определить как ( Q , F , Q f , Δ) с Q = { Bool , BList } , Q f = { BList } и Δ, состоящим из правил
| ложный | → | Bool ( ложь ) | (1), |
| истинный | → | Бул ( правда ) | (2), |
| ноль | → | BList ( ноль ) | (3), и |
| минусы ( Bool (x 1 ), BList (x 2 )) | → | BList ( минусы (x 1 , x 2 )) | (4). |
В этом примере правила можно интуитивно понять как присвоение каждому термину его типа снизу вверх; например, правило (4) можно прочитать как «Термин cons ( x 1 , x 2 ) имеет тип BList , при условии, что x 1 и x 2 имеют типы Bool и BList , соответственно». Приемлемый пример запуска:
| минусы ( | ложь , | минусы ( | правда , | ноль | )) | ||
| ⇒ | минусы ( | ложь , | минусы ( | правда , | BList ( ноль ) | )) | по (3) |
| ⇒ | минусы ( | ложь , | минусы ( | Бул ( правда ), | BList ( ноль ) | )) | по (2) |
| ⇒ | минусы ( | ложь , | BList ( минусы ( | правда , | ноль | ))) | по (4) |
| ⇒ | минусы ( | Bool ( ложь ), | BList ( минусы ( | правда , | ноль | ))) | по (1) |
| ⇒ | BList ( минусы ( | ложь , | минусы ( | правда , | ноль | ))) | по (4), принято. |
Ср. вывод того же термина из грамматики регулярных деревьев, соответствующей автомату, показанный в разделе « Грамматика регулярных деревьев # Примеры» .
Отклоняющий пример запуска
| минусы ( | ложь , | истинный | ) | ||
| ⇒ | минусы ( | ложь , | Бул ( правда ) | ) | по (1) |
| ⇒ | минусы ( | Bool ( ложь ), | Бул ( правда ) | ) | согласно (2), никакие другие правила не применяются. |
Интуитивно это соответствует термину cons ( false , true ), который не соответствует типу.
Автомат сверху вниз, принимающий числа, кратные 3, в двоичной системе счисления
| (А) | (В) | (С) | (D) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Правила грамматики строк |
Строка автоматные переходы |
Дерево автомат переходы |
Правила грамматики дерева |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
Детерминированный конечный (строковый) автомат, принимающий числа, кратные 3, в двоичной системе счисления
|
Используя ту же раскраску, что и выше, этот пример показывает, как древовидные автоматы обобщают обычные строковые автоматы. Конечный детерминированный строковый автомат, показанный на рисунке, принимает все строки двоичных цифр, которые обозначают кратное 3. Используя понятия из Детерминированного конечного автомата # Формальное определение , он определяется следующим образом:
- множество Q состояний равно { S 0 , S 1 , S 2 },
- входной алфавит - { 0 , 1 },
- начальное состояние S 0 ,
- набор конечных состояний - { S 0 }, и
- переходы такие, как показано в столбце (B) таблицы.
В настройке древовидного автомата входной алфавит изменяется таким образом, что символы 0 и 1 являются унарными, а нулевой символ, скажем, nil , используется для листьев дерева. Например, двоичная строка « 110 » в настройке строкового автомата соответствует термину « 1 ( 1 ( 0 ( nil )))» в настройке древовидного автомата; таким образом строки могут быть обобщены на деревья или термины. Нисходящий конечный древовидный автомат, принимающий набор всех членов, соответствующих кратным 3 в двоичной строковой нотации, затем определяется следующим образом:
- множество Q состояний по-прежнему { S 0 , S 1 , S 2 },
- ранжированный входной алфавит равен { 0 , 1 , nil }, с Arity ( 0 ) = Arity ( 1 ) = 1 и Arity ( nil ) = 0, как объяснено,
- набор начальных состояний равен { S 0 }, и
- переходы такие, как показано в столбце (C) таблицы.
Например, дерево « 1 ( 1 ( 0 ( nil )))» принимается следующим запуском древовидного автомата:
| S 0 ( | 1 ( | 1 ( | 0 ( | ноль | )))) | |||||
| ⇒ | 1 ( | S 1 ( | 1 ( | 0 ( | ноль | )))) | на 2 | |||
| ⇒ | 1 ( | 1 ( | S 0 ( | 0 ( | ноль | )))) | по 4 | |||
| ⇒ | 1 ( | 1 ( | 0 ( | S 0 ( | ноль | )))) | на 1 | |||
| ⇒ | 1 ( | 1 ( | 0 ( | ноль | ))) | 0 |
Напротив, термин « 1 ( 0 ( nil ))» приводит к следующему не принимающему запуску автомата:
| ⇒ S 0 ( | 1 ( | 0 ( | ноль | ))) | |||
| ⇒ | 1 ( | S 1 ( | 0 ( | ноль | )))) | на 2 | |
| ⇒ | 1 ( | 0 ( | S 2 ( | ноль | )))) | на 3, дальнейшие правила не применяются |
Поскольку нет других начальных состояний, кроме S 0, с которыми можно начать работу автомата, термин « 1 ( 0 ( nil ))» не принимается древовидным автоматом.
В целях сравнения в столбцах (A) и (D) таблица дает (справа) регулярную (строковую) грамматику и грамматику регулярного дерева , соответственно, каждая из которых принимает тот же язык, что и ее автоматный аналог.
Характеристики
Узнаваемость
Для восходящего автомата основной член t (то есть дерево) принимается, если существует редукция, которая начинается с t и заканчивается q ( t ), где q - конечное состояние. Для нисходящего автомата основной член t принимается, если существует редукция, которая начинается с q ( t ) и заканчивается t , где q - начальное состояние.
Язык дерева L ( ) принято , или признаются , дерево автомата А есть множество всех наземных условий , принятых A . Набор основных терминов распознается, если существует древовидный автомат, который его принимает.
Линейный (т.е. сохраняющий арность) гомоморфизм деревьев сохраняет узнаваемость.
Полнота и редукция
Недетерминированный конечный древовидный автомат считается полным, если существует хотя бы одно правило перехода, доступное для каждой возможной комбинации состояний символа. Состояние д является доступным , если существует наземную термин т таким образом, что существует такое сокращение от т к д ( т ). NFTA сокращается, если все его состояния доступны.
Лемма о накачке
Каждый достаточно большие термы т в узнаваемом языке дерева L может быть вертикально tripartited таким образом, что произвольное повторение ( «накачка») от средней части сохраняет полученный член в L .
Для языка всех конечных списков логических значений из приведенного выше примера все члены, превышающие предел высоты k = 2, могут быть перекачаны, поскольку они должны содержать вхождение cons . Например,
| минусы ( ложь , | минусы ( правда , ноль ) | ) | , |
| минусы ( ложь , минусы ( ложь , | минусы ( правда , ноль ) | )) | , |
| минусы ( ложь , минусы ( ложь , минусы ( ложь , | минусы ( правда , ноль ) | ))) | , ... |
все принадлежат этому языку.
Закрытие
Класс распознаваемых древовидных языков замкнут относительно объединения, дополнения и пересечения.
Теорема Майхилла – Нероде
Конгруэнцией на множестве всех деревьев над ранжированным алфавитом F называется отношение эквивалентности, такое что u 1 ≡ v 1 и ... и u n ≡ v n влечет f ( u 1 , ..., u n ) ≡ f ( v 1 , ..., v п ) для любого х ∈ F . Он имеет конечный индекс, если число его классов эквивалентности конечно.
Для заданного дерева языка L , конгруэнтность может быть определена с помощью U ≡ L v , если С [ U ] ∈ L ⇔ C [ v ] ∈ L для каждого контекста C .
Теорема Майхилла – Нероде для древовидных автоматов утверждает, что следующие три утверждения эквивалентны:
- L - узнаваемый древовидный язык
- L - объединение некоторых классов эквивалентности конгруэнции конечного индекса
- отношение ≡ L является конгруэнцией конечного индекса
Смотрите также
- Теорема Курселя - применение древовидных автоматов для доказательства алгоритмической мета-теоремы о графах
- Преобразователи деревьев - расширяют древовидные автоматы таким же образом, как преобразователи слов расширяют словарные автоматы .
- Чередующиеся древовидные автоматы
- Бесконечные древовидные автоматы
Примечания
использованная литература
- Комон, Юбер; Дауше, Макс; Гиллерон, Реми; Жакемар, Флоран; Лужие, Денис; Лёдинг, Кристоф; Тисон, Софи; Томмази, Марк (ноябрь 2008 г.). Методы и приложения древовидных автоматов (PDF) . Проверено 11 февраля 2014 года .
- Хосоя, Харуо (4 ноября 2010 г.). Основы обработки XML: подход древовидных автоматов . Издательство Кембриджского университета. ISBN 978-1-139-49236-2.
внешние ссылки
Реализации
- Граппа - библиотеки ранговых и неранговых древовидных автоматов (OCaml)
- Timbuk - инструменты для анализа достижимости и расчетов древовидных автоматов (OCaml)
- LETHAL - библиотека для работы с конечными деревьями и хедж-автоматами (Java)
- Библиотека древовидных автоматов с машинной проверкой (Isabelle [OCaml, SML, Haskell])
- VATA - библиотека для эффективного управления недетерминированными древовидными автоматами (C ++)