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

Эта статья нужно больше ссылки на другие статьи помочь интегрировать в энциклопедию. Пожалуйста помоги улучшить эту статью добавляя ссылки которые имеют отношение к контексту в существующем тексте. (Октябрь 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Описание

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

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

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

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

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

Пример

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

${ Displaystyle S () к х { текст {:}} A () B (x)}$

${ Displaystyle А () к А ()}$

${ Displaystyle А () к epsilon}$

${ Displaystyle В (ху) к а / х б В (у) с}$

${ Displaystyle В ( эпсилон) к эпсилон}$

Вывод для aabbcc, используя круглые скобки также для группировки, поэтому

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

${ Displaystyle к aa a / a b B (a) c к aab B (a) c к aab a / a b B () cc к aabb B ( ) cc to aabbcc}$

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

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

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