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

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

• 1 Описание
• 2 Пример
• 3 Линейные системы перезаписи без контекста (LCFRS)
• 4 См. Также
• 5 Ссылки

A GCFG состоит из двух компонентов: набора функций композиции, которые объединяют строковые кортежи, и набора правил перезаписи. Все композиционные функции имеют вид $f\; (⟨x\; 1,...,\; xm⟩,\; ⟨y\; 1,...,\; yn⟩,...)\; =\; \gamma \; \{\backslash \; displaystyle\; f\; (\backslash \; langle\; x\_\; \{1\; \},...,\; x\_\; \{m\}\; \backslash \; rangle,\; \backslash \; langle\; y\_\; \{1\},...,\; y\_\; \{n\}\; \backslash \; rangle,...)\; =\; \backslash \; gamma\}$, где $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$- это либо однострочный кортеж, либо некоторое использование (потенциально другой) функции композиции, которая сводится к строковому кортежу. Правила перезаписи выглядят так: $X\; \to \; f\; (Y,\; Z,...)\; \{\backslash \; Displaystyle\; X\; \backslash \; to\; f\; (Y,\; Z,...)\}$, где $Y\; \{\backslash \; displaystyle\; Y\}$, $Z\; \{\backslash \; displaystyle\; Z\}$,... - строковые кортежи или нетерминальные символы.

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

Простой перевод контекстно-свободной грамматики в GCFG может быть выполнен следующим образом. Учитывая грамматику в (1), которая порождает язык палиндрома $\{ww\; R:\; w\; \in \; \{a,\; b\}\; \ast \}\; \{\backslash \; displaystyle\; \backslash \; \{ww\; ^\; \{R\}:\; w\; \backslash \; in\; \backslash \; \{a,\; b\; \backslash \}\; ^\; \{*\}\; \backslash \}\}$, где $w\; R\; \{\backslash \; displaystyle\; w\; ^\; \{R\}\}$- строка, обратная $w\; \{\backslash \; displaystyle\; w\; \}$, мы можем определить композиционную функцию conc, как в (2a), и правила перезаписи, как в (2b).

$S\; \to \; ϵ\; |\; a\; S\; a\; |\; б\; S\; б\; \{\backslash \; Displaystyle\; S\; \backslash \; к\; \backslash \; эпсилон\; ~\; |\; ~\; aSa\; ~\; |\; ~\; bSb\}$

(1)

$конц\; (⟨x⟩,\; ⟨y⟩,\; ⟨z⟩)\; =\; ⟨xyz⟩\; \{\backslash \; displaystyle\; conc\; (\backslash \; langle\; x\; \backslash \; rangle,\; \backslash \; langle\; y\; \backslash \; rangle,\; \backslash \; langle\; z\; \backslash \; rangle)\; =\; \backslash \; langle\; xyz\; \backslash \; rangle\}$

(2a)

$S\; \to \; conc\; (⟨ϵ⟩,\; ⟨ϵ⟩,\; ⟨ϵ\; ⟩)\; |\; c\; o\; n\; c\; (⟨a⟩,\; S,\; ⟨a⟩)\; |\; конц\; (⟨б⟩,\; S,\; ⟨б⟩)\; \{\backslash \; displaystyle\; S\; \backslash \; to\; conc\; (\backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle,\; \backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle,\; \backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle)\; ~\; |\; ~\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; S,\; \backslash \; langle\; a\; \backslash \; rangle)\; ~\; |\; ~\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; S,\; \backslash \; langle\; b\; \backslash \; rangle)\}$

(2b)

Производство CF для abbbba составляет

S

aSa

abSba

abbSbba

abbbba

и соответствующая продукция GCFG равна

