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

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

• 1 Основы
• 2 Исчисление Ламбека
  • 2.1 Связь с контекстно-независимыми грамматиками
  • 2.2 Обозначение
• 3 Исторические заметки
• 4 Некоторые определения
• 5 Уточнения категориальной грамматики
  • 5.1 Характеристики и подкатегории
  • 5.2 Состав функций
  • 5.3 Соединение
  • 5.4 Разрывность
• 6 См. Также
• 7 Ссылки
• 8 Дополнительная литература
• 9 Внешние ссылки

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

Категориальная грамматика имеет общие черты с просто типизированным лямбда-исчислением. В то время как лямбда-исчисление имеет только один тип функции $A\; \to \; B\; \{\backslash \; displaystyle\; A\; \backslash \; rightarrow\; B\}$, категориальная грамматика обычно имеет два типа функций, один из которых применяется слева и один справа. Например, простая категориальная грамматика может иметь два типа функций: $B\; /\; A\; \{\backslash \; displaystyle\; B\; /\; A\; \backslash ,\; \backslash !\}$и $A\; \setminus \; B\; \{\backslash \; displaystyle\; A\; \backslash \; backslash\; B\}.$. Первый, $B\; /\; A\; \{\backslash \; displaystyle\; B\; /\; A\; \backslash ,\; \backslash !\}$, является типом фразы, которая приводит к фразе типа $B\; \{\backslash \; displaystyle\; B\; \backslash ,\; \backslash !\}$, если за ним (справа) следует фраза типа $A\; \{\backslash \; displaystyle\; A\; \backslash ,\; \backslash !\}$. Второй, $A\; \setminus \; B\; \{\backslash \; displaystyle\; A\; \backslash \; backslash\; B\; \backslash ,\; \backslash !\}$, представляет собой тип фразы, в результате которой получается фраза типа $B\; \{\backslash \; displaystyle\; B\; \backslash ,\; \backslash !\}$, если ему предшествует (слева) фраза типа $A\; \{\backslash \; displaystyle\; A\; \backslash ,\; \backslash !\}$.

Нотация основана на алгебре. Умножение дроби на знаменатель (т. Е. Соединение) дает числитель. Поскольку конкатенация не является коммутативной, имеет значение, находится ли знаменатель слева или справа. Конкатенация должна быть на той же стороне, что и знаменатель, чтобы она сократилась.

Первый и самый простой вид категориальной грамматики называется базовой категориальной грамматикой или иногда AB-грамматикой (после Айдукевич и Бар-Гиллеля ). Учитывая набор примитивных типов $Prim\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Prim\}\}\; \backslash ,\; \backslash !\}$, пусть $Tp\; (Prim)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\; \backslash ,\; \backslash !\}$- набор типов, созданных из примитивных типов. В базовом случае это наименьший набор, такой что $Prim\; \subseteq \; Tp\; (Prim)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Prim\}\}\; \backslash \; substeq\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\}$и если $X,\; Y\; \in \; Tp\; (Prim)\; \{\backslash \; displaystyle\; X,\; Y\; \backslash \; in\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\}$затем $(X\; /\; Y),\; (Y\; \setminus \; X)\; \in \; Tp\; (Prim)\; \{\backslash \; displaystyle\; (X\; /\; Y),\; (Y\; \backslash \; backslash\; X)\; \backslash \; in\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\; \}\})\}$. Думайте об этом как о чисто формальных выражениях, свободно генерируемых из примитивных типов; любая семантика будет добавлена ​​позже. Некоторые авторы предполагают фиксированный бесконечный набор примитивных типов, используемых всеми грамматиками, но, делая примитивные типы частью грамматики, вся конструкция сохраняется конечной.

Базовая категориальная грамматика - это кортеж $(\Sigma ,\; Prim,\; S,\; ◃)\; \{\backslash \; displaystyle\; (\backslash \; Sigma,\; \{\backslash \; text\; \{Prim\}\},\; S,\; \backslash \; треугольникleft)\}$где $\Sigma \; \{\backslash \; displaystyle\; \backslash \; Sigma\; \backslash ,\; \backslash !\}$- конечный набор символов, $Prim\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Prim\}\}\; \backslash ,\; \backslash !\}$- конечный набор примитивных типов, а $S\; \in \; Tp\; (Prim)\; \{\backslash \; displaystyle\; S\; \backslash \; in\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\}$.

