Основная грамматика

концепция в обобщенном контексте свободная грамматика

Головная грамматика (HG) - это грамматический формализм, представленный в Карла Полларда (1984) как расширение контекстно-свободной грамматики класса грамматик. Таким образом, основная грамматика является разновидностью грамматики структуры фраз , в отличие от грамматики зависимостей. Класс грамматик заголовков является подмножеством линейных систем контекстно-свободной перезаписи.

Один из типичных способов определения грамматик заголовков - заменить терминальные строки CFG индексированными терминальными строками, где индекс обозначает "заголовок" слово строки. Так, например, правило CF, такое как $A\; \to \; abc\; \{\backslash \; displaystyle\; A\; \backslash \; to\; abc\}$, может вместо этого быть $A\; \to \; (abc,\; 0)\; \{\backslash \; displaystyle\; A\; \backslash \; to\; (\; abc,\; 0)\}$, где 0-й терминал, a, является заголовком результирующей терминальной строки. Для удобства записи такое правило может быть записано как просто терминальная строка, с головным терминалом, обозначенным какой-то меткой, как в $A\; \to \; a\; ^\; bc\; \{\backslash \; displaystyle\; A\; \backslash \; to\; \{\backslash \; widehat\; \{a\}\; \}\; bc\}$.

Затем ко всем правилам перезаписи добавляются две основные операции: упаковка и конкатенация.

• 1 Операции над заголовками
  • 1.1 Обертывание
  • 1.2 Конкатенация
  • 1.3 Форма правил
• 2 Пример
• 3 Формальные свойства
  • 3.1 Эквивалентности
• 4 Ссылки

Обертывание

Обертывание - это операция над строками с двумя заголовками, определенными следующим образом:

Пусть $\alpha \; x\; ^\; \beta \; \{\backslash \; displaystyle\; \backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta\}$и $\gamma \; y\; ^\; \delta \; \{\backslash \; displaystyle\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta\}$быть конечными строками с заголовком на x и y соответственно.

$вес\; (\alpha \; x\; ^\; \beta ,\; \gamma \; y\; ^\; \delta )\; знак\; равно\; \alpha \; x\; \gamma \; y\; ^\; \delta \; \beta \; \{\backslash \; displaystyle\; w\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta,\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta)\; =\; \backslash \; alpha\; x\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta\; \backslash \; beta\}$

Конкатенация

Конкатенация - это семейство операций над n>0 строками с заголовком, определенное для n = 1, 2, 3 следующим образом:

Пусть $\alpha \; x\; ^\; \beta \; \{\backslash \; displaystyle\; \backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta\}$, $\gamma \; y\; ^\; \delta \; \{\backslash \; displaystyle\; \backslash \; gamma\; \{\backslash \; widehat\; \{\; y\}\}\; \backslash \; delta\}$и $\zeta \; z\; ^\; \eta \; \{\backslash \; displaystyle\; \backslash \; zeta\; \{\backslash \; widehat\; \{z\}\}\; \backslash \; eta\}$быть конечными строками, возглавляемыми x, y, и z соответственно.

$c\; 1,\; 0\; (\alpha \; x\; ^\; \beta )\; =\; \alpha \; x\; ^\; \beta \; \{\backslash \; displaystyle\; c\_\; \{1,0\}\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta)\; =\; \backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta\}$

$с\; 2,\; 0\; (\alpha \; x\; ^\; \beta ,\; \gamma \; y\; ^\; \delta )\; =\; \alpha \; x\; ^\; \beta \; \gamma \; y\; \delta \; \{\backslash \; displaystyle\; c\_\; \{2,0\}\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta,\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta)\; =\; \backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta\; \backslash \; gamma\; y\; \backslash \; delta\}$

