Грамматика регулярных деревьев - Regular tree grammar

В теоретическая информатика и формальная теория языка, а регулярная древовидная грамматика (РИТЭГ) это формальная грамматика который описывает набор направленные деревья, или же термины.[1] А грамматика регулярных слов можно рассматривать как особый вид регулярной древовидной грамматики, описывающей набор одно-дорожка деревья.

Определение

Обычная древовидная грамматика грамм определяется набором

грамм = (N, Σ, Z, п),

куда

  • N конечное множество нетерминалов,
  • Σ является ранжированный алфавит (т.е. алфавит, символы которого имеют связанный арность ) не пересекаются с N,
  • Z - начальный нетерминал, с Z ∈ N, и
  • п является конечным множеством продукций вида А → т, с А ∈ N, и т ∈ ТΣ(N), куда ТΣ(N) является ассоциированным алгебра терминов, т.е. множество всех деревьев, составленных из символов в Σ ∪ N согласно их арности, где нетерминалы считаются нулевыми.

Вывод деревьев

Грамматика грамм неявно определяет набор деревьев: любое дерево, которое может быть получено из Z используя набор правил п как говорят описанный к граммЭтот набор деревьев известен как язык из граммФормально соотношение ⇒грамм на съемочной площадке ТΣ(N) определяется следующим образом:

Дерево т1∈ ТΣ(N) возможно полученный за один шаг в дерево т2 ∈ ТΣ(N) (короче: т1 ⇒грамм т2), если есть контекст S и производство (А→т) ∈ п такой, что:

  • т1 = S[А], и
  • т2 = S[т].

Здесь контекст означает дерево с ровно одной дыркой; если S такой контекст, S[т] обозначает результат заполнения дерева т в отверстие S.

Древовидный язык, созданный грамм это язык L(грамм) = { т ∈ ТΣ | Z ⇒грамм* т }.

Здесь, ТΣ обозначает множество всех деревьев, составленных из символов Σ, а ⇒грамм* обозначает последовательные применения ⇒грамм.

Язык, порожденный некоторой регулярной грамматикой деревьев, называется обычный язык дерева.

Примеры

Пример дерево происхождения из G1 в линейном (верхняя левая таблица) и графическом (основное изображение) обозначении

Позволять грамм1 = (N1, Σ1,Z1,п1), куда

  • N1 = {Bool, BList } - наш набор нетерминалов,
  • Σ1 = { истинный, ложный, ноль, минусы(.,.)} - наш ранжированный алфавит, арности обозначены фиктивными аргументами (т.е. символом минусы имеет арность 2),
  • Z1 = BList это наш начальный нетерминал, и
  • набор п1 состоит из следующих постановок:
    • Bool → ложный
    • Bool → истинный
    • BList → ноль
    • BList → минусы(Bool,BList)

Пример вывода из грамматики грамм1 является

BList⇒ минусы(Bool,BList)⇒ минусы(ложный,минусы(Bool,BList))⇒ минусы(ложный,минусы(истинный,ноль)).

На изображении показаны соответствующие дерево происхождения; это дерево деревьев (основное изображение), тогда как дерево производных в грамматики слов дерево строк (верхняя левая таблица).

Древовидный язык, созданный грамм1 - это набор всех конечных списков логических значений, то есть L(грамм1) оказывается равным ТΣ1.Грамматика грамм1 соответствует объявлениям алгебраических типов данных (в Стандартный ML язык программирования):

  тип данных Bool    = ложный    | истинный  тип данных BList    = ноль    | минусы из Bool * BList

Каждый член L(грамм1) соответствует значению Standard-ML типа BList.

В качестве другого примера пусть грамм2 = (N1, Σ1,BList1,п1 ∪ п2), используя нетерминальный набор и алфавит сверху, но расширяя производственный набор п2, состоящий из следующих постановок:

  • BList1 → минусы(истинный,BList)
  • BList1 → минусы(ложный,BList1)

