Контролируемая грамматика

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

Управление по заданным последовательностям

Грамматики с предписанными последовательностями — это грамматики, в которых последовательность применения правил каким-либо образом ограничена. Существует четыре различных версии грамматик предписанных последовательностей: грамматики, управляемые языком (часто называемые просто управляемыми грамматиками), матричные грамматики , векторные грамматики и программированные грамматики.

В стандартном формализме контекстно-свободной грамматики сама грамматика рассматривается как четырехкортеж . $G=(N,T,S,P)$, где N — набор нетерминальных/фразовых символов , T — непересекающийся набор символов терминала/слова, S — специально назначенный начальный символ, выбранный из N , а P — набор правил продукции, таких как $X\to \alpha$, где X — некоторый член N , и $\alpha$ какой-то член $(N\cup T)^{*}$.

Продукция такой грамматики представляет собой последовательность правил в P , которые при применении в порядке последовательности приводят к терминальной строке. То есть можно рассматривать множество мыслимых дифференцирований в G как множество $\{p_{1}p_{2}...p_{n}:n\geq 0\}$и язык G как набор терминальных строк $L(G)=\{w\in T^{*}:S\Rightarrow _{p_{1}}...\Rightarrow _{p_{n}}w\}$. Управляющие грамматики серьезно относятся к этому определению языка, порожденному грамматикой, конкретизируя набор производных как аспект грамматики. Таким образом, заданная грамматика с контролируемой последовательностью представляет собой, по крайней мере, приблизительно пятикортежную грамматику. $G=(N,T,S,P,R)$ где все, кроме R, такое же, как и в CFG, а R представляет собой бесконечный набор допустимых последовательностей вывода. $p_{1}p_{2}...p_{n}$.

Множество R из-за своей бесконечности почти всегда (хотя и не обязательно) описывается с помощью какого-либо более удобного механизма, такого как грамматика (как в грамматиках, управляемых языком) или набор матриц или векторов (как в матричных и векторных грамматиках). ). Таким образом, различные варианты предписанных грамматик последовательностей различаются тем, как последовательность выводов определяется поверх контекстно-свободной базы. Поскольку матричные и векторные грамматики по сути являются частными случаями грамматик, управляемых языком, примеры первых двух ниже не приводятся.

Грамматики, контролируемые языком

Грамматики, управляемые языком, — это грамматики, в которых производственные последовательности составляют четко определенный язык произвольной природы, обычно, хотя и не обязательно регулярный, на основе набора (опять же обычно, хотя и не обязательно) контекстно-свободных производственных правил. Они также часто имеют шестой набор в грамматическом кортеже, что делает его $G=(N,T,S,P,R,F)$, где F — множество продукций, которые разрешено применять безосновательно. Отныне эта версия грамматик, управляемых языком, с так называемой «проверкой внешнего вида».

Теоретико-доказательное описание

Мы позволяем регулярно контролируемой контекстно-свободной грамматике с проверкой внешнего вида быть шестикортежной $G=(N,T,S,P,R,F)$ где N , T , S и P определены как в CFG, R — подмножество P*, регулярный язык над P , а F — некоторое подмножество P. составляющее Затем мы определяем отношение немедленного вывода $\Rightarrow _{p_{i}}$ следующее:

Учитывая некоторые строки x и y , обе в $(N\cup T)^{*}$и некоторое правило $p=A\to w\in P$,

$x\Rightarrow _{p}^{ac}y$

имеет место, если либо

$x=x_{1}Ax_{2}$ и $y=y_{1}wy_{2}$, или

$x=y$ и $p\in F$

Интуитивно это означает, что правило может применяться к строке, если левая часть правила присутствует в этой строке, или если правило входит в набор «бесприменимых» правил, которые могут «применяться» к строке без меняя что-либо. Это требование, согласно которому должны применяться непусто применимые правила, представляет собой аспект проверки внешнего вида такой грамматики. Языком такого типа грамматики является просто набор терминальных строк. $L(G)=\{w\in T^{*}:S\Rightarrow _{p_{1}}^{ac}w_{1}\Rightarrow _{p_{2}}^{ac}w_{2}\Rightarrow _{p_{3}}^{ac}...\Rightarrow _{p_{n}}^{ac}w,\ for\ some\ p_{1}p_{2}...p_{n}\in R\}$.

Пример

Рассмотрим простую (хотя и не самую простую) контекстно-свободную грамматику, генерирующую язык $\{a^{n}:n\geq 1\}$:

Позволять $G=(\{S,A,X\},\{a\},S,\{f,g,h,k,l\})$, где

