Слегка контекстно-зависимый грамматический формализм

В компьютерной лингвистике термин « мягко контекстно-зависимые грамматические формализмы» относится к нескольким грамматическим формализмам , которые были разработаны с целью обеспечить адекватное описание структуры синтаксической естественного языка .

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

Фон

К 1985 году несколько исследователей в области описательной и математической лингвистики представили доказательства против гипотезы о том, что синтаксическая структура естественного языка может быть адекватно описана с помощью контекстно-свободных грамматик . ^[1]^[2]В то же время переход на следующий уровень иерархии Хомского , к контекстно-зависимым грамматикам , оказался одновременно и ненужным, и нежелательным.Пытаясь определить точную формальную силу, необходимую для адекватного описания синтаксиса естественного языка, Аравинд Джоши охарактеризовал «грамматики (и связанные с ними языки ), которые лишь немного более мощны, чем контекстно-свободные грамматики (контекстно-свободные языки)». ^[3]Он назвал эти грамматики умеренно контекстно-зависимыми грамматиками , а связанные с ними языки — умеренно контекстно-зависимыми языками .

Характеристика Джоши слегка контекстно-зависимых грамматик была смещена в сторону его работы над грамматикой, примыкающей к дереву (TAG).Однако вместе со своими учениками Виджаем Шанкером и Дэвидом Вейром Джоши вскоре обнаружил, что TAG эквивалентны с точки зрения сгенерированных строковых языков независимо введенной головной грамматике (HG). ^[4]За этим последовали два аналогичных результата эквивалентности для линейной индексированной грамматики (LIG). ^[5] и комбинаторная категориальная грамматика (CCG), ^[6] который показал, что понятие умеренной контекстной чувствительности является очень общим и не привязано к конкретному формализму.

TAG-эквивалентные формализмы были обобщены путем введения линейных систем контекстно-свободной перезаписи (LCFRS). ^[7]^[8]Эти грамматики определяют бесконечную иерархию строковых языков между контекстно-свободными и контекстно-зависимыми языками, причем языки, созданные с помощью TAG-эквивалентных формализмов, находятся на нижнем конце. ^{[ нужны разъяснения ]} иерархии.Независимо и почти одновременно с LCFRS, Hiroyuki Seki et al. предложил по существу идентичный формализм множественной контекстно-свободной грамматики (MCFG). ^[9]LCFRS/MCFG иногда рассматривается как наиболее общий формализм для определения слегка контекстно-зависимых грамматик.Однако некоторые авторы отметили, что некоторые характерные свойства TAG-эквивалентных формализмов не сохраняются LCFRS/MCFG, ^[10] и что существуют языки, которые имеют характерные свойства легкой контекстно-зависимости, но не генерируются LCFRS/MCFG. ^[11]

В последние годы возрос интерес к ограниченному классу хорошо вложенных линейных контекстно-свободных систем переписывания/множественных контекстно-свободных грамматик. ^[10]^[12] которые определяют класс грамматик, который должным образом включает в себя формализмы, эквивалентные TAG, но должным образом включен в неограниченную иерархию LCFRS/MCFG.

Характеристика

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

Согласно оригинальной характеристике Джоши, ^[3] класс слабо контекстно-зависимых грамматик должен иметь следующие свойства:

ограниченные межсерийные зависимости
постоянный рост
полиномиальный анализ

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

Характеристика Джоши не является формальным определением. Он отмечает: ^[3]

Это лишь приблизительная характеристика, поскольку условия 1 и 3 зависят от грамматик, а условие 2 — от языков; далее, условие 1 нужно указать гораздо точнее, чем я это делал до сих пор.

Другие авторы предложили альтернативные характеристики легкой контекстной чувствительности, некоторые из которых принимают форму формальных определений.Например, Лаура Каллмейер ^[13] придерживается точки зрения, согласно которой умеренную контекстную чувствительность следует определять как свойство классов языков, а не, как в характеристике Джоши, классов грамматик.Такое языковое определение приводит к иному пониманию концепции, чем у Джоши.

Межсерийные зависимости