отношение $◃\; \{\backslash \; displaystyle\; \backslash \; треугольникleft\}$- это лексикон, который связывает типы с символами $(◃)\; \subseteq \; Tp\; (Prim)\; \times \; \Sigma \; \{\backslash \; displaystyle\; (\backslash \; Triangleleft)\; \backslash \; substeq\; \{\backslash \; текст\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\; \backslash \; times\; \backslash \; Sigma\}$. Поскольку лексика конечна, ее можно указать, перечислив набор пар, например $ТИП\; ◃\; символ\; \{\backslash \; displaystyle\; TYPE\; \backslash \; треугольникleft\; \{\backslash \; text\; \{symbol\}\}\}$.

Такая грамматика для английского языка может иметь три основных типа $(N,\; NP\; и\; S)\; \{\backslash \; displaystyle\; (N,\; NP,\; \{\backslash \; text\; \{and\}\}\; S)\; \backslash ,\; \backslash !\}$, присваивая count существительным введите $N\; \{\backslash \; displaystyle\; N\; \backslash ,\; \backslash !\}$, завершите именные фразы типа $NP\; \{\backslash \; displaystyle\; NP\; \backslash ,\; \backslash !\}$и предложите тип $S\; \{\backslash \; Displaystyle\; S\; \backslash ,\; \backslash !\}$. Тогда прилагательное может иметь тип $N\; /\; N\; \{\backslash \; displaystyle\; N\; /\; N\; \backslash ,\; \backslash !\}$, потому что если за ним следует существительное, то вся фраза существительное. Точно так же определитель имеет тип $N\; P\; /\; N\; \{\backslash \; displaystyle\; NP\; /\; N\; \backslash ,\; \backslash !\}$, потому что он образует полную именную фразу, за которой следует существительное. Непереходные глаголы имеют тип $NP\; \setminus \; S\; \{\backslash \; displaystyle\; NP\; \backslash \; backslash\; S\}$, а переходные глаголы имеют тип $(NP\; \setminus \; S)\; /\; NP\; \{\backslash \; displaystyle\; (NP\; \backslash \; обратная\; косая\; черта\; S)\; /\; NP\}$. Тогда строка слов является предложением, если она имеет общий тип $S\; \{\backslash \; displaystyle\; S\; \backslash ,\; \backslash !\}$.

Например, возьмем строку «плохой мальчик сделал этот беспорядок». Теперь «the» и «that» являются определяющими, «мальчик» и «беспорядок» - существительные, «bad» - прилагательное, а «made» - переходный глагол, поэтому лексикон будет {$NP\; /\; N\; ◃\; \{\backslash \; displaystyle\; NP\; /\; N\; \backslash \; треугольникleft\; \{\backslash \; text\; \{the\}\}\}$, $NP\; /\; N\; ◃\; that\; \{\backslash \; displaystyle\; NP\; /\; N\; \backslash \; треугольникleft\; \{\backslash \; text\; \{that\}\}\}$, $N\; ◃\; мальчик\; \{\backslash \; displaystyle\; N\; \backslash \; треугольникleft\; \{\backslash \; текст\; \{мальчик\}\}\}$, $N\; ◃\; беспорядок\; \{\backslash \; displaystyle\; N\; \backslash \; треугольникleft\; \{\backslash \; text\; \{mess\}\}\}$, $N\; /\; N\; ◃\; плохо\; \{\backslash \; displaystyle\; N\; /\; N\; \backslash \; треугольникleft\; \{\backslash \; text\; \{\; bad\}\}\}$, $(NP\; \setminus \; S)\; /\; NP\; ◃\; made\; \{\backslash \; displaystyle\; (NP\; \backslash \; backslash\; S)\; /\; NP\; \backslash \; треугольникleft\; \{\backslash \; text\; \{made\}\}\}$}.

и последовательность типов в строке

$NP\; /\; N,\; плохой\; N\; /\; N,\; мальчик\; N,\; сделано\; (NP\; \setminus \; S)\; /\; NP,\; это\; NP\; /\; N,\; беспорядок\; N\; \{\backslash \; displaystyle\; \{\{\backslash \; text\; \{the\}\}\; \backslash \; atop\; \{NP\; /\; N,\}\}\; \{\{\backslash \; text\; \{bad\}\}\; \backslash \; atop\; \{N\; /\; N,\}\}\; \{\{\backslash \; text\; \{boy\}\}\; \backslash \; atop\; \{N,\}\}\; \{\; \{\backslash \; text\; \{made\}\}\; \backslash \; atop\; \{(NP\; \backslash \; backslash\; S)\; /\; NP,\}\}\; \{\{\backslash \; text\; \{that\}\}\; \backslash \; atop\; \{NP\; /\; N,\}\}\; \{\{\backslash \; text\; \{mess\}\}\; \backslash \; atop\; \{N\; \}\}\}$

теперь найдите функции и соответствующие аргументы и уменьшите их в соответствии с двумя правилами вывода $X\; \leftarrow \; X\; /\; Y,\; Y\; \{\backslash \; displaystyle\; X\; \backslash \; leftarrow\; X\; /\; Y,\; \backslash ;\; Y\; \}$и $X\; \leftarrow \; Y,\; Y\; \setminus \; X\; \{\backslash \; displaystyle\; X\; \backslash \; leftarrow\; Y,\; \backslash ;\; Y\; \backslash \; backslash\; X\}$:

$.\; NP\; /\; N,\; N\; /\; N,\; N,\; (NP\; \setminus \; S)\; /\; NP,\; NP\; /\; N,\; N\; ⏟\; \{\backslash \; displaystyle.\; \backslash \; Qquad\; NP\; /\; N,\; \backslash ;\; N\; /\; N,\; \backslash ;\; N,\; \backslash ;\; (NP\; \backslash \; обратная\; косая\; черта\; S)\; /\; NP,\; \backslash ;\; \backslash \; underbrace\; \{NP\; /\; N,\; \backslash ;\; N\}\}$. $.\; NP\; /\; N,\; N\; /\; N,\; N,\; (NP\; \setminus \; S)\; /\; NP,\; NP\; ⏟\; \{\backslash \; displaystyle.\; \backslash \; Qquad\; NP\; /\; N,\; \backslash ;\; N\; /\; N,\; \backslash ;\; N,\; \backslash ;\; \backslash \; underbrace\; \{(NP\; \backslash \; обратная\; косая\; черта\; S)\; /\; NP,\; \backslash \; quad\; NP\}\}$. $.\; NP\; /\; N,\; N\; /\; N,\; N\; ⏟,\; (NP\; \setminus \; S)\; \{\backslash \; Displaystyle.\; \backslash \; Qquad\; NP\; /\; N,\; \backslash ;\; \backslash \; underbrace\; \{N\; /\; N,\; \backslash ;\; N\},\; \backslash \; qquad\; (NP\; \backslash \; обратная\; косая\; черта\; S)\}$. $.\; N\; п\; /\; N,\; N\; ⏟,\; (N\; п\; \setminus \; S)\; \{\backslash \; displaystyle.\; \backslash \; Qquad\; \backslash \; underbrace\; \{NP\; /\; N,\; \backslash ;\; \backslash \; quad\; N\},\; \backslash ;\; \backslash \; qquad\; (NP\; \backslash \; backslash\; S)\}$. $.\; N\; п,\; (N\; п\; \setminus \; S)\; ⏟\; \{\backslash \; displaystyle.\; \backslash \; Qquad\; \backslash \; qquad\; \backslash \; underbrace\; \{NP,\; \backslash ;\; \backslash \; qquad\; (NP\; \backslash \; backslash\; S)\}\}$. $.\; S\; \{\backslash \; displaystyle.\; \backslash \; Qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; quad\; \backslash ;\; \backslash ;\; \backslash ;\; S\}$

Тот факт, что результат $S\; \{\backslash \; displaystyle\; S\; \backslash ,\; \backslash !\}$означает что строка является предложением, а последовательность сокращений показывает, что она должна быть проанализирована как (((плохой мальчик)) (сделал (тот беспорядок))).

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

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

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

Для исчисления Ламбека существует оператор конкатенации типов $\star \; \{\backslash \; displaystyle\; \backslash \; star\; \backslash ,\; \backslash !\}$, так что $Prim\; \subseteq \; Tp\; (Prim)\; \{\; \backslash \; displaystyle\; \{\backslash \; text\; \{Prim\}\}\; \backslash \; substeq\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\}$и если $X,\; Y\; \in \; Tp\; (Prim)\; \{\backslash \; displaystyle\; X,\; Y\; \backslash \; in\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\}$, затем $(X\; /\; Y),\; (X\; \setminus \; Y),\; (X\; \star \; Y)\; \in \; Tp\; (Prim)\; \{\backslash \; displaystyle\; (X\; /\; Y),\; (X\; \backslash \; backslash\; Y),\; (X\; \backslash \; star\; Y)\; \backslash \; in\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\}$.

Ламбек исчисление состоит из нескольких правил вывода, которые определяют, как утверждения включения типов могут быть получены. В следующих правилах заглавные латинские буквы обозначают типы, а прописные греческие буквы - последовательность типов. Последовательность вида $X\; \leftarrow \; \Gamma \; \{\backslash \; displaystyle\; X\; \backslash \; leftarrow\; \backslash \; Gamma\}$может быть прочитана: строка имеет тип $X\; \{\backslash \; displaystyle\; X\; \backslash ,\; \backslash !\}$, если он состоит из конкатенации строк каждого из типов в $\Gamma \; \{\backslash \; displaystyle\; \backslash \; Gamma\; \backslash ,\; \backslash !\}$. Если тип интерпретируется как набор строк, то $\leftarrow \; \{\backslash \; displaystyle\; \backslash \; leftarrow\}$может интерпретироваться как $\supseteq \; \{\backslash \; displaystyle\; \backslash \; supseteq\; \backslash ,\; \backslash !\}$, то есть «включает как подмножество». Горизонтальная линия означает, что включение выше линии подразумевает включение ниже линии.

Процесс начинается с правила Аксиомы, которое не имеет антецедентов и просто говорит, что любой тип включает себя.

$(A\; x\; i\; o\; m)\; X\; \leftarrow \; X\; \{\backslash \; displaystyle\; (Axiom)\; \backslash \; quad\; \{\{\}\; \backslash \; over\; X\; \backslash \; leftarrow\; X\}\}$

Правило Cut гласит, что включения могут быть составлены.

$(C\; ut)\; Z\; \leftarrow \; \Delta \; Икс\; \Delta \; \prime \; X\; \leftarrow \; \Gamma \; Z\; \leftarrow \; \Delta \; \Gamma \; \Delta \; \prime \; \{\backslash \; displaystyle\; (Cut)\; \backslash \; quad\; \{Z\; \backslash \; leftarrow\; \backslash \; Delta\; X\; \backslash \; Delta\; \text{'}\backslash \; qquad\; X\; \backslash \; leftarrow\; \backslash \; Gamma\; \backslash \; over\; Z\; \backslash \; leftarrow\; \backslash \; Delta\; \backslash \; Gamma\; \backslash \; Delta\; \text{'}\}\}$

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

Цель	Источник
$(\setminus \; \leftarrow )\; Y\; \leftarrow \; X\; \Gamma \; X\; \setminus \; Y\; \leftarrow \; \Gamma \; \{\backslash \; displaystyle\; (\backslash \; backslash\; \backslash \; leftarrow)\; \backslash \; quad\; \{Y\; \backslash \; leftarrow\; X\; \backslash \; Gamma\; \backslash \; over\; X\; \backslash \; backslash\; Y\; \backslash \; leftarrow\; \backslash \; Gamma\}\}$	$(\leftarrow \; \setminus )\; Z\; \leftarrow \; \Delta \; Y\; \Delta \; \prime \; X\; \leftarrow \; \Gamma \; Z\; \leftarrow \; \Delta \; \Gamma \; (X\; \setminus \; Y)\; \Delta \; \prime \; \{\backslash \; displaystyle\; (\backslash \; leftarrow\; \backslash \; backslash)\; \backslash \; quad\; \{Z\; \backslash \; leftarrow\; \backslash \; Delta\; Y\; \backslash \; Delta\; \text{'}\backslash \; qquad\; X\; \backslash \; leftarrow\; \backslash \; Gamma\; \backslash \; over\; Z\; \backslash \; leftarrow\; \backslash \; Delta\; \backslash \; Gamma\; (X\; \backslash \; backslash\; Y)\; \backslash \; Delta\text{'}\}\}$
$(/\; \leftarrow )\; Y\; \leftarrow \; \Gamma \; XY\; /\; X\; \leftarrow \; \Gamma \; \{\backslash \; displaystyle\; (/\; \backslash \; leftarrow)\; \backslash \; quad\; \{Y\; \backslash \; leftarrow\; \backslash \; Gamma\; X\; \backslash \; over\; Y\; /\; X\; \backslash \; leftarrow\; \backslash \; Gamma\}\}$	$(\leftarrow \; /)\; Z\; \leftarrow \; \Delta \; Y\; \Delta \; \prime \; X\; \leftarrow \; \Gamma \; Z\; \leftarrow \; \Delta \; (Y\; /\; X)\; \Gamma \; \Delta \; \prime \; \{\backslash \; displaystyle\; (\backslash \; leftarrow\; /)\; \backslash \; quad\; \{Z\; \backslash \; leftarrow\; \backslash \; Delta\; Y\; \backslash \; Delta\; \text{'}\backslash \; qquad\; X\; \backslash \; leftarrow\; \backslash \; Gamma\; \backslash \; over\; Z\; \backslash \; leftarrow\; \backslash \; Delta\; (Y\; /\; X)\; \backslash \; Gamma\; \backslash \; Delta\text{'}\}\}$
$(\star \; \leftarrow )\; Икс\; \leftarrow \; \Gamma \; Y\; \leftarrow \; \Gamma \; \prime \; X\; \star \; Y\; \leftarrow \; \Gamma \; \Gamma \; \prime \; \{\backslash \; displaystyle\; (\backslash \; star\; \backslash \; leftarrow)\; \backslash \; quad\; \{X\; \backslash \; leftarrow\; \backslash \; Gamma\; \backslash \; qquad\; Y\; \backslash \; leftarrow\; \backslash \; Gamma\; \text{'}\backslash \; over\; X\; \backslash \; star\; Y\; \backslash \; leftarrow\; \backslash \; Gamma\; \backslash \; Gamma\; \text{'}\}\}$	$(\leftarrow \; \star )\; Z\; \leftarrow \; \Delta \; XY\; \Delta \; \prime \; Z\; \leftarrow \; \Delta \; (X\; \star \; Y)\; \Delta \; \prime \; \{\backslash \; displaystyle\; (\backslash \; leftarrow\; \backslash \; star)\; \backslash \; quad\; \{Z\; \backslash \; leftarrow\; \backslash \; Delta\; XY\; \backslash \; Delta\; \text{'}\backslash \; over\; Z\; \backslash \; leftarrow\; \backslash \; Delta\; (X\; \backslash \; star\; Y)\; \backslash \; Delta\; \text{'}\}\}$

Например, вот вывод от «повышения типа», который говорит, что $(B\; /\; A)\; \setminus \; B\; \leftarrow \; A\; \{\backslash \; displaystyle\; (B\; /\; A)\; \backslash \; обратная\; косая\; черта\; B\; \backslash \; leftarrow\; A\}$. Справа указаны названия правил и используемые замены.

$B\; \leftarrow \; BA\; \leftarrow \; AB\; \leftarrow \; (B\; /\; A),\; A\; (B\; /\; A)\; \setminus \; B\; \leftarrow \; A\; (Аксиомы)\; (\leftarrow \; /)\; [Z\; =\; Y\; =\; B,\; X\; =\; A,\; \Gamma \; =\; (A),\; \Delta \; Знак\; равно\; \Delta \; \prime \; =\; ()]\; (\setminus \; \leftarrow )\; [Y\; =\; B,\; X\; =\; (B\; /\; A),\; \Gamma \; =\; (A)]\; \{\backslash \; displaystyle\; \{\backslash \; dfrac\; \{\{\backslash \; dfrac\; \{\}\; \{B\; \backslash \; leftarrow\; B\}\}\; \backslash \; qquad\; \{\backslash \; dfrac\; \{\}\; \{A\; \backslash \; leftarrow\; A\}\}\}\; \{\backslash \; dfrac\; \{B\; \backslash \; leftarrow\; (B\; /\; A),\; \backslash ;\; \backslash ;\; A\}\; \{(B\; /\; A)\; \backslash \; backslash\; B\; \backslash \; leftarrow\; A\}\}\}\; \backslash \; qquad\; \{\backslash \; begin\; \{matrix\}\; \{\backslash \; t\_dv\; \{(Axioms)\}\}\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \{\}\; \backslash \backslash \; \{(\backslash \; leftarrow\; /)\; \backslash ,\; \backslash ,\; [Z\; =\; Y\; =\; B,\; X\; =\; A,\; \backslash \; Gamma\; =\; (A),\; \backslash \; Delta\; =\; \backslash \; Delta\; \text{'}=\; ()]\}\; \backslash \backslash \; \{(\backslash \; backslash\; \backslash \; leftarrow)\; \backslash ,\; \backslash ,\; [Y\; =\; B,\; X\; =\; (B\; /\; A),\; \backslash \; Gamma\; =\; (A)]\}\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \{\}\; \backslash \backslash \backslash \; end\; \{matrix\}\}\}$

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

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

$G\; =\; (V,\; \Sigma ,\; ::\; =,\; S)\; \{\backslash \; displaystyle\; G\; =\; (V,\; \backslash ,\; \backslash \; Sigma,\; \backslash ,\; ::\; =,\; \backslash ,\; S)\; \}$где

1. $V\; \{\backslash \; displaystyle\; V\; \backslash ,\}$- конечный набор нетерминалов или переменных.

2. $\Sigma \; \{\backslash \; displaystyle\; \backslash \; Sigma\; \backslash ,\}$- конечный набор терминальных символов.

3. $::\; =\; \{\backslash \; displaystyle\; ::\; =\; \backslash ,\}$- конечный набор производственных правил, то есть конечное отношение $(::\; =)\; \subseteq \; V\; \times \; (V\; \cup \; \Sigma )\; \ast \; \{\backslash \; displaystyle\; (::\; =)\; \backslash \; substeq\; V\; \backslash \; times\; (V\; \backslash \; cup\; \backslash \; Sigma)\; ^\; \{*\}\}$.

4. $S\; \{\backslash \; displaystyle\; S\; \backslash ,\}$- начальная переменная.

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

В частности, учитывая неконтекстную грамматику, как указано выше, определите категориальную грамматику $(Prim,\; \Sigma ,\; ◃,\; S)\; \{\backslash \; displaystyle\; (\{\backslash \; text\; \{Prim\}\},\; \backslash ,\; \backslash \; Sigma,\; \backslash ,\; \backslash \; треугольникleft,\; \backslash ,\; S)\}$где $Prim\; =\; V\; \cup \; \Sigma \; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Prim\}\}\; =\; V\; \backslash \; cup\; \backslash \; Sigma\}$, и $Tp\; (Prim)\; =\; Prim\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Tp\}\}\; (\{\backslash \; text\; \{Prim\}\})\; =\; \{\backslash \; text\; \{Prim\}\}\; \backslash ,\; \backslash !\}$. Пусть существует аксиома $x\; \leftarrow \; x\; \{\backslash \; displaystyle\; \{x\; \backslash \; leftarrow\; x\}\}$для каждого символа $x\; \in \; V\; \cup \; \Sigma \; \{\backslash \; displaystyle\; x\; \backslash \; in\; V\; \backslash \; cup\; \backslash \; Sigma\}$, аксиома $X\; \leftarrow \; \Gamma \; \{\backslash \; displaystyle\; \{X\; \backslash \; leftarrow\; \backslash \; Gamma\}\}$для каждого производственного правила $X\; ::\; =\; \Gamma \; \{\backslash \; displaystyle\; X\; ::\; =\; \backslash \; Gamma\; \backslash ,\; \backslash !\}$, словарная статья $s\; ◃\; s\; \{\backslash \; displaystyle\; \{s\; \backslash \; треугольникleft\; s\}\}$для каждого терминального символа $s\; \in \; \Sigma \; \{\backslash \; displaystyle\; s\; \backslash \; in\; \backslash \; Sigma\}$и Cut для единственного правила. Эта категориальная грамматика генерирует тот же язык, что и данный CFG.