$f:S\to AA$

$g:S\to X$

$h:A\to S$

$k:A\to X$

$l:S\to a$

В управляемой языком форме эта грамматика просто $G^{\prime }=(\{S,A,X\},\{a\},S,\{f,g,h,k,l\},(f|g|h|k|l)^{*},\{f,g,h,k,l\})$ (где $(f|g|h|k|l)^{*}$ — регулярное выражение, обозначающее набор всех последовательностей продукционных правил). Простая модификация этой грамматики: изменение набора управляющих последовательностей R на набор $(f^{*}gh^{*}k)^{*}l^{*}$и изменив свой бессмысленный набор правил F на $\{g,k\}$, дает грамматику, которая генерирует язык, отличный от CF. $\{a^{2^{n}}:n\geq 0\}$. Чтобы увидеть, как это сделать, рассмотрим общий случай некоторой строки с n экземплярами S в ней, т.е. $S^{n}$ (особый случай $S^{1}$ тривиально выводит строку a, которая $a^{2^{0}}$, неинтересный факт).

Если мы выбрали некоторую произвольную производственную последовательность $f^{u}gh^{v}k...$, мы можем рассмотреть три возможности: $n=u$, $n<u$, и $n>u$ Когда $n=u$ мы переписываем все n экземпляров S как AA , применяя правило f к строке u раз, и переходим к применению g , которое применяется бессмысленно (в силу того, что оно находится в F ). Когда $n<u$, мы переписываем все n экземпляров S как AA , а затем пытаемся выполнить перезапись n+1 , используя правило f , но это терпит неудачу, потому что больше нет S для перезаписи, а f не находится в F и поэтому не может применяться бессмысленно, таким образом, когда $n<u$, вывод не удался. Наконец, тогда $n>u$, мы переписываем u экземпляров S один экземпляр S для перезаписи при последующем применении g , переписывая S как X. , оставляя по крайней мере Учитывая, что ни одно правило этой грамматики никогда не переписывает X , такой вывод никогда не приведет к созданию терминальной строки. Таким образом, только выводы с $n=u$ когда-нибудь успешно перезапишет строку $S^{n}$. Аналогичные рассуждения справедливы и для числа A s и v . В общем, тогда мы можем сказать, что единственные действительные выводы имеют структуру $S^{n}\Rightarrow _{f}...\Rightarrow _{f}A^{2n}\Rightarrow {g}A^{2n}\Rightarrow {h}...\Rightarrow {h}S^{2n}\Rightarrow {k}S^{2n}$ создаст терминальные строки грамматики. Правила X в сочетании со структурой управления по существу вынуждают все S перезаписывать как AA до того, как любые A будут перезаписаны как S , что опять же вынуждено произойти перед всеми еще более поздними итерациями над S. цикл до-АА . Наконец, S перезаписываются как s . Таким образом, количество S удваивается для каждого экземпляра $f^{8}gh^{*}k$ который появляется в последовательности, производной от терминала.

Выбрав две случайные нетерминальные производные последовательности и одну терминальную, мы можем увидеть это в работе:

Позволять $s_{1}=ffghkll$, то мы получим неудавшийся вывод:

$S\Rightarrow _{f}^{ac}AA\Rightarrow _{f}^{ac}{\text{failure: f cannot apply, no S to rewrite}}$

Позволять $s_{2}=fghhhkll$, то мы получим неудавшийся вывод:

$S\Rightarrow _{f}^{ac}AA\Rightarrow _{g}^{ac}AA\Rightarrow _{h}^{ac}SA\Rightarrow _{h}^{ac}SS\Rightarrow _{h}^{ac}{\text{failure: h cannot apply, no A to rewrite}}$

Позволять $s_{3}=fghhkll$, то мы получим успешный вывод:

$S\Rightarrow _{f}^{ac}AA\Rightarrow _{g}^{ac}AA\Rightarrow _{h}^{ac}SA\Rightarrow _{h}^{ac}SS\Rightarrow _{k}^{ac}SS\Rightarrow _{l}^{ac}aS\Rightarrow _{l}^{ac}aa$

Подобные выводы со вторым циклом $f^{*}gh^{*}k$ производить только SSSS . Показан только (продолжающийся) успешный вывод:

$...\Rightarrow SS\Rightarrow _{f}^{ac}AAS\Rightarrow _{f}^{ac}AAAA\Rightarrow _{g}^{ac}AAAA$

