Конъюнктивная грамматика

Конъюнктивные грамматики — это класс формальных грамматик. изучал формальную теорию языка .Они расширяют базовый тип грамматик,контекстно -свободные грамматики ,с операцией конъюнкции .Помимо явного союза,конъюнктивные грамматики допускают неявное дизъюнкцию представлено несколькими правилами для одного нетерминального символа,это единственная логическая связка, которую можно выразить в контекстно-свободных грамматиках.Союз может использоваться, в частности,указать пересечение языков.Дальнейшее расширение соединительных грамматик.известные как булевы грамматики дополнительно допускает явное отрицание .

Правила соединительной грамматики имеют вид

$A\to \alpha _{1}\And \ldots \And \alpha _{m}$

где $A$ является нетерминалом и $\alpha _{1}$, ..., $\alpha _{m}$представляют собой строки, состоящие из символов в $\Sigma$ и $V$ (конечные множества терминальных и нетерминальных символов соответственно).Неформально такое правило утверждает, что каждая строка $w$ над $\Sigma$который удовлетворяет каждому из синтаксических условий, представленныхк $\alpha _{1}$, ..., $\alpha _{m}$следовательно, удовлетворяет условию, определенному $A$.

Формальное определение

Соединительная грамматика $G$ определяется 4- кортежом $G=(V,\Sigma ,R,S)$ где

1. V — конечное множество; каждый элемент $v\in V$ называется нетерминальным символом или переменной . Каждая переменная представляет отдельный тип фразы или предложения в предложении. Переменные также иногда называют синтаксическими категориями.
2. Σ — конечное множество терминальных s, не пересекающихся с V , которые составляют фактическое содержание предложения. Набор терминалов представляет собой алфавит языка, определяемый G. грамматикой
3. R — конечное множество продукций, каждая из которых имеет вид $A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}$ для некоторых $A$ в $V$ и $\alpha _{i}\in (V\cup \Sigma )^{*}$. Члены R называются правилами или продуктами грамматики.
4. S — начальная переменная (или начальный символ), используемая для представления всего предложения (или программы). Это должен быть элемент V .

Обычно все правые части одной и той же левой части перечисляются в одной строке, используя | ( символ трубы ), чтобы разделить их. Правила $A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}$ и $A\rightarrow \beta _{1}\&\ldots \&\beta _{n}$ следовательно, можно записать как $A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\ |\ \beta _{1}\&\ldots \&\beta _{n}$.

Два эквивалентных формальных определенияязыка, определенного соединительной грамматикой, существуют.Одно определение основано на представлении грамматикикак система языковых уравнений с объединением, пересечением и конкатенациейи рассматривая его наименьшее решение.Другое определение обобщает Хомского Генеративное определение контекстно-свободных грамматик использование переписывания терминов вместо соединения и конкатенации.

Определение по выводу

Для любых строк $u,v\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}$, мы говорим, что u непосредственно дает v , записанный как $u\Rightarrow v\,$, если

• либо есть правило $A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\in R$ такой, что $u\,=u_{1}Au_{2}$ и $v\,=u_{1}(\alpha _{1}\&\ldots \&\alpha _{m})u_{2}$,
• или существует строка $w\in (V\cup \Sigma )^{*}$ такой, что $u\,=u_{1}(w\&\ldots \&w)u_{2}$ и $v\,=u_{1}wu_{2}$.

Для любой строки $w\in \Sigma ^{*},$ мы говорим, что G порождает w , записанное как $S\ {\stackrel {*}{\Rightarrow }}\ w$, если $\exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}$ такой, что $S=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=w$.

Язык грамматики $G=(V,\Sigma ,R,S)$ — это набор всех строк, которые он генерирует.

Пример

Грамматика $G=(\{S,A,B,C,D\},\{a,b,c\},R,S)$, с постановками

$S\rightarrow AB\&DC$,

$A\rightarrow aA\ |\ \epsilon$,

$B\rightarrow bBc\ |\ \epsilon$,

$C\rightarrow cC\ |\ \epsilon$,

$D\rightarrow aDb\ |\ \epsilon$,

является соединительным. Типичный вывод

$S\Rightarrow (AB\&DC)\Rightarrow (aAB\&DC)\Rightarrow (aB\&DC)\Rightarrow (abBc\&DC)\Rightarrow (abc\&DC)\Rightarrow (abc\&aDbC)\Rightarrow (abc\&abC)\Rightarrow (abc\&abcC)\Rightarrow (abc\&abc)\Rightarrow abc$

Можно показать, что $L(G)=\{a^{n}b^{n}c^{n}:n\geq 0\}$. Язык не является контекстно-свободным, что доказывает лемма о накачке для контекстно-свободных языков .

Алгоритмы разбора

Хотя выразительная сила союзных грамматикбольше, чем у контекстно-свободных грамматик,соединительные грамматики сохраняют часть последних.Самое главное — существуют обобщения основных алгоритмов контекстно-свободного парсинга, в линейном времени включая рекурсивный спуск , кубического времени обобщенный LR ,кубическое время Кок-Касами-Младшего ,а также алгоритм Valiant, работающий так же быстро, как умножение матриц.

Теоретические свойства

Свойство, которое неразрешимо уже для контекстно-свободных языков или конечных их пересечений, должно быть неразрешимо и для конъюнктивных грамматик; к ним относятся: пустота , конечность , регулярность , бесконтекстность , включение и эквивалентность.

Семейство конъюнктивных языков замкнуто относительно объединения, пересечения, конкатенации и звезды Клини , но не относительно гомоморфизма строк , префикса , суффикса и подстроки.Замыкание при дополнении и гомоморфизме струн без ε все еще остаются открытыми проблемами (по состоянию на 2001 год).

Исследована выразительная сила грамматик над однобуквенным алфавитом.

Эта работа послужила основойдля изучения языковых уравнений более общего вида.

Синхронизированные попеременные автоматы с опусканием вниз

Айзиковиц и Камински представил новый класс автоматов с выталкиванием (PDA), названный синхронизированными автоматами с попеременным выталкиванием (SAPDA). Они доказали, что это эквивалентно конъюнктивным грамматикам точно так же, как недетерминированные КПК эквивалентны контекстно-свободным грамматикам.

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

• Артур Еж (2007). «Соединительные грамматики порождают нерегулярные унарные языки» (PDF) (Слайды выступления на Международной конференции по развитию теории языка ) . Проверено 5 ноября 2019 г.
• «Страница Александра Охотина о союзных грамматиках» . 9 октября 2011 года . Проверено 5 ноября 2019 г.
• Александр Охотин (2007). «Девять открытых задач по конъюнктивной и булевой грамматикам» . Бюллетень ЕАТКС . Архивировано из оригинала 29 сентября 2007 г.
• Александр Охотин (2013). «Соединительные и логические грамматики: истинный общий случай контекстно-свободных грамматик». Обзор компьютерных наук . 9 : 27–59. дои : 10.1016/j.cosrev.2013.06.001 . Эта статья заменяет предыдущие обзоры «Обзор конъюнктивных грамматик» (Бюллетень EATCS, 2004 г.) и «Девять открытых задач для конъюнктивных и булевых грамматик».
• Еж, Артур (2008). «Соединительные грамматики порождают нерегулярные унарные языки». Международный журнал основ компьютерных наук . 19 (3): 597–615. дои : 10.1142/S012905410800584X . Версия технического отчета (pdf)