Конечно, это не базовая категориальная грамматика, поскольку в ней есть особые аксиомы, которые зависят от языка; т.е. не лексикализован. Кроме того, он вообще не использует непримитивные типы.

Чтобы показать, что любой контекстно-свободный язык можно сгенерировать с помощью базовой категориальной грамматики, вспомним, что любой контекстно-свободный язык может быть сгенерирован с помощью контекстно-свободной грамматики в нормальной форме Грейбаха.

грамматика находится в нормальной форме Грейбаха, если каждое продукционное правило имеет вид $A\; ::\; =\; s\; A\; 0\dots \; AN\; -\; 1\; \{\backslash \; displaystyle\; A\; ::\; =\; sA\_\; \{0\}\; \backslash \; ldots\; A\_\; \{N-1\}\}$, где заглавные буквы - переменные, $s\; \in \; \Sigma \; \{\backslash \; displaystyle\; s\; \backslash \; in\; \backslash \; Sigma\}$и $N\; \ge \; 0\; \{\backslash \; displaystyle\; N\; \backslash \; geq\; 0\}$, то есть правая часть продукции представляет собой один конечный символ, за которым следует ноль или более (нетерминальных) переменных.

Теперь, имея CFG в нормальной форме Грейбаха, определите базовую категориальную грамматику с примитивным типом для каждой нетерминальной переменной $Prim\; =\; V\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Prim\}\}\; =\; V\; \backslash ,\; \backslash !\}$, и с записью в лексиконе $A\; /\; AN\; -\; 1\; /\dots \; /\; A\; 0\; ◃\; s\; \{\backslash \; displaystyle\; A\; /\; A\_\; \{N-1\}\; /\; \backslash \; ldots\; /\; A\_\; \{0\; \}\; \backslash \; треугольникleft\; s\}$, для каждого производственного правила $A\; ::\; =\; s\; A\; 0\dots \; AN\; -\; 1\; \{\backslash \; displaystyle\; A\; ::\; =\; sA\_\; \{0\}\; \backslash \; ldots\; A\_\; \{N-1\}\}$. Довольно легко увидеть, что эта базовая категориальная грамматика генерирует тот же язык, что и исходный CFG. Обратите внимание, что лексика этой грамматики обычно присваивает несколько типов каждому символу.

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