$\Rightarrow _{h}^{ac}SAAA\Rightarrow _{h}^{ac}SSAA\Rightarrow _{h}^{ac}SSSA\Rightarrow _{h}^{ac}SSSS\Rightarrow _{k}^{ac}SSSS$

$\Rightarrow _{l}^{ac}aSSS\Rightarrow _{l}^{ac}aaSS\Rightarrow _{l}^{ac}aaaS\Rightarrow _{l}^{ac}aaaa$

Матричные грамматики

Матричные грамматики (расширенные в отдельной статье ) представляют собой частный случай регулярных управляемых контекстно-свободных грамматик, в которых язык производственных последовательностей имеет форму $(m_{1}|m_{2}|...|m_{n})^{*}$, где каждая «матрица» $m_{i}$ представляет собой единую последовательность. Для удобства такая грамматика представляется не грамматикой над P , а просто набором матриц вместо языка и правил продукции. Таким образом, матричная грамматика представляет собой пятикортеж $G=(N,T,M,S,F)$, где N , T , S и F определяются по существу так же, как это было сделано ранее ( на этот раз F является подмножеством M ), а M представляет собой набор матриц $m_{i}=p_{i,1}p_{i,2}...p_{i,n_{i}}$ где каждый $p_{i,j}$ это контекстно-свободное производственное правило.

Таким образом, отношение производных в матричной грамматике определяется просто как:

Учитывая некоторые строки x и y , обе в $(N\cup T)^{*}$и некоторая матрица $m=p_{1}p_{2}...p_{n}\in M$,

$x\Rightarrow _{m}^{ac}y$

имеет место, если либо

$x=x_{1}Ax_{2}$, $y=y_{1}wy_{2}$, и $A\Rightarrow _{p_{1}}^{ac}w_{1}\Rightarrow _{p_{2}}^{ac}w_{2}\Rightarrow _{p_{3}}^{ac}...\Rightarrow _{p_{n}}^{ac}w$, или

$x=y$ и $m\in F$

Неформально, матричная грамматика — это просто грамматика, в которой во время каждого цикла перезаписи должна выполняться определенная последовательность операций перезаписи, а не просто одна операция перезаписи, т. е. одно правило «запускает» каскад других правил. Подобные явления могут быть реализованы в стандартной контекстно-зависимой идиоме, как это делалось в фонологии, основанной на правилах, и в более ранней Трансформационной грамматике , с помощью так называемых «подпитывающих» правил, которые изменяют вывод таким образом, чтобы обеспечить среду для нефакультативное правило, которое следует сразу за ним.

Векторные грамматики

Векторные грамматики тесно связаны с матричными грамматиками и фактически могут рассматриваться как особый класс матричных грамматик, в котором если $m\in M$, то таковы и все его перестановки $p(m)$. Однако для удобства мы определим векторные грамматики следующим образом: векторная грамматика представляет собой 5-кортеж $G=(N,T,M,S,F)$, где N , T и F определены ранее ( F снова является подмножеством M ), и где M представляет собой набор векторов $m_{i}=\{p_{1},p_{2},...,p_{n}\}$, каждый вектор представляет собой набор контекстно-свободных правил.

Тогда отношение производных в векторной грамматике будет следующим:

Учитывая некоторые строки x и y , обе в $(N\cup T)^{*}$и некоторая матрица $m=\{p_{1},p_{2},...,p_{n}\}\in M$,

$x\Rightarrow _{m}^{ac}y$

имеет место, если либо

$x=x_{1}Ax_{2}$, $y=y_{1}wy_{2}$, и $A\Rightarrow _{p_{i_{1}}}^{ac}w_{1}\Rightarrow _{p_{i_{2}}}^{ac}w_{2}\Rightarrow _{p_{i_{3}}}^{ac}...\Rightarrow _{p_{i_{n}}}^{ac}w$, где $m=\{p_{i_{1}},p_{i_{2}},...,p_{i_{n}}\}$, или

$x=y$ и $m\in F$

Обратите внимание, что количество продукционных правил, используемых в последовательности вывода, n , совпадает с количеством продукционных правил в векторе. Неофициально векторная грамматика — это такая грамматика, в которой применяется набор продукций, причем каждая продукция применяется ровно один раз в произвольном порядке для получения одной строки из другой. Таким образом, векторные грамматики почти идентичны матричным грамматикам, за исключением ограничения на порядок, в котором продукция должна происходить во время каждого цикла применения правил.

Программированные грамматики