Язык L(грамм2) - это множество всех конечных списков логических значений, содержащих истинный Хотя бы один раз. Набор L(грамм2) не имеет тип данных аналог в Standard ML или на любом другом функциональном языке. Это собственное подмножество L(грамм1Вышеупомянутый примерный термин находится в L(грамм2), как показывает следующий вывод:

BList1⇒ минусы(ложный,BList1)⇒ минусы(ложный,минусы(истинный,BList))⇒ минусы(ложный,минусы(истинный,ноль)).

Свойства языка

Если L1, L2 оба являются обычными древовидными языками, тогда дерево устанавливает L1 ∩ L2, L1 ∪ L2, и L1 L2 также являются регулярными древовидными языками, и разрешимо ли L1 ⊆ L2, и будет ли L1 = L2.

Альтернативные характеристики и отношение к другим формальным языкам

Приложения

Применения обычных древовидных грамматик включают:

Смотрите также

Рекомендации

  1. ^ «Регулярные древовидные грамматики как формализм для недостаточной спецификации области». CiteSeerX  10.1.1.164.5484. Цитировать журнал требует | журнал = (помощь)
  2. ^ Комон, Юбер; Дауше, Макс; Гиллерон, Реми; Лёдинг, Кристоф; Жакемар, Флоран; Лужие, Денис; Тисон, Софи; Томмази, Марк (12 октября 2007 г.). «Методы и приложения древовидных автоматов». Получено 25 января 2016.CS1 maint: ref = harv (связь)
  3. ^ Alur, R .; Мадхусудан, П. (2004). «Языки с явным раскрытием» (PDF). Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04. С. 202–211. Дои:10.1145/1007352.1007390. ISBN  978-1581138528.CS1 maint: ref = harv (связь) Раздел 4, теорема 5,
  4. ^ Alur, R .; Мадхусудан, П. (2009). «Добавление структуры вложенности к словам» (PDF). Журнал ACM. 56 (3): 1–43. CiteSeerX  10.1.1.145.9971. Дои:10.1145/1516512.1516518.CS1 maint: ref = harv (связь) Раздел 7
  5. ^ Эммельманн, Гельмут (1991). «Выбор кода путем регулярно контролируемого переписывания терминов». Генерация кода - концепции, инструменты, методы. Мастерские по вычислительной технике. Springer. С. 3–29.
  6. ^ Комон, Хуберт (1990). "Формулы уравнений в упорядоченных алгебрах". Proc. ИКАЛП.
  7. ^ Gilleron, R .; Tison, S .; Томмази, М. (1993). «Решение систем заданных ограничений с использованием древовидных автоматов». 10-й ежегодный симпозиум по теоретическим аспектам информатики. LNCS. 665. Springer. С. 505–514.
  8. ^ Бургхардт, Йохен (2002). «Аксиоматизация конечных алгебр». Достижения в области искусственного интеллекта. LNAI. 2479. Springer. С. 222–234. arXiv:1403.7347. Bibcode:2014arXiv1403.7347B. ISBN  3-540-44185-9.
  9. ^ Зив-Укельсон, Смолы (2016). Алгоритмы поиска в сети регулярной древовидной грамматики и их применение для анализа паттернов вирусных заражений человека. J. of Comp. Bio. [1]

дальнейшее чтение

  • Регулярные древовидные грамматики были описаны еще в 1968 году:
  • Книга, посвященная древовидной грамматике: Ниват, Морис; Подельски, Андреас (1992). Древовидные автоматы и языки. Исследования в области компьютерных наук и искусственного интеллекта. 10. Северная Голландия.
  • Алгоритмы на регулярных древовидных грамматиках обсуждаются с точки зрения эффективности в: Aiken, A .; Мерфи, Б. (1991). «Реализация регулярных древовидных выражений». Конференция ACM по языкам функционального программирования и компьютерной архитектуре. С. 427–447. CiteSeerX  10.1.1.39.3766.
  • Учитывая отображение деревьев в веса, Дональд Кнут обобщение Алгоритм кратчайшего пути Дейкстры может применяться к грамматике обычного дерева для вычисления для каждого нетерминала минимального веса выводимого дерева. Основываясь на этой информации, легко перечислить его язык в порядке возрастания веса. В частности, любой нетерминал с бесконечным минимальным весом порождает пустой язык. Видеть: Кнут, Д. (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации. 6 (1): 1–5. Дои:10.1016/0020-0190(77)90002-3.
  • Обычные древовидные автоматы были обобщены, чтобы допускать проверки на равенство между родственными узлами в деревьях. Видеть: Bogaert, B .; Тисон, Софи (1992). «Ограничения равенства и неравенства на прямых подпунктах в древовидных автоматах». Proc. Девятый STACS. LNCS. 577. Springer. С. 161–172.
  • Разрешение проверки равенства между более глубокими узлами приводит к неразрешимости. Видеть: Томмази, М. (1991). Automates d'Arbres avec Tests d'Egalités entre Cousins ​​Germains. LIFL-IT.