Показать обратное, что каждый язык, созданный грамматикой Ламбека, является контекстно-независимым, намного сложнее. Это была открытая проблема в течение почти тридцати лет, с начала 1960-х годов до примерно 1991 года, когда это было доказано Пентусом.

Основная идея с учетом грамматики Ламбека: $(Prim,\; \Sigma ,\; ◃,\; S)\; \{\backslash \; displaystyle\; (\{\backslash \; text\; \{Prim\}\},\; \backslash ,\; \backslash \; Sigma,\; \backslash ,\; \backslash \; треугольникleft,\; \backslash ,\; S)\}$построить контекстно-свободную грамматику $(V,\; \Sigma ,\; ::\; =,\; S)\; \{\backslash \; displaystyle\; (V,\; \backslash ,\; \backslash \; Sigma,\; \backslash ,\; ::\; =,\; \backslash ,\; S)\}$с тем же набором терминальных символов, тем же начальным символом, с переменными некоторых (не всех) типов $V\; \subset \; Tp\; (Prim)\; \{\backslash \; displaystyle\; V\; \backslash \; subset\; \{\backslash \; text\; \{Tp\; \}\}\; (\{\backslash \; text\; \{Prim\}\})\; \backslash ,\; \backslash !\}$и с производственным правилом $T\; ::\; =\; s\; \{\backslash \; displaystyle\; T\; ::\; =\; \{\backslash \; text\; \{s\}\}\; \backslash ,\; \backslash !\}$для каждой записи $T\; ◃\; s\; \{\backslash \; displaystyle\; T\; \backslash \; треугольникleft\; \{\backslash \; text\; \{s\}\}\}$в лексиконе и производственных правил $T\; ::\; =\; \Gamma \; \{\backslash \; displaystyle\; T\; ::\; =\; \backslash \; Gamma\; \backslash ,\; \backslash !\}$для определенных секвенций $T\; \leftarrow \; \Gamma \; \{\backslash \; displaystyle\; T\; \backslash \; leftarrow\; \backslash \; Gamma\}$, которые выводимы в исчислении Ламбека.

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