$S\; \to \; conc\; (⟨a⟩,\; S,\; ⟨a⟩)\; \{\backslash \; displaystyle\; S\; \backslash \; to\; conc\; (\backslash \; langle\; a\; \backslash \; rangle\; S,\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$conc\; (⟨a⟩,\; conc\; (⟨b⟩,\; S,\; ⟨b⟩),\; ⟨a⟩)\; \{\backslash \; displaystyle\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; S,\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$conc\; (⟨a⟩,\; conc\; (⟨b⟩,\; conc\; (⟨b⟩,\; S,\; ⟨b⟩),\; ⟨\; б⟩),\; ⟨a⟩)\; \{\backslash \; displaystyle\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; S,\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$conc\; (⟨a⟩,\; conc\; (⟨b⟩,\; conc\; (⟨b⟩,\; conc\; (⟨ϵ⟩,\; ⟨ϵ⟩,\; ⟨ϵ⟩),\; ⟨b⟩),\; ⟨)\; б⟩),\; ⟨a⟩)\; \{\backslash \; Displaystyle\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; conc\; (\backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle,\; \backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle,\; \backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle),\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$conc\; (⟨a⟩,\; conc\; (⟨b⟩,\; conc\; (⟨b⟩,\; ⟨ϵ⟩,\; ⟨b⟩),\; ⟨\; б⟩),\; ⟨a⟩)\; \{\backslash \; displaystyle\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; \backslash \; langle\; \backslash \; epsilon\; \backslash \; rangle,\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$conc\; (⟨a⟩,\; conc\; (⟨b⟩,\; ⟨bb⟩,\; ⟨b⟩),\; ⟨a⟩)\; \{\backslash \; displaystyle\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; conc\; (\backslash \; langle\; b\; \backslash \; rangle,\; \backslash \; langle\; bb\; \backslash \; rangle,\; \backslash \; langle\; b\; \backslash \; rangle),\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$conc\; (⟨a⟩,\; ⟨bbbb⟩,\; ⟨a⟩)\; \{\backslash \; displaystyle\; conc\; (\backslash \; langle\; a\; \backslash \; rangle,\; \backslash \; langle\; bbbb\; \backslash \; rangle,\; \backslash \; langle\; a\; \backslash \; rangle)\}$

$⟨abbbba⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; abbbba\; \backslash \; rangle\}$

Вейр (1988) описывает два свойства композиционных функций: линейность и регулярность. Функция, определяемая как $f\; (x\; 1,...,\; X\; n)\; =...\; \{\backslash \; displaystyle\; f\; (x\_\; \{1\},...,\; x\_\; \{n\})\; =...\}$является линейным тогда и только тогда, когда каждая переменная появляется не более одного раза по обе стороны от =, что делает $f\; (x)\; =\; g\; (x,\; y)\; \{\backslash \; displaystyle\; f\; (x)\; =\; g\; (x,\; y)\}$линейный, но не $f\; (x)\; =\; g\; (x,\; х)\; \{\backslash \; Displaystyle\; е\; (х)\; =\; г\; (х,\; х)\}$. Функция, определяемая как $f\; (x\; 1,...,\; X\; n)\; =...\; \{\backslash \; displaystyle\; f\; (x\_\; \{1\},...,\; x\_\; \{n\})\; =...\}$является правильным, если левая и правая стороны имеют точно такие же переменные, что делает $f\; (x,\; y)\; =\; g\; (y,\; x)\; \{\backslash \; displaystyle\; f\; (x,\; y)\; =\; g\; (y,\; x)\}$обычный, но не $f\; (x)\; =\; g\; (\; икс,\; y)\; \{\backslash \; displaystyle\; f\; (x)\; =\; g\; (x,\; y)\}$или $f\; (x,\; y)\; =\; g\; (x)\; \{\backslash \; displaystyle\; f\; (x,\; y)\; =\; g\; (x)\}$.

Грамматика, в которой все функции композиции являются как линейными, так и регулярными, называется Линейной системой перезаписи без контекста (LCFRS). LCFRS - это надлежащий подкласс GCFG, то есть он имеет строго меньшую вычислительную мощность, чем GCFG в целом.

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

LCFRS слабо эквивалентны (локально установленным) многокомпонентным тегам (), а также (MCFG [1] ). и минималистские грамматики (MG). Языки, сгенерированные LCFRS (и их слабые эквиваленты), могут быть проанализированы за полиномиальное время.

• Грамматика конкатенации диапазонов

1. ^ Weir, David Jeremy (сентябрь 1988 г.). Характеризация формально-зависимых грамматических формальностей (PDF) (Ph.D.). Бумага. AAI8908403. Университет Пенсильвании в Анн-Арборе.
2. ^Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик. Springer Science Business Media. п. 33. ISBN 978-3-642-14846-0.
3. ^Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик. Springer Science Business Media. п. 35-36. ISBN 978-3-642-14846-0.
4. ^Йохан F.A.K. ван Бентем; Алиса тер Мёлен (2010). Справочник по логике и языку (2-е изд.). Эльзевир. п. 404. ISBN 978-0-444-53727-0.