$c\; 2,\; 1\; (\alpha \; x\; ^\; \beta ,\; \gamma \; y\; ^\; \delta )\; =\; \alpha \; Икс\; \beta \; \gamma \; Y\; ^\; \delta \; \{\backslash \; Displaystyle\; c\_\; \{2,1\}\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta,\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta)\; =\; \backslash \; alpha\; x\; \backslash \; beta\; \backslash \; gamma\; \{\; \backslash \; widehat\; \{y\}\}\; \backslash \; delta\}$

$с\; 3,\; 0\; (\alpha \; x\; ^\; \beta ,\; \gamma \; y\; ^\; \delta ,\; \zeta \; z\; ^\; \eta )\; =\; \alpha \; x\; ^\; \beta \; \gamma \; y\; \delta \; \zeta \; z\; \eta \; \{\backslash \; displaystyle\; c\_\; \{3,\; 0\}\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta,\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta,\; \backslash \; zeta\; \{\backslash \; widehat\; \{z\}\}\; \backslash \; eta)\; =\; \backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; бета\; \backslash \; гамма\; y\; \backslash \; дельта\; \backslash \; дзета\; z\; \backslash \; эта\}$

$с\; 3,\; 1\; (\alpha \; x\; ^\; \beta ,\; \gamma \; y\; ^\; \delta ,\; \zeta \; z\; ^\; \eta )\; =\; \alpha \; x\; \beta \; \gamma \; y\; ^\; \delta \; \zeta \; z\; \eta \; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta,\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta,\; \backslash \; zeta\; \{\backslash \; widehat\; \{z\}\}\; \backslash \; eta)\; =\; \backslash \; alpha\; x\; \backslash \; beta\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta\; \backslash \; zeta\; z\; \backslash \; eta\}$

$c\; 3,\; 2\; (\alpha \; x\; ^\; \beta ,\; \gamma \; y\; ^\; \delta ,\; \zeta \; z\; ^\; \eta )\; =\; \alpha \; x\; \beta \; \gamma \; y\; \delta \; \zeta \; z\; ^\; \eta \; \{\; \backslash \; дис\; стиль\; игры\; c\_\; \{3,2\}\; (\backslash \; alpha\; \{\backslash \; widehat\; \{x\}\}\; \backslash \; beta,\; \backslash \; gamma\; \{\backslash \; widehat\; \{y\}\}\; \backslash \; delta,\; \backslash \; zeta\; \{\backslash \; widehat\; \{z\}\}\; \backslash \; eta)\; =\; \backslash \; alpha\; x\; \backslash \; beta\; \backslash \; gamma\; y\; \backslash \; delta\; \backslash \; zeta\; \{\backslash \; widehat\; \{z\}\}\; \backslash \; eta\}$

И так далее для . Можно резюмировать шаблон здесь просто как «объединить некоторое количество терминальных строк m с заголовком строки n, обозначенным как заголовок результирующей строки».

Форма правил

Правила основной грамматики определяются в терминах этих двух операций, причем правила принимают любую из форм

$X\; \to \; w\; (\alpha ,\; \beta )\; \{\backslash \; displaystyle\; X\; \backslash \; вес\; (\backslash \; альфа,\; \backslash \; бета)\}$

$Икс\; \to \; см,\; n\; (\alpha ,\; \beta ,...)\; \{\backslash \; Displaystyle\; X\; \backslash \; к\; c\_\; \{м,\; n\}\; (\backslash \; альфа,\; \backslash \; бета,...)\; \}$

где $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$, $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$,... каждое из них либо конечная строка, либо нетерминальный символ.

Грамматики заголовка могут генерировать язык $\{anbncndn:\; n\; \ge \; 0\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{n\}\; b\; ^\; \{n\}\; c\; ^\; \{n\; \}\; d\; ^\; \{n\}:\; n\; \backslash \; geq\; 0\; \backslash \}\}$. Мы можем определить грамматику следующим образом:

$S\; \to \; c\; 1,\; 0\; (ϵ\; ^)\; \{\backslash \; displaystyle\; S\; \backslash \; to\; c\_\; \{1,0\}\; (\{\backslash \; widehat\; \{\backslash \; epsilon\}\})\}$