Обозначение

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

В логике стрелки обычно указывают слева направо. В этой статье это соглашение изменено на обратное для согласования с обозначением контекстно-свободных грамматик, где единственный нетерминальный символ всегда находится слева. Мы используем символ $::\; =\; \{\backslash \; displaystyle\; ::\; =\}$в производственном правиле, как в форме Бэкуса-Наура. Некоторые авторы используют стрелку, которая, к сожалению, может указывать в любом направлении, в зависимости от того, считается ли грамматика генерирующей или распознающей язык.

Некоторые авторы категориальных грамматик пишут $B\; \setminus \; A\; \{\backslash \; displaystyle\; B\; \backslash \; backslash\; A\}$вместо $A\; \setminus \; B\; \{\backslash \; displaystyle\; A\; \backslash \; backslash\; B\}$. Используемое здесь соглашение следует Ламбеку и алгебре.

Основные идеи категориальной грамматики восходят к работе Казимежа Айдукевича (в 1935 году) и Иегошуа Бар-Гилеля (в 1953 году).). В 1958 году Иоахим Ламбек представил синтаксическое исчисление, которое формализовало конструкторы типа function вместе с различными правилами для комбинирования функций. Это исчисление является предшественником линейной логики в том смысле, что это субструктурная логика. Грамматика Монтегю использует специальную синтаксическую систему для английского языка, основанную на принципах категориальной грамматики. Хотя работа Монтегю иногда считается синтаксически неинтересной, она помогла поддержать интерес к категориальной грамматике, связав ее с очень успешной формальной обработкой семантики естественного языка . Недавние исследования категориальной грамматики были сосредоточены на улучшении синтаксического охвата. Одним из формализмов, который привлек значительное внимание в последние годы, является Стидман и Сабольчи комбинаторно-категориальная грамматика, основанная на комбинаторной логике, изобретенная Моисей Шёнфинкель и Хаскелл Карри.