Термин «перекрестные зависимости» относится к определенным характерным моделям порядка слов, в частности к моделям глагола и аргумента, наблюдаемым в придаточных предложениях в голландском языке. ^[1] и швейцарский немецкий. ^[2]Это те самые закономерности, которые можно использовать для аргументации против контекстно-свободного языка естественного языка; таким образом, требование слегка контекстно-зависимых грамматик для моделирования межпоследовательных зависимостей означает, что эти грамматики должны быть более мощными, чем контекстно-свободные грамматики.

Кальмейер ^[13] определяет способность моделировать межпоследовательные зависимости с возможностью генерировать язык копирования

${\mathit {COPY}}=\{\,ww\mid w\in \{a,b\}^{*}\,\}$

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

Постоянный рост

Формальный язык имеет постоянный рост , если каждая строка в языке длиннее следующих более коротких строк не более чем на константу (специфичную для языка).Языки, нарушающие это свойство, часто считаются выходящими за пределы человеческих возможностей, хотя некоторые авторы утверждают, что некоторые явления в естественном языке действительно демонстрируют рост, который не может быть ограничен константой. ^[14]

Наиболее слабо контекстно-зависимые грамматические формализмы (в частности, LCFRS/MCFG) на самом деле удовлетворяют более сильному свойству, чем постоянный рост, называемому полулинейностью . ^[7]Язык является полулинейным, если его образ при отображении Париха (отображении, которое «забывает» относительное положение символов в строке, фактически рассматривая его как набор слов) является регулярным языком .Все полулинейные языки имеют постоянный рост, но не каждый язык с постоянным ростом является полулинейным. ^[11]

Полиномиальный анализ

Говорят, что грамматический формализм имеет полиномиальный анализ , если его проблема принадлежности может быть решена за детерминированное полиномиальное время .Это проблема, которую необходимо решить, учитывая грамматику , написанную в этом формализме, и строку w , ли w порождена G , то есть является ли w «грамматической» согласно G. G Временная сложность этой проблемы измеряется совокупным размером G и w .

С точки зрения умеренной контекстной чувствительности как свойства классов языков, полиномиальный синтаксический анализ относится к проблеме принадлежности языка.Это проблема, чтобы решить для фиксированного языка L ли данная строка w , принадлежит L. языку Временная сложность этой задачи измеряется длиной w ; он игнорирует вопрос, как L. указывается

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

Формализмы

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

Формализмы, эквивалентные TAG

Древовидная грамматика (TAG) ^[3]
Головная грамматика (HG) ^[15]^[16]
Линейно-индексированная грамматика (LIG) ^[17]
Комбинаторная категориальная грамматика (CCG) ^[6]
Хорошо вложенная LCFRS/MCFG разветвления 2

Формализмы, эквивалентные общему LCFRS/MCFG

Линейные системы контекстно-свободной перезаписи (LCFRS) ^[7]^[8]
Множественные контекстно-свободные грамматики (MCFG) ^[9]
Многокомпонентные древовидные грамматики (MCTAG) ^[7]
Минималистские грамматики (МГ) ^[18]
Простые (линейные, нестираемые, некомбинаторные) грамматики конкатенации положительного диапазона (sRCG) ^[19]

Формализмы, эквивалентные хорошо вложенному LCFRS/MCFG

Недублирующиеся макрограмматики ^[20]
Связанные контекстно-свободные грамматики (CCFG) ^[21]
Хорошо вложенные линейные контекстно-свободные системы переписывания ^[12]
Хорошо вложенные множественные контекстно-свободные грамматики ^[10]

Отношения между формализмами

Линейные бесконтекстные системы переписывания/множественные контекстно-свободные грамматики образуют двумерную иерархию порождающей силы по отношению к двум специфичным для грамматики параметрам, называемым разветвлением и рангом . ^[22]Точнее, языки, порожденные LCFRS/MCFG с разветвлением $f \geq 1$ и рангом $r \geq 3,$ правильно включаются в класс языков, порожденных LCFRS/MCFG с рангом $r + 1$ и разветвлением f , а также класс языков, порожденный LCFRS/MCFG с рангом r и разветвлением $f + 1$ .При наличии хорошей вложенности эта иерархия схлопывается до одномерной иерархии относительно разветвления; это связано с тем, что каждый LCFRS/MCFG с хорошей вложенностью можно преобразовать в эквивалентный LCFRS/MCFG с хорошим вложением с тем же разветвлением и рангом 2. ^[10]^[12]В иерархии LCFRS/MCFG контекстно-свободные языки могут быть охарактеризованы грамматиками с разветвлением 1; для этого разветвления нет разницы между общей и хорошо вложенной грамматикой.TAG-эквивалентные формализмы можно охарактеризовать как хорошо вложенные LCFRS/MCFG с разветвлением 2.