Программированные грамматики представляют собой относительно простые расширения контекстно-свободных грамматик с постепенным контролем вывода. Программированная грамматика представляет собой четырехкортеж $G=(N,T,S,P)$, где N , T и S такие же, как в контекстно-свободной грамматике, а P — набор кортежей $(p,\sigma ,\phi )$, где p — контекстно-свободное производственное правило, $\sigma$ является подмножеством P (называемым полем успеха), и $\phi$ является подмножеством P (называемым полем отказа). Если поле сбоя каждого правила в P пусто, в грамматике отсутствует проверка внешнего вида, а если хотя бы одно поле сбоя не пусто, грамматика имеет проверку внешнего вида. Отношение вывода в программной грамматике определяется следующим образом:

Даны две строки $x,y\in (N\cup T)^{*}$и некоторое правило $p=(A\to w,\sigma ,\phi )\in P$,

$x\Rightarrow _{p}y$ и $x=x'Ax'',y=x'wx''$, или

$x=y$ и А не появляется в x.

Язык программируемой грамматики G определяется путем ограничения правила вывода, как $L(G)=\{w\in (N\cup T)^{*}:S\Rightarrow _{p_{1}}w_{1}\Rightarrow _{p_{2}}...\Rightarrow _{p_{n}}w\}$, где для каждого $p_{i}=(A_{i}\to v_{i},\sigma _{i},\phi _{i})$, или $w_{i-1}=x_{i-1}Ax'_{i-1},w_{i}=x_{i-1}v_{i}x'_{i-1},\ and\ p_{i+1}\in \sigma _{i}$ или $w_{i-1}=w_{i},p_{i+1}\in \phi _{i}$.

Интуитивно понятно, что при применении правила p в запрограммированной грамматике правило может либо успешно перезаписать символ в строке, и в этом случае последующее правило должно находиться в поле успеха p , либо правило может не переписать символ (таким образом, применяется бессмысленно), и в этом случае последующее правило должно быть в p поле отказа s. Выбор того, какое правило применить к начальной строке, является произвольным, в отличие от грамматики, управляемой языком, но как только выбор сделан, правила, которые могут быть применены после этого, с этого момента ограничивают последовательность правил.

Пример

Как и многие другие контролируемые грамматики, запрограммированные грамматики могут генерировать язык $\{a^{2^{n}}:n\geq 0\}$:

Позволять $G=(\{S,A\},\{a\},S,\{r_{1},r_{2},r_{3}\})$, где

$r_{1}=(S\to AA,\{r_{1}\},\{r_{2}\})$

$r_{2}=(A\to S,\{r_{2}\},\{r_{1},r_{3}\})$

$r_{3}=(S\to a,\{r_{3}\},\emptyset )$

Вывод строки aaaa следующий:

$S\Rightarrow _{r_{1}}AA\Rightarrow _{r_{1}}AA\Rightarrow _{r_{2}}SA\Rightarrow _{r_{2}}SS\Rightarrow _{r_{2}}SS$

$\Rightarrow _{r_{1}}AAS\Rightarrow _{r_{1}}AAAA\Rightarrow _{r_{1}}AAAA$

$\Rightarrow _{r_{2}}SAAA\Rightarrow _{r_{2}}SSAA\Rightarrow _{r_{2}}SSSA\Rightarrow _{r_{2}}SSSS\Rightarrow _{r_{2}}SSSS$

$\Rightarrow _{r_{3}}aSSS\Rightarrow _{r_{3}}aaSS\Rightarrow _{r_{3}}aaaS\Rightarrow _{r_{3}}aaaa\Rightarrow _{r_{3}}aaaa$

Как видно из вывода и правил, каждый раз $r_{1}$ и $r_{2}$ преуспевают, они возвращают информацию самим себе, что заставляет каждое правило продолжать перезаписывать строку снова и снова, пока оно больше не сможет это делать. В случае неудачи деривация может переключиться на другое правило. В случае $r_{1}$, это означает перезапись всех S как AA , а затем переключение на $r_{2}$. В случае $r_{2}$, это означает перезапись всех A как S , а затем переключение либо на $r_{1}$, что приведет к удвоению количества произведенных S или к $r_{3}$ который преобразует S в a s, а затем останавливает вывод. Каждый цикл через $r_{1}$ затем $r_{2}$ поэтому либо удваивает исходное количество S , либо преобразует S в a . Тривиальный случай генерации a , если его трудно увидеть, просто включает в себя бессмысленное применение $r_{1}$, таким образом перепрыгивая прямо к $r_{2}$ что также бессмысленно применимо, а затем перепрыгиваем к $r_{3}$ производит . который

Управление по условиям контекста