В лингвистике существует ряд связанных формализмов такого рода, например и.

Деривация

Деривация - это двоичное дерево, которое кодирует доказательство.

Дерево синтаксического анализа

Дерево синтаксического анализа отображает производное, показывающая синтаксическую структуру предложения.

Функтор и аргумент

В приложении правой (левой) функции узел типа A \ B (B / A) называется функтором, а узел типа A называется аргументом.

Функтор – структура аргумента

Для улучшения синтаксического покрытия было предложено множество изменений категориальной грамматики. Некоторые из наиболее распространенных из них перечислены ниже.

Функции и подкатегории

Большинство систем категориальной грамматики подразделяют категории. Наиболее распространенный способ сделать это - пометить их тегами функций, например человек, пол, число и . напряженный. Иногда таким образом помечаются только атомарные категории. В грамматике Монтегю традиционно разделяют категории функций с помощью соглашения о множественных косых чертах, поэтому A / B и A // B будут двумя разными категориями функций, применяемых слева, которые принимают одни и те же аргументы, но могут различаться другими функциями. принимая их как аргументы.

Функциональная композиция

Правила функциональной композиции включены во многие категориальные грамматики. Примером такого правила может быть правило, позволяющее объединить компонент типа A / B с одним из типов B / C, чтобы создать новый компонент типа A / C. Семантика такого правила будет просто включать состав задействованных функций. Функциональная композиция важна в категориальных отчетах о соединении и извлечении, особенно в связи с такими явлениями, как подъем правого узла. Введение функциональной композиции в категориальную грамматику приводит ко многим видам деривационной двусмысленности, которые бессмысленны в том смысле, что они не соответствуют семантическим двусмысленностям.