См. также

Ссылки

^ Jump up to: ^а ^б Рини Хайбрегтс. «Слабая неадекватность грамматик бесконтекстной фразовой структуры». Гер де Хаан, Мике Троммелен и Вим Зонневельд, редакторы, «От периферии к ядру» , страницы 81–99. Форис, Дордрехт, Нидерланды, 1984 г.
^ Jump up to: ^а ^б Стюарт М. Шибер. « Свидетельства против контекстной свободы естественного языка ». Лингвистика и философия , 8 (3): 333–343, 1985.
^ Jump up to: ^а ^б ^с ^д Аравинд К. Джоши. « Грамматики, примыкающие к дереву: какая контекстная чувствительность необходима для обеспечения разумных структурных описаний? ». Дэвид Р. Даути, Лаури Карттунен и Арнольд М. Цвикки, редакторы журнала « Разбор естественного языка» , страницы 206–250. Издательство Кембриджского университета, 1985.
^ Дэвид Дж. Вейр, К. Виджай-Шанкер и Аравинд К. Джоши. « Взаимосвязь между грамматиками, примыкающими к дереву, и головными грамматиками ». В материалах 24-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 67–74, Нью-Йорк, США, 1986.
^ К. Виджай-Шанкер. « Исследование грамматик, прилегающих к деревьям ». доктор философии диссертация, Пенсильванский университет, Филадельфия, США, 1987 г.
^ Jump up to: ^а ^б Дэвид Дж. Вейр и Аравинд К. Джоши. « Комбинаторные категориальные грамматики: порождающая сила и связь с линейными бесконтекстными системами переписывания ». В материалах 26-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 278–285, Буффало, США, 1988.
^ Jump up to: ^а ^б ^с ^д К. Виджай-Шанкер, Дэвид Дж. Вейр и Аравинд К. Джоши. « Характеристика структурных описаний, созданных с помощью различных грамматических формализмов ». В материалах 25-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 104–111, Стэнфорд, Калифорния, США, 1987.
^ Jump up to: ^а ^б Дэвид Дж. Вейр. « Характеристика умеренно контекстно-зависимых грамматических формализмов ». доктор философии диссертация, Пенсильванский университет, Филадельфия, США, 1988 г.
^ Jump up to: ^а ^б Хироюки Секи, Такаси Мацумура, Мамору Фуджи и Тадао Касами. « О множественных контекстно-свободных грамматиках ». Теоретическая информатика , 88(2):191–229, 1991.
^ Jump up to: ^а ^б ^с ^д Макото Канадзава. « Лемма о накачке для нескольких хорошо вложенных контекстно-свободных языков ». В разделе «Развития теории языка». 13-я Международная конференция DLT 2009, Штутгарт, Германия, 30 июня – 3 июля 2009 г. Труды , том 5583 конспектов лекций по информатике , страницы 312–325, 2009 г.
^ Jump up to: ^а ^б Лаура Каллмейер. « О мягком контекстно-зависимом нелинейном переписывании ». Исследования языка и вычислений , 8(4):341–363, 2010.
^ Jump up to: ^а ^б ^с Карлос Гомес-Родригес, Марко Кульманн и Джорджио Сатта. « Эффективный анализ хорошо вложенных линейных контекстно-свободных систем переписывания ». В материалах по технологиям человеческого языка: Ежегодная конференция Североамериканского отделения Ассоциации компьютерной лингвистики (NAACL) 2010 г. , страницы 276–284, Лос-Анджелес, США, 2010 г.
^ Jump up to: ^а ^б Лаура Каллмейер. Синтаксический анализ за пределами контекстно-свободных грамматик . Спрингер, 2010.
^ Йенс Михаэлис и Маркус Крахт. « Полулинейность как синтаксический инвариант ». В логических аспектах компьютерной лингвистики. Первая международная конференция, LACL 1996, Нанси, Франция, 23–25 сентября 1996 г. Избранные статьи , том 1328 конспектов лекций по информатике , страницы 329–345. Спрингер, 1997.
^ Карл Дж. Поллард . «Обобщенные грамматики фразовой структуры, главные грамматики и естественный язык». доктор философии диссертация, Стэнфордский университет, 1984 г.
^ Келли Роуч. « Формальные свойства головных грамматик ». Алексис Манастер-Рамер, редактор журнала «Математика языка» , страницы 293–347. Джон Бенджаминс, 1987 год.
^ Джеральд Газдар. « Применимость индексированных грамматик к естественному языку ». В книге Уве Рейле и Кристиана Рорера, редакторов, «Разбор естественного языка и лингвистические теории» , страницы 69–94. Д. Рейдель, 1987.
^ Йенс Михаэлис. « Деривационный минимализм слегка контекстно-зависим ». В «Логических аспектах компьютерной лингвистики», Третья международная конференция, LACL 1998, Гренобль, Франция, 14–16 декабря 1998 г., Избранные статьи , том 2014 г. Конспектов лекций по информатике , страницы 179–198. Спрингер, 1998.
^ Пьер Булье. « Грамматики конкатенации диапазонов ». В Гарри К. Бунте, Джоне Кэрролле и Джорджио Сатте, редакторах, « Новые разработки в технологии синтаксического анализа» , том 23 журнала «Текст, речь и языковые технологии» , страницы 269–289. Издательство Kluwer Academic, 2004.
^ Майкл Дж. Фишер. « Грамматики с макроподобными постановками ». На девятом ежегодном симпозиуме по теории коммутации и автоматов , страницы 131–142, Скенектади, Нью-Йорк, США, 1968.
^ Гюнтер Хотц и Гизела Питч. «О синтаксическом анализе связанных контекстно-свободных языков». Теоретическая информатика , 161(1–2):205–233, 1996.
^ Оуэн Рэмбоу и Джорджио Сатта. « Двумерная иерархия для систем параллельной перезаписи ». Технический отчет IRCS-94-02, Пенсильванский университет, Филадельфия, США, 1994 г.

[huybregts1984-1] Jump up to: ^а ^б Рини Хайбрегтс. «Слабая неадекватность грамматик бесконтекстной фразовой структуры». Гер де Хаан, Мике Троммелен и Вим Зонневельд, редакторы, «От периферии к ядру» , страницы 81–99. Форис, Дордрехт, Нидерланды, 1984 г.

[shieber1985evidence-2] Jump up to: ^а ^б Стюарт М. Шибер. « Свидетельства против контекстной свободы естественного языка ». Лингвистика и философия , 8 (3): 333–343, 1985.

[joshi1985tree-3] Jump up to: ^а ^б ^с ^д Аравинд К. Джоши. « Грамматики, примыкающие к дереву: какая контекстная чувствительность необходима для обеспечения разумных структурных описаний? ». Дэвид Р. Даути, Лаури Карттунен и Арнольд М. Цвикки, редакторы журнала « Разбор естественного языка» , страницы 206–250. Издательство Кембриджского университета, 1985.

[weir1986relationship-4] Дэвид Дж. Вейр, К. Виджай-Шанкер и Аравинд К. Джоши. « Взаимосвязь между грамматиками, примыкающими к дереву, и головными грамматиками ». В материалах 24-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 67–74, Нью-Йорк, США, 1986.

[vijayshanker1987study-5] К. Виджай-Шанкер. « Исследование грамматик, прилегающих к деревьям ». доктор философии диссертация, Пенсильванский университет, Филадельфия, США, 1987 г.

[weir1988combinatory-6] Jump up to: ^а ^б Дэвид Дж. Вейр и Аравинд К. Джоши. « Комбинаторные категориальные грамматики: порождающая сила и связь с линейными бесконтекстными системами переписывания ». В материалах 26-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 278–285, Буффало, США, 1988.

[vijayshanker1987characterizing-7] Jump up to: ^а ^б ^с ^д К. Виджай-Шанкер, Дэвид Дж. Вейр и Аравинд К. Джоши. « Характеристика структурных описаний, созданных с помощью различных грамматических формализмов ». В материалах 25-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 104–111, Стэнфорд, Калифорния, США, 1987.

[weir1988characterizing-8] Jump up to: ^а ^б Дэвид Дж. Вейр. « Характеристика умеренно контекстно-зависимых грамматических формализмов ». доктор философии диссертация, Пенсильванский университет, Филадельфия, США, 1988 г.

[seki1991multiple-9] Jump up to: ^а ^б Хироюки Секи, Такаси Мацумура, Мамору Фуджи и Тадао Касами. « О множественных контекстно-свободных грамматиках ». Теоретическая информатика , 88(2):191–229, 1991.

[kanazawa2009pumping-10] Jump up to: ^а ^б ^с ^д Макото Канадзава. « Лемма о накачке для нескольких хорошо вложенных контекстно-свободных языков ». В разделе «Развития теории языка». 13-я Международная конференция DLT 2009, Штутгарт, Германия, 30 июня – 3 июля 2009 г. Труды , том 5583 конспектов лекций по информатике , страницы 312–325, 2009 г.

[kallmeyer2010mildly-11] Jump up to: ^а ^б Лаура Каллмейер. « О мягком контекстно-зависимом нелинейном переписывании ». Исследования языка и вычислений , 8(4):341–363, 2010.

[gomez2010efficient-12] Jump up to: ^а ^б ^с Карлос Гомес-Родригес, Марко Кульманн и Джорджио Сатта. « Эффективный анализ хорошо вложенных линейных контекстно-свободных систем переписывания ». В материалах по технологиям человеческого языка: Ежегодная конференция Североамериканского отделения Ассоциации компьютерной лингвистики (NAACL) 2010 г. , страницы 276–284, Лос-Анджелес, США, 2010 г.

[kallmeyer2010parsing-13] Jump up to: ^а ^б Лаура Каллмейер. Синтаксический анализ за пределами контекстно-свободных грамматик . Спрингер, 2010.

[michaelis1996semilinearity-14] Йенс Михаэлис и Маркус Крахт. « Полулинейность как синтаксический инвариант ». В логических аспектах компьютерной лингвистики. Первая международная конференция, LACL 1996, Нанси, Франция, 23–25 сентября 1996 г. Избранные статьи , том 1328 конспектов лекций по информатике , страницы 329–345. Спрингер, 1997.

[pollard1984generalized-15] Карл Дж. Поллард . «Обобщенные грамматики фразовой структуры, главные грамматики и естественный язык». доктор философии диссертация, Стэнфордский университет, 1984 г.

[roach1987formal-16] Келли Роуч. « Формальные свойства головных грамматик ». Алексис Манастер-Рамер, редактор журнала «Математика языка» , страницы 293–347. Джон Бенджаминс, 1987 год.

[gazdar1987applicability-17] Джеральд Газдар. « Применимость индексированных грамматик к естественному языку ». В книге Уве Рейле и Кристиана Рорера, редакторов, «Разбор естественного языка и лингвистические теории» , страницы 69–94. Д. Рейдель, 1987.

[michaelis1998derivational-18] Йенс Михаэлис. « Деривационный минимализм слегка контекстно-зависим ». В «Логических аспектах компьютерной лингвистики», Третья международная конференция, LACL 1998, Гренобль, Франция, 14–16 декабря 1998 г., Избранные статьи , том 2014 г. Конспектов лекций по информатике , страницы 179–198. Спрингер, 1998.

[boullier2004range-19] Пьер Булье. « Грамматики конкатенации диапазонов ». В Гарри К. Бунте, Джоне Кэрролле и Джорджио Сатте, редакторах, « Новые разработки в технологии синтаксического анализа» , том 23 журнала «Текст, речь и языковые технологии» , страницы 269–289. Издательство Kluwer Academic, 2004.

[fischer1968grammars-20] Майкл Дж. Фишер. « Грамматики с макроподобными постановками ». На девятом ежегодном симпозиуме по теории коммутации и автоматов , страницы 131–142, Скенектади, Нью-Йорк, США, 1968.

[hotz1996parsing-21] Гюнтер Хотц и Гизела Питч. «О синтаксическом анализе связанных контекстно-свободных языков». Теоретическая информатика , 161(1–2):205–233, 1996.

[rambow1994two-22] Оуэн Рэмбоу и Джорджио Сатта. « Двумерная иерархия для систем параллельной перезаписи ». Технический отчет IRCS-94-02, Пенсильванский университет, Филадельфия, США, 1994 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]