Из Википедии, бесплатной энциклопедии
  (Перенаправлено с умеренно зависимого от контекста языка )
Перейти к навигации Перейти к поиску

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

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

Фон [ править ]

К 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] класс умеренно контекстно-зависимых грамматик должен обладать следующими свойствами:

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

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

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

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

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

Межсерийные зависимости [ править ]

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

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

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

Постоянный рост [ править ]

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

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

Полиномиальный анализ [ править ]

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

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

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

Формализмы [ править ]

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

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

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

Формализмы эквивалентны общим LCFRS / MCFG [ править ]

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

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

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

Отношения между формализмами [ править ]

Линейные системы переписывания без контекста / множественные контекстно-свободные грамматики образуют двумерную иерархию порождающей способности по двум параметрам, зависящим от грамматики, называемым разветвлением и рангом . [22] Точнее, языки, сгенерированные LCFRS / MCFG с разветвлением  f  ≥ 1 и рангом  r  ≥ 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.

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ a b Рини Хайбрегтс. «Слабая неадекватность грамматик контекстно-свободных фраз». Гер де Хаан, Мике Троммелен и Вим Зонневельд, редакторы, Van periferie naar kern , страницы 81–99. Форис, Дордрехт, Нидерланды, 1984.
  2. ^ a b Стюарт М. Шибер. « Свидетельства против контекстной свободы естественного языка ». Лингвистика и философия , 8 (3): 333–343, 1985.
  3. ^ а б в г Аравинд К. Джоши. « Грамматики, примыкающие к дереву: какая контекстная чувствительность требуется для предоставления разумных структурных описаний? ». В книге Дэвида Р. Даути, Лаури Карттунена и Арнольда М. Цвикки, редакторов, Natural Language Parsing , страницы 206–250. Издательство Кембриджского университета, 1985.
  4. ^ Дэвид Дж. Вейр, К. Виджай-Шанкер и Аравинд К. Джоши. « Взаимосвязь между грамматиками, примыкающими к дереву, и грамматиками головы ». В материалах 24-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 67–74, Нью-Йорк, США, 1986.
  5. ^ К. Виджай-Шанкер. " Исследование грамматик, прилегающих к дереву ". Кандидат наук. диссертация, Пенсильванский университет, Филадельфия, США, 1987.
  6. ^ а б Дэвид Дж. Вейр и Аравинд К. Джоши. « Комбинированные категориальные грамматики: порождающая сила и связь с линейными системами перезаписи, не зависящими от контекста ». В материалах 26-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 278–285, Буффало, США, 1988.
  7. ^ a b c d К. Виджай-Шанкер, Дэвид Дж. Вейр и Аравинд К. Джоши. « Характеристика структурных описаний, произведенных различными грамматическими формализмами ». В материалах 25-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 104–111, Стэнфорд, Калифорния, США, 1987.
  8. ^ а б Дэвид Дж. Вейр. « Характеризуя слегка контекстно-зависимые грамматические формализмы ». Кандидат наук. диссертация, Пенсильванский университет, Филадельфия, США, 1988.
  9. ^ а б Хироюки Секи, Такаши Мацумура, Мамору Фуджи и Тадао Касами. « О множественных контекстно-свободных грамматиках ». Теоретическая информатика , 88 (2): 191–229, 1991.
  10. ^ a b c d Макото Канадзава. « Лемма накачки для множественных контекстно-свободных языков с хорошей вложенностью ». В развитии теории языка. 13-я Международная конференция, DLT 2009, Штутгарт, Германия, 30 июня - 3 июля 2009 г. Труды , том 5583 конспектов лекций по информатике , страницы 312–325, 2009 г.
  11. ^ а б Лаура Каллмейер. « О слегка контекстно-зависимом нелинейном перезаписи ». Исследования языка и вычислений , 8 (4): 341–363, 2010.
  12. ^ a b c Карлос Гомес-Родригес, Марко Кульман и Джорджио Сатта. « Эффективный анализ хорошо вложенных линейных систем перезаписи без контекста ». 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. ^ а б Лаура Каллмейер. Анализ вне контекстно-свободных грамматик . Спрингер, 2010.
  14. ^ Йенс Михаэлис и Маркус Крахт. « Полулинейность как синтаксический инвариант ». В логических аспектах компьютерной лингвистики. Первая международная конференция, LACL 1996, Нанси, Франция, 23–25 сентября 1996 г. Избранные статьи , том 1328конспектов лекций по информатике , страницы 329–345. Спрингер, 1997.
  15. ^ Карл Дж. Поллард . «Обобщенные грамматики фразовой структуры, основные грамматики и естественный язык». Кандидат наук. диссертация, Стэнфордский университет, 1984.
  16. ^ Келли Роуч. « Формальные свойства головных грамматик ». В Алексис Манастер-Рамер, редактор, « Математика языка» , страницы 293–347. Джон Бенджаминс, 1987.
  17. ^ Джеральд Газдар. « Применимость индексированных грамматик к естественному языку ». В Уве Рейле и Кристиане Рорере, редакторах, Natural Language Parsing and Linguistic Theories , страницы 69–94. Д. Рейдель, 1987.
  18. ↑ Йенс Михаэлис. « Деривационный минимализм умеренно контекстно-зависимый ». В логических аспектах компьютерной лингвистики, Третья международная конференция, LACL 1998, Гренобль, Франция, 14–16 декабря 1998 г., Избранные статьи , том 2014 конспектов лекций по информатике , страницы 179–198. Спрингер, 1998.
  19. ^ Пьер Булье. « Грамматики конкатенации диапазонов ». В книге Гарри С. Банта, Джона Кэрролла и Джорджио Сатта, редакторов, « Новые разработки в технологии синтаксического анализа» , том 23, « Технология текста, речи и языка» , страницы 269–289. Kluwer Academic Publishers, 2004.
  20. ^ Майкл Дж. Фишер. " Грамматики с Macro-Like Productions ". В Девятом ежегодном симпозиуме по теории переключений и автоматов , страницы 131–142, Скенектади, Нью-Йорк, США, 1968.
  21. ^ Гюнтер Хотц и Гизела Питч. «О синтаксическом анализе связанных контекстно-свободных языков». Теоретическая информатика , 161 (1-2): 205-233, 1996.
  22. ^ Owen Rambow и Giorgio Satta. « Двумерная иерархия для параллельных систем перезаписи ». Технический отчет IRCS-94-02, Пенсильванский университет, Филадельфия, США, 1994.