В отличие от грамматик, управляемых предписанными последовательностями продукционных правил, которые ограничивают пространство допустимых выводов, но не ограничивают типы предложений, к которым может применяться продукционное правило, грамматики, управляемые контекстными условиями, не имеют ограничений последовательности, но допускают ограничения различной сложности на предложения, к которым применяется производственное правило. Подобно грамматикам, управляемым предписанными последовательностями, существует множество различных типов грамматик, управляемых условиями контекста: условные грамматики, полуусловные грамматики, грамматики случайного контекста и упорядоченные грамматики.

Условные грамматики

Условные грамматики — это простейшая версия грамматик, управляемых контекстными условиями. Структура условной грамматики очень похожа на структуру обычной переписанной грамматики: $G=(N,T,S,P)$, где N , T и S определены в контекстно-свободной грамматике, а P представляет собой набор пар формы $(p,R)$ где p — производственное правило (обычно контекстно-свободное), а R — язык (обычно регулярный) над $N\cup T$. Когда R является регулярным, R можно просто выразить как регулярное выражение.

Теоретико-доказательное определение

Используя это определение условной грамматики, мы можем определить отношение производных следующим образом:

Даны две строки $x,y\in (N\cup T)^{*}$, и некоторое производственное правило $p=(A\to w,R)\in P$,

$x\Rightarrow _{p}y$ тогда и только тогда, когда $x=x'Ax''$, $y=x'wx''$, и $x\in R$

Тогда неформально правило продукции для некоторой пары в P может применяться только к строкам, которые находятся на языке ее контекста. Так, например, если бы у нас была какая-то пара $(S\to x,a^{*}Sb^{*})$, мы можем применить это только к строкам, состоящим из любого количества букв , за которыми следует ровно только S, за которым следует любое количество букв b , то есть к предложениям в $\{a^{m}Ab^{n}:m,n\geq 0\}$, например, строки S , aSb , aaaS , aSbbbbbb и т. д. Это не может применяться к таким строкам, как xSy , aaaSxbbb и т. д.

Пример

Условные грамматики могут генерировать контекстно-зависимый язык. $\{a^{2^{n}}:n\geq 0\}$.

Позволять $G=(\{S,S'\},\{a\},\{f,g,h\},S)$, где

$f=(S\to AA,A^{*}S^{+})$

$g=(A\to B,B^{*}A^{+})$

$h=(B\to S,S^{*}B^{+})$

$k=(S\to a,a^{*}S^{+})$

Затем мы можем сгенерировать предложение aaaa со следующим выводом:

$S\Rightarrow _{f}AA\Rightarrow _{g}BA\Rightarrow _{g}BB$

$\Rightarrow _{h}SB\Rightarrow _{h}SS\Rightarrow _{f}AAS\Rightarrow _{f}AAAA$

$\Rightarrow _{g}BAAA\Rightarrow _{g}BBAA\Rightarrow _{g}BBBA\Rightarrow _{g}BBBB$

$\Rightarrow _{h}SBBB\Rightarrow _{h}SSBB\Rightarrow _{h}SSSB\Rightarrow _{h}SSSS$

$\Rightarrow _{k}aSSS\Rightarrow _{k}aaSS\Rightarrow _{k}aaaS\Rightarrow _{k}aaaa$

Полуусловные грамматики

Полуусловная грамматика очень похожа на условную грамматику, и технически класс полуусловных грамматик является подмножеством условных грамматик. Вместо указания того, как должна выглядеть вся строка, чтобы правило применялось, полуусловные грамматики указывают, что для применения правила строка должна иметь в качестве подстрок все строки из некоторого набора строк и ни одной из другого набора. . Тогда формально полуусловная грамматика представляет собой кортеж $G=(N,T,S,P)$, где N , T и S определены как в CFG, а P представляет собой набор правил, таких как $(p,R,Q)$ где p — производственное правило (обычно контекстно-свободное), а R и Q — конечные наборы строк. Тогда отношение производных можно определить следующим образом.

Для двух струн $xAx',xwx'\in (N\cup T)^{*}$и некоторое правило $p=(A\to w,R,Q)\in P$,

$xAx'\Rightarrow _{p}xwx'$ тогда и только тогда, когда каждая строка в R является подстрокой $xAx'$, и ни одна строка в Q не является подстрокой $xAx'$

Тогда язык полуусловной грамматики тривиально представляет собой набор терминальных строк. $L(G)=\{w\in T^{*}:S\Rightarrow ^{*}w\}$.

Ниже приведен пример полуусловной грамматики, также как пример грамматик случайного контекста.

Случайные контекстные грамматики

Грамматика случайного контекста — это полуусловная грамматика, в которой R и Q являются подмножествами N. множества Поскольку подмножества N являются конечными множествами над $(N\cup T)^{*}$, ясно, что грамматики случайного контекста действительно являются разновидностью полуусловных грамматик.

Пример

Подобно условным грамматикам, грамматики случайного контекста (и, следовательно, полуусловные грамматики) могут генерировать язык $\{a^{2^{n}}:n\geq 0\}$. Одна грамматика, которая может это сделать:

Позволять $G=(\{S,X,Y,A\},\{a\},S,\{r_{1},r_{2},r_{3},r_{4},r_{5}\})$, где

$r_{1}=(S\to XX,\emptyset ,\{Y,A\})$

$r_{2}=(X\to Y,\emptyset ,\{S\})$

$r_{3}=(Y\to S,\emptyset ,\{X\})$

$r_{4}=(S\to A,\emptyset ,\{X,Y\})$

$r_{5}=(A\to a,\emptyset ,\{S\})$

Рассмотрим теперь постановку aaaa :

$S\Rightarrow _{r_{1}}XX\Rightarrow _{r_{2}}YX\Rightarrow _{r_{2}}YY\Rightarrow _{r_{3}}SY\Rightarrow _{r_{3}}SS$

$\Rightarrow _{r_{1}}XXS\Rightarrow _{r_{1}}XXXX\Rightarrow _{r_{2}}YXXX\Rightarrow _{r_{2}}YYXX\Rightarrow _{r_{2}}YYYX\Rightarrow _{r_{2}}YYYY$

$\Rightarrow _{r_{3}}SYYY\Rightarrow _{r_{3}}SSYY\Rightarrow _{r_{3}}SSSY\Rightarrow _{r_{3}}SSSS$

$\Rightarrow _{r_{4}}ASSS\Rightarrow _{r_{4}}AASS\Rightarrow _{r_{4}}AAAS\Rightarrow _{r_{4}}AAAA$

$\Rightarrow _{r_{5}}aAAA\Rightarrow _{r_{5}}aaAA\Rightarrow _{r_{5}}aaaA\Rightarrow _{r_{5}}aaaa$

Поведение множеств R здесь тривиально: любую строку можно переписать в соответствии с ними, поскольку они не требуют наличия каких-либо подстрок. Однако поведение множеств Q более интересно. В $r_{1}$ вынуждает нас , набор Q перезаписать S , тем самым начиная процесс S -удвоения, только тогда, когда нет Y или A в строке , что означает только тогда, когда предыдущий процесс S -удвоения был полностью инициирован, исключая возможность удвоения только некоторых S . В $r_{2}$, который переводит процесс S -удвоения на второй этап, мы не можем начать этот процесс до тех пор, пока первый этап не будет завершен и не останется больше S , которые можно попытаться удвоить, потому что набор Q препятствует применению правила, если есть S символ все еще находится в строке. В $r_{3}$, мы завершаем этап удвоения, возвращая S обратно только тогда, когда больше не осталось X , которые нужно перезаписывать, то есть когда второй этап завершен. Мы можем проходить через эти этапы столько раз, сколько захотим, переписывая все S в XX , затем переписывая каждый X в Y, а затем каждый Y в S , и, наконец, заканчивая заменой каждого S на A , а затем на a. . Поскольку правило замены S на A запрещает применение к строке с X в ней, мы не можем применить его в середине первого этапа процесса S -удвоения, что снова не позволяет нам удвоить только некоторые S .

Упорядоченные грамматики

Упорядоченные грамматики, возможно, являются одним из самых простых расширений грамматик в контролируемую грамматическую область. Упорядоченная грамматика — это просто кортеж $G=(N,T,S,P)$ где N , T и S идентичны правилам в CFG, а P — набор контекстно-свободных правил перезаписи с частичным упорядочением. $<$. Частичный порядок затем используется для определения того, какое правило применить к строке, если применимо несколько правил. Тогда отношение производных будет следующим:

Учитывая некоторые строки $xAx',xwx'\in (N\cup T)^{*}$ и некоторые правила $p=A\to w\in P$,

$xAx'\Rightarrow _{p}xwx'$ тогда и только тогда, когда нет правила $p'=A\to w'\in P$ такой, что $p<p'$.

Пример

Как и многие другие грамматики, управляемые контекстом, упорядоченные грамматики могут обеспечивать применение правил в определенном порядке. Поскольку это важнейшее свойство предыдущих грамматик, которые могли породить язык $\{a^{2^{n}}:n\geq 0\}$, неудивительно, что грамматика, которая явно использует порядок правил, а не кодирует его через строковые контексты, также должна иметь возможность захватывать этот язык. И как оказалось, существует именно такая упорядоченная грамматика:

Позволять $G=(\{S,X,Y,Z,A\},\{a\},S,P)$, где P — частично упорядоченное множество, описываемое диаграммой Хассе

Вывод строки aaaa прост:

$S\Rightarrow _{S\to XX}\ XX\ \Rightarrow _{X\to Y}\ YX\ \Rightarrow _{X\to Y}\ YY\ \Rightarrow _{Y\to S}\ SY\ \Rightarrow _{Y\to S}\ YY$

$\Rightarrow _{S\to XX}\ XXS\ \Rightarrow _{S\to XX}\ XXXX$

$\Rightarrow _{X\to Y}\ YXXX\ \Rightarrow _{X\to Y}\ YYXX\ \Rightarrow _{X\to Y}\ YYYX\ \Rightarrow _{X\to Y}\ YYYY$

$\Rightarrow _{Y\to S}\ SYYY\ \Rightarrow _{Y\to S}\ SSYY\ \Rightarrow _{Y\to S}\ SSSY\ \Rightarrow _{Y\to S}\ SSSS$

$\Rightarrow _{S\to A}\ ASSS\ \Rightarrow _{S\to A}\ AASS\ \Rightarrow _{S\to A}\ AAAS\ \Rightarrow _{S\to A}\ AAAA$

$\Rightarrow _{A\to a}\ aAAA\ \Rightarrow _{A\to a}\ aaAA\ \Rightarrow _{A\to a}\ aaaA\ \Rightarrow _{A\to a}\ aaaa$

На каждом шаге вывода происходит циклическая перезапись. Обратите внимание: если на пятом шаге SY у нас было четыре варианта: $Y\to Z,S\to Z,Y\to S,S\to A$, первые два из которых останавливают вывод, поскольку Z невозможно переписать. В примере мы использовали $Y\to S$ чтобы вывести SS , но подумайте, выбрали ли мы $S\to A$ вместо. Мы бы создали строку AS , варианты которой: $Y\to Z$ и $A\to Z$, оба из которых останавливают вывод. Таким образом, со строкой SY и наоборот с YS мы должны переписать Y , чтобы получить SS . То же самое справедливо и для других комбинаций, так что в целом упорядочивание приводит к остановке вывода или продолжению переписывания всех S в XX , затем всех X в Y , затем всех Y в S и так далее. , затем, наконец, все S в A , затем все A в as . Таким образом, строка $S^{n}$ можно переписать только как $A^{n}$ который производит s или как $S^{2n}$. Начиная с n = 0 , должно быть ясно, что эта грамматика генерирует только язык $\{a^{2^{n}}:n\geq 0\}$.

Грамматики с параллелизмом

Еще одним классом управляемых грамматик является класс грамматик с параллелизмом в применении операции перезаписи, в котором каждый шаг перезаписи может (или должен) перезаписывать более одного нетерминала одновременно. Они также бывают нескольких разновидностей: индийские параллельные грамматики, k-грамматики, грамматики с разрозненным контекстом, неупорядоченные грамматики с разбросанным контекстом и k-простые матричные грамматики. Опять же, варианты различаются тем, как определяется параллелизм.

Индийские параллельные грамматики

Индийская параллельная грамматика — это просто CFG, в которой для использования правила перезаписи все экземпляры нетерминального символа правил должны быть переписаны одновременно. Так, например, дана строка aXbYcXd с двумя экземплярами X и некоторым правилом $X\to w$, единственный способ переписать эту строку с помощью этого правила — переписать ее как awbYcwd ; ни awbYcXd , ни aXbYcwd не являются допустимыми перезаписями в индийской параллельной грамматике, поскольку они не переписывают все экземпляры X .

Индийские параллельные грамматики могут легко создать язык $\{ww:w\in \{a,b\}^{*}\}$:

Позволять $G=(\{S,A\},\{a,b\},S,\{f,g,h,k\})$, где

$f=S\to AA$

$g=A\to aA$

$h=A\to bA$

$k=A\to \epsilon$

Генерировать aabaab довольно просто:

$S\Rightarrow _{f}AA\Rightarrow _{g}aAaA\Rightarrow _{g}aaAaaA\Rightarrow _{h}aabAaabA\Rightarrow _{k}aabaab$

Язык $\{a^{2^{n}}:n\geq 0\}$ еще проще:

Позволять $G=(\{S\},\{a\},S,P)$, где P состоит из

$S\to SS$

$S\to a$

Уже из первого правила и требования, чтобы все экземпляры нетерминала переписывались одновременно по одному и тому же правилу, должно быть очевидно, что число S удваивается на каждом шаге перезаписи с использованием первого правила, что дает шаги вывода $S\Rightarrow S^{2}\Rightarrow S^{4}\Rightarrow S^{8}\Rightarrow ...$. Окончательное применение второго правила заменяет все S на s , показывая тем самым, как этот простой язык может создать язык $\{a^{2^{n}}:n\geq 0\}$.

К-грамматики

K-грамматика — это еще один вид параллельной грамматики, сильно отличающийся от индийской параллельной грамматики, но все же обладающий определенным уровнем параллелизма. В k-грамматике для некоторого числа k на каждом шаге необходимо переписать ровно k нетерминальных символов (кроме первого шага, где единственный символ в строке является начальным символом). Если в строке меньше k нетерминалов, деривация не удалась.

3-грамматика может создать язык $\{a^{n}b^{n}c^{n}:n\geq 0\}$, как можно видеть ниже:

Позволять $G=(\{S,A,B,C\},\{a,b,c\},S,P)$, где P состоит из:

$S\to ABC$

$A\to aA$

$A\to a$

$B\to bB$

$B\to b$

$C\to cC$

$C\to c$

Со следующим выводом для aaabbbccc :

$S\Rightarrow ABC\Rightarrow aAbBcC\Rightarrow aaAbbBccC\Rightarrow aaabbbccc$

На каждом шаге вывода, кроме первого и последнего, мы использовали саморекурсивные правила. $A\to aA,B\to bB,C\to cC$. Если бы мы не использовали рекурсивные правила, а использовали бы, скажем, $A\to a,B\to bB,C\to cC$, если одно из правил не является саморекурсивным, количество нетерминалов уменьшится до 2, что сделает невозможным дальнейшее выведение строки, поскольку в ней будет слишком мало нетерминалов для перезаписи.

Русские параллельные грамматики

Русские параллельные грамматики находятся где-то между индийскими параллельными грамматиками и k-грамматиками, определяемыми как $G=(N,T,S,P)$, где N , T и S такие же, как в контекстно-свободной грамматике, а P — набор пар $(A\to w,k)$, где $A\to w$ является контекстно-свободным продукционным правилом, а k равно 1 или 2. Применение правила $p=(A\to w,k)$ включает переписывание k вхождений A в w одновременно.

Разбросанные контекстные грамматики

Грамматика с рассеянным контекстом представляет собой четырехкортеж. $G=(N,T,S,P)$ где N , T и S определены как в контекстно-свободной грамматике, а P — это набор кортежей, называемых матрицами. $p=(A_{1}\to w_{1},...,A_{n}\to w_{n})$, где $n>0$ может варьироваться в зависимости от матрицы. Отношение производных для такой грамматики имеет вид

$x\Rightarrow _{p}y$ тогда и только тогда, когда

$p=(A_{1}\to w_{1},...,A_{n}\to w_{n})\in P$, и

$x=x_{1}A_{1}x_{2}...x_{n}A_{n}x_{n+1},y=x_{1}w_{1}x_{2}...x_{n}w_{n}x_{n+1}$, для $x_{i}\in (N\cup T)^{*}$

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

контекста — это грамматика рассеянного контекста, в которой для каждого правила из P каждая из его перестановок также находится в P. Неупорядоченная грамматика рассеянного Таким образом, правило и его перестановки могут быть представлены в виде набора, а не кортежей.

Пример

Грамматики с разбросанным контекстом способны описывать язык. $\{a^{n}b^{n}c^{n}:n\geq 0\}$ довольно легко.

Позволять $G=(\{S,A,B,C\},\{a,b,c\},S,\{r_{1},r_{2},r_{3}\})$, где

$r_{1}=(S\to ABC)$

$r_{2}=(A\to aA,B\to bB,C\to cC)$

$r_{3}=(A\to \epsilon ,B\to \epsilon ,C\to \epsilon )$

Вывод aaabbbccc тогда тривиален:

$S\Rightarrow _{r_{1}}ABC\Rightarrow _{r_{2}}aAbBcC\Rightarrow _{r_{2}}aaAbbBccC\Rightarrow _{r_{2}}aaaAbbbBcccC\Rightarrow _{r_{3}}aaabbbccc$