Конъюнкция

Многие категориальные грамматики включают типичное конъюнкцию правило общего вида X CONJ X → X, где X - категория. Конъюнкция обычно может применяться к нестандартным составляющим, возникающим в результате повышения типа или композиции функций.

Разрыв

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

• Комбинаторная категориальная грамматика
• Некоммутативная логика
• Pregroup Grammar
• Link грамматика

• Curry, Haskell B. ; Ричард Фейс (1958), Combinatory Logic, 1, North-Holland
• Jacobson, Pauline (1999), «На пути к семантике без переменных», Linguistics and Philosophy, 22 (2): 117–184, doi : 10.1023 / A: 1005464228727, S2CID 60578091
• Ламбек, Иоахим (1958), «Математика структуры предложения», амер. Математика. Ежемесячно, 65(3): 154–170, CiteSeerX 10.1.1.538.885, doi : 10.1080 / 00029890.1958.11989160
• Пентус, Мати (1997), Исчисление Ламбека и формальные грамматики (PDF), Amer. Математика. Soc. Перевод
• Стидман, Марк (1987), «Комбинаторные грамматики и паразитические пробелы», Natural Language and Linguistic Theory, 5 (3): 403–439, doi : 10.1007 / bf00134555, S2CID 170899264
• Стидман, Марк (1996), Структура поверхности и интерпретация, The MIT Press
• Стидман, Марк (2000), Синтаксический процесс, The MIT Press
• Сабольчи, Анна (1989). «Связанные переменные в синтаксисе (есть ли?)» (PDF). В Барче; ван Бентем; ван Эмде Боас (ред.). Семантика и контекстное выражение. Форис. С. 294–318.
• Сабольчи, Анна (1992). «Комбинаторная грамматика и проекция из лексикона» (PDF). В Sag; Сабольчи (ред.). Лексические вопросы. Лекционные заметки CSLI. 24 . Стэнфорд: публикации CSLI. стр. 241–269.
• Сабольчи, Анна (2003), «Связывание на лету: перекрестно-смысловая анафора в семантике без переменных», в Kruijff; Oehrle (ред.), Resource Sensitivity in Binding and Anaphora, Studies in Linguistics and Philosophy, 80, Kluwer, pp. 215–229, CiteSeerX 10.1.1.205.3142, doi : 10.1007 / 978-94-010-0037-6_8, ISBN 978-1-4020-1692-9
• Моррил, Глин (1995), «Непрерывность в категориальной грамматике», Лингвистика и философия, 18 (2): 175–219, doi : 10.1007 / bf00985216, S2CID 62533943

• Майкл Мортгат, Логика категориального типа, глава 2 в книге Дж. Ван Бентема и А. тер Мейлена (ред.) Справочник по логике и языку. Elsevier, 1997, ISBN 0-262-22053-9
• Войцех Бушковский, Математическая лингвистика и теория доказательств, Глава 12 в J. van Benthem и A. ter Meulen (ред..) Справочник по логике и языку. Эльзевир, 1997, ISBN 0-262-22053-9
• Герхард Ягер (2005). Анафора и типовая логическая грамматика. Springer. ISBN 978-1-4020-3904-1.
• Глин Моррилл (2010). Категориальная грамматика: логический синтаксис, семантика и обработка. Издательство Оксфордского университета. ISBN 978-0-19-958986-9.
• Ричард Мут; Кристиан Реторе (2012). Логика категориальных грамматик: дедуктивный учет синтаксиса и семантики естественного языка. Springer Verlag. ISBN 978-3-642-31554-1.

• Грамматика, категориальная в Springer Энциклопедия математики
• http: // plato. stanford.edu/entries/typelogical-grammar/