$S\; \to \; c\; 3,\; 1\; (a\; ^,\; T,\; d\; ^)\; \{\backslash \; displaystyle\; S\; \backslash \; to\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; T,\; \{\backslash \; widehat\; \{d\}\})\}$

$T\; \to \; w\; (S,\; b\; ^\; c)\; \{\backslash \; displaystyle\; T\; \backslash \; to\; w\; (S,\; \{\backslash \; widehat\; \{b\}\}\; c)\}$

Вывод для «abcd» следующий:

$S\; \{\backslash \; displaystyle\; S\}$

$c\; 3,\; 1\; (a\; ^,\; T,\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; T,\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; вес\; (S,\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (S,\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (c\; 1,\; 0\; (ϵ\; ^),\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (c\_\; \{1,0\}\; (\{\backslash \; widehat\; \{\backslash \; epsilon\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; вес\; (ϵ\; ^,\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (\{\backslash \; widehat\; \{\backslash \; epsilon\}\},\; \{\backslash \; widehat\; \{\; b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; b\; ^\; c,\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; \{\backslash \; widehat\; \{b\}\}\; c,\; \{\backslash \; widehat\; \{d\}\})\}$

$ab\; ^\; cd\; \{\backslash \; displaystyle\; a\; \{\backslash \; widehat\; \{b\}\}\; cd\}$

А для "aabbccdd":

$S\; \{\backslash \; displaystyle\; S\}$

$c\; 3,\; 1\; (a\; ^,\; T,\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,\; 1\}\; (\{\backslash \; widehat\; \{a\}\},\; T,\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (S,\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{\; 3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (S,\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (c\; 3,\; 1\; (a\; ^,\; T,\; d\; ^),\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; T,\; \{\backslash \; widehat\; \{d\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (c\; 3,\; 1\; (a\; ^,\; w\; (S,\; b\; ^\; c),\; d\; ^),\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (c\_\; \{\; 3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (S,\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{\; d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (c\; 3,\; 1\; (a\; ^,\; w\; (c\; 1,\; 0\; (ϵ\; ^),\; b\; ^\; c),\; d\; ^),\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\}),\; w\; (c\_\; \{1,0\}\; (\{\backslash \; widehat\; \{\backslash \; epsilon\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (c\; 3,\; 1\; (a\; ^,\; w\; (ϵ\; ^,\; b\; ^\; c),\; d\; ^),\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\}),\; w\; (\{\; \backslash \; widehat\; \{\backslash \; epsilon\}\},\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (c\; 3,\; 1\; (a\; ^,\; b\; ^\; c,\; d\; ^),\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; \{\backslash \; widehat\; \{b\}\}\; c,\; \{\backslash \; widehat\; \{d\}\}),\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{\; d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; w\; (ab\; ^\; cd,\; b\; ^\; c),\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; w\; (\; a\; \{\backslash \; widehat\; \{b\}\}\; cd,\; \{\backslash \; widehat\; \{b\}\}\; c),\; \{\backslash \; widehat\; \{d\}\})\}$

$c\; 3,\; 1\; (a\; ^,\; abb\; ^\; ccd,\; d\; ^)\; \{\backslash \; displaystyle\; c\_\; \{3,1\}\; (\{\backslash \; widehat\; \{a\}\},\; ab\; \{\backslash \; widehat\; \{b\}\}\; ccd,\; \{\backslash \; widehat\; \{d\}\})\}$

$aabb\; ^\; ccdd\; \{\backslash \; displaystyle\; aab\; \{\backslash \; widehat\; \{b\}\; \}\; ccdd\}$

Эквивалентности

Виджай-Шанкер и Вейр (1994) демонстрируют, что линейно проиндексированные грамматики, комбинаторно-категориальные грамматики, смежные с деревом грамматики и главные грамматики являются слабо эквивалентными формализмами, поскольку все они определяют те же строковые языки.