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

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

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

• 1 Предпосылки
• 2 Характеризация
  • 2.1 Межсерийные зависимости
  • 2.2 Постоянный рост
  • 2.3 Полиномиальный синтаксический анализ
• 3 Формализмы
  • 3.1 Формализмы, эквивалентные TAG
  • 3.2 Формализмы, эквивалентные общему LCFRS / MCFG
  • 3.3 Формализмы, эквивалентные хорошо вложенным LCFRS / MCFG
  • 3.4 Отношения между формализмами
• 4 См. Также
• 5 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

Каллмейер определяет способность моделировать кросс-последовательные зависимости с возможностью создания языка копирования

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

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

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

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

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

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

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

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

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

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

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

• грамматике, примыкающей к дереву (TAG)
• Грамматика заголовка ( HG)
• Линейная индексированная грамматика (LIG)
• Комбинаторная категориальная грамматика (CCG)
• Хорошо вложенные LCFRS / MCFG разветвления 2

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

• Линейные бесконтекстные системы перезаписи (LCFRS)
• Множественные контекстно-свободные грамматики (MCFG)
• Многокомпонентные грамматики, примыкающие к дереву (MCTAG)
• Минималистичный грамматики (MG)
• Простые (линейные, без стирания, некомбинаторные), положительные грамматики конкатенации диапазонов (sRCG)

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

• Макрограмматики без дублирования
• Связанные контекстно-свободные грамматики (CCFG)
• Хорошо вложенные линейные системы контекстно-свободного перезаписывания
• Хорошо вложенные множественные контекстные бесплатные грамматики

Связи между формализмами

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

• Грамматика, примыкающая к дереву
• Линейная контекстно-свободная система перезаписи
• Конкатенация диапазонов грамматика
• Иерархия плотины

1. ^ Рини Хайбрегтс. «Слабая неадекватность грамматик контекстно-свободных фраз». Гер де Хаан, Мике Троммелен и Вим Зонневельд, редакторы, Van periferie naar kern, страницы 81–99. Foris, Dordrecht, Нидерланды, 1984.
2. ^ Стюарт М. Шибер. «Свидетельства против контекстной свободы естественного языка ». Лингвистика и философия, 8 (3): 333–343, 1985.
3. ^ Аравинд К. Джоши. «Грамматики, граничащие с деревом: какая контекстная чувствительность требуется для предоставления разумных структурных описаний? ». В книге Дэвида Р. Даути, Лаури Карттунена и Арнольда М. Цвикки, редакторов, Natural Language Parsing, страницы 206–250. Cambridge University Press, 1985.
4. ^Дэвид Дж. Вейр, К. Виджай-Шанкер и Аравинд К. Джоши. «Связь между грамматиками, примыкающими к дереву, и грамматиками головы ». В Трудах 24-го Ежегодного собрания Ассоциации компьютерной лингвистики (ACL), страницы 67–74, Нью-Йорк, США, 1986.
5. ^К. Виджай-Шанкер. "Исследование грамматик, прилегающих к дереву ". Кандидат наук. диссертация, Университет Пенсильвании, Филадельфия, США, 1987.
6. ^ Дэвид Дж. Вейр и Аравинд К. Джоши. «Комбинированные категориальные грамматики: генерирующая сила и связь с линейными бесконтекстными системами перезаписи ». В материалах 26-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL), страницы 278–285, Буффало, США, 1988.
7. ^ К. Виджай-Шанкер, Дэвид Дж. Вейр и Аравинд К. Джоши. «Характеристика структурных описаний, произведенных различными грамматическими формализмами ». In Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics (ACL), pages 104–111, Stanford, CA, USA, 1987.
8. ^ Дэвид Дж. Вейр. «Характеристика грамматических формализмов, слегка зависимых от контекста ». Кандидат наук. диссертация, Пенсильванский университет, Филадельфия, США, 1988.
9. ^ Хироюки Секи, Такаши Мацумура, Мамору Фуджи и Тадао Касами. «О множественных контекстно-свободных грамматиках ». Теоретическая информатика, 88 (2): 191–229, 1991.
10. ^ Макото Канадзава. «Лемма накачки для множественных контекстно-свободных языков с хорошей вложенностью ». В развитии теории языка. 13-я Международная конференция, DLT 2009, Штутгарт, Германия, 30 июня - 3 июля 2009 г. Труды, том 5583 конспектов лекций по информатике, страницы 312–325, 2009 г.
11. ^ Лаура Каллмейер. «О слегка контекстно-зависимом нелинейном перезаписи ». Research on Language and Computing, 8 (4): 341–363, 2010.
12. ^ Карлос Гомес-Родригес, Марко Кульман и Джорджио Сатта. «Эффективный анализ хорошо вложенных линейных систем перезаписи без контекста ». In Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 276–284, Los Angeles, USA, 2010.
13. ^ Лаура Каллмейер. Анализ вне контекстно-свободных грамматик. Springer, 2010.
14. ^Йенс Михаэлис и Маркус Крахт. «Полулинейность как синтаксический инвариант ». В логических аспектах компьютерной лингвистики. Первая международная конференция, LACL 1996, Нанси, Франция, 23–25 сентября 1996 г. Избранные статьи, том 1328 конспектов лекций по информатике, страницы 329–345. Springer, 1997.
15. ^Карл Дж. Поллард. «Обобщенные грамматики фразовой структуры, основные грамматики и естественный язык». Кандидат наук. диссертация, Стэнфордский университет, 1984.
16. ^Келли Роуч. «Формальные свойства основных грамматик ». В Алексис Манастер-Рамер, редактор, «Математика языка», страницы 293–347. Джон Бенджаминс, 1987.
17. ^Джеральд Газдар. «Применимость индексированных грамматик к естественному языку ». В Уве Рейле и Кристиане Рорере, редакторах, Natural Language Parsing and Linguistic Theories, стр. 69–94. D. Reidel, 1987.
18. ^Йенс Михаэлис. «Деривационный минимализм умеренно контекстно-зависимый ». В логических аспектах компьютерной лингвистики, Третья международная конференция, LACL 1998, Гренобль, Франция, 14–16 декабря 1998 г., Избранные статьи, том 2014 конспектов лекций по информатике, страницы 179–198. Springer, 1998.
19. ^Пьер Булье. «Грамматика конкатенации диапазонов ». В книге Гарри С. Банта, Джона Кэрролла и Джорджио Сатта, редакторов, «Новые разработки в технологии синтаксического анализа», том 23, «Технология текста, речи и языка», страницы 269–289. Kluwer Academic Publishers, 2004.
20. ^Майкл Дж. Фишер. «Грамматики с макроподобными произведениями ». В Девятом ежегодном симпозиуме по теории коммутации и автоматов, страницы 131–142, Скенектади, Нью-Йорк, США, 1968.
21. ^Гюнтер Хотц и Гизела Питч. «О синтаксическом анализе языков, свободных от контекста». Теоретическая информатика, 161 (1-2): 205-233, 1996.
22. ^Оуэн Рамбоу и Джорджио Сатта. «Двумерная иерархия для параллельных систем перезаписи ». Технический отчет IRCS-94-02, Университет Пенсильвании, Филадельфия, США, 1994.