Грамматика буквального движения

В лингвистике и информатике теоретической грамматики буквальных движений (LMG) представляют собой грамматический формализм, предназначенный для характеристики определенных экстрапозиционных явлений естественного языка, таких как топизация и межсерийная зависимость . LMG расширяют класс контекстно-свободных грамматик (CFG), добавляя семантику перезаписи, подобную функции, соответствующей шаблону, а также операции привязки переменных и удаления косой черты. Ручные пулеметы были представлены А.В.Грёнинком в 1995 году.

Описание

Основная операция перезаписи LMG очень похожа на операцию CFG, с добавлением аргументов к нетерминальным символам. Если правило контекстно-свободной перезаписи подчиняется общей схеме $S\to \alpha$ для некоторых нетерминальных $S$ и некоторая строка терминалов и/или нетерминалов $\alpha$правило перезаписи LMG подчиняется общей схеме $X(x_{1},...,x_{n})\to \alpha$, где X — нетерминал с арностью n (называемый предикатом в терминологии LMG), и $\alpha$ представляет собой строку «элементов», как определено ниже. Аргументы $x_{i}$ представляют собой строки терминальных символов и/или переменных символов, определяющих шаблон аргумента. В случае, когда шаблон аргумента имеет несколько соседних символов переменных, шаблон аргумента будет соответствовать всем разделам фактического значения, которые объединяются. Таким образом, если предикат $f(xy)$ и фактическая картина $f(ab)$, есть три действительных совпадения: $x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon$. Таким образом, одно правило на самом деле представляет собой семейство альтернатив.

«Предмет» в грамматике буквального движения является одним из

• $f(x_{1},\ldots ,x_{n})$, предикат арности n,
• $x{\text{:}}f(x_{1},\ldots ,x_{n})$, переменная, связывающая x со строкой, созданной $f(x_{1},...,x_{n})$, или
• $f(x_{1},\ldots ,x_{n})/\alpha$, удаление косой черты $f(x_{1},...,x_{n})$ по строке терминалов и/или переменных $\alpha$.

В правиле типа $f(x_{1},...,x_{m})\to \alpha \ y{\text{:}}g(z_{1},...z_{n})\ \beta$, переменная y привязана к любой конечной строке, которую создает предикат g, и в $\alpha$ и $\beta$, все вхождения y заменяются этой строкой, и $\alpha$ и $\beta$ производятся так, как если бы терминальная строка всегда была там.

Предмет $x/y$, где x — это что-то, что создает терминальную строку (либо сама терминальная строка, либо некоторый предикат), а y — это строка терминалов и/или переменных, перезаписывается как пустая строка ( $\epsilon$) тогда и только тогда, когда $g(y_{1},...,y_{n})=z$, и иначе вообще не может быть переписано.

Пример

LMG могут характеризовать язык, не относящийся к CF. $\{a^{n}b^{n}c^{n}:n\geq 1\}$ следующее:

$S()\to x{\text{:}}A()\ B(x)$

$A()\to a\ A()$

$A()\to \epsilon$

$B(xy)\to a/x\ b\ B(y)c$

$B(\epsilon )\to \epsilon$

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

$S()\to x{\text{:}}A()\ B(x)\to x{\text{:}}(a\ A())\ B(x)\to x{\text{:}}(aa\ A())\ B(x)\to x{\text{:}}aa\ B(x)\to aa\ B(aa)$

$\to aa\ a/a\ b\ B(a)\ c\to aab\ B(a)\ c\to aab\ a/a\ b\ B()\ cc\to aabb\ B()\ cc\ \to aabbcc$

Вычислительная мощность

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