Грамматический формализм, в некоторой степени зависящий от контекста

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

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

Фон

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

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

TAG-эквивалентные формализмы были обобщены путем введения линейных контекстно-свободных систем переписывания (LCFRS). [7] [8] Эти грамматики определяют бесконечную иерархию строковых языков между контекстно-свободными и контекстно-зависимыми языками, с языками, генерируемыми TAG-эквивалентными формализмами в нижнем конце [ требуется разъяснение ] иерархии. Независимо от LCFRS и почти одновременно с ним Хироюки Секи и др. предложили по сути идентичный формализм множественной контекстно-свободной грамматики (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] отождествляет способность моделировать кросс-серийные зависимости с возможностью генерировать язык копирования

С О П И = { ж ж ∣ ж ∈ { а , б } ∗ } {\displaystyle {\mathit {COPY}}=\{\,ww\mid w\in \{a,b\}^{*}\,\}}

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

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

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

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

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

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

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

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

Формализмы

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

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

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

Формализмы, эквивалентные хорошо вложенным 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. ^ аб Рини Хайбрегтс. «Слабая неадекватность грамматик бесконтекстной фразовой структуры». В Гер де Хаан, Мике Троммелен и Вим Зонневельд, редакторы, Van periferie naar kern , страницы 81–99. Форис, Дордрехт, Нидерланды, 1984 г.
  2. ^ Стюарт М. Шибер. «Доказательства против контекстно-свободного характера естественного языка». Лингвистика и философия , 8(3):333–343, 1985.
  3. ^ abcd Аравинд К. Джоши. «Грамматика примыкания деревьев: насколько контекстная чувствительность необходима для предоставления разумных структурных описаний?». В книге Дэвида Р. Доути, Лаури Карттунена и Арнольда М. Цвикки, редакторов, Natural Language Parsing , страницы 206–250. Cambridge University Press, 1985.
  4. ^ Дэвид Дж. Вейр, К. Виджай-Шанкер и Аравинд К. Джоши. «Связь между грамматиками смежных деревьев и грамматиками голов». В трудах 24-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 67–74, Нью-Йорк, США, 1986.
  5. ^ К. Виджай-Шанкер. «Исследование древовидных смежных грамматик». Кандидатская диссертация, Университет Пенсильвании, Филадельфия, США, 1987.
  6. ^ ab Дэвид Дж. Вейр и Аравинд К. Джоши. «Комбинаторные категориальные грамматики: порождающая сила и связь с линейными системами контекстно-свободной переписывания». В трудах 26-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 278–285, Буффало, США, 1988.
  7. ^ abcd K. Vijay-Shanker, David J. Weir и Aravind K. Joshi. «Характеристика структурных описаний, создаваемых различными грамматическими формализмами». В трудах 25-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL) , страницы 104–111, Стэнфорд, Калифорния, США, 1987.
  8. ^ Дэвид Дж. Вейр. «Характеристика умеренно контекстно-чувствительных грамматических формализмов». Кандидатская диссертация, Университет Пенсильвании, Филадельфия, США, 1988.
  9. ^ ab Хироюки Секи, Такаши Мацумура, Мамору Фудзи и Тадао Касами. «О множественных контекстно-свободных грамматиках». Теоретическая информатика , 88(2):191–229, 1991.
  10. ^ abcd Макото Каназава. "The Pumping Lemma for Well-Nested Multiple Context-Free Languages". В Developments in Language Theory. 13-я международная конференция, DLT 2009, Штутгарт, Германия, 30 июня–3 июля 2009 г. Труды , том 5583 Lecture Notes in Computer Science , страницы 312–325, 2009.
  11. ^ ab Лора Каллмейер. «О умеренной нелинейной переписывании, чувствительной к контексту». Исследования по языку и вычислениям , 8(4):341–363, 2010.
  12. ^ abc Карлос Гомес-Родригес, Марко Кульманн и Джорджио Сатта. "Эффективный анализ хорошо вложенных линейных систем контекстно-свободной переписывания". В Трудах Human Language Technologies: Ежегодная конференция 2010 года Североамериканского отделения Ассоциации компьютерной лингвистики (NAACL) , страницы 276–284, Лос-Анджелес, США, 2010.
  13. ^ ab Лора Каллмейер. Анализ за пределами контекстно-свободных грамматик . Springer, 2010.
  14. ^ Йенс Михаэлис и Маркус Крахт. «Полулинейность как синтаксический инвариант». В «Логических аспектах компьютерной лингвистики». Первая международная конференция, LACL 1996, Нанси, Франция, 23–25 сентября 1996 г. Избранные статьи , том 1328 Lecture Notes in Computer Science , страницы 329–345. Springer, 1997.
  15. ^ Карл Дж. Поллард . «Граммы обобщенной фразовой структуры, грамматики голов и естественный язык». Кандидатская диссертация, Стэнфордский университет, 1984.
  16. ^ Келли Роуч. «Формальные свойства грамматик головного языка». В Алексис Манастер-Рамер, редактор, Математика языка , страницы 293–347. Джон Бенджаминс, 1987.
  17. ^ Джеральд Газдар. «Применимость индексированных грамматик к естественному языку». В Уве Рейле и Кристиане Рорере, редакторах, Natural Language Parsing and Linguistic Theories , страницы 69–94. Д. Рейдель, 1987.
  18. ^ Йенс Михаэлис. «Деривационный минимализм слабо чувствителен к контексту». В «Логических аспектах компьютерной лингвистики», Третья международная конференция, LACL 1998, Гренобль, Франция, 14–16 декабря 1998 г., Избранные статьи , том 2014 г. Lecture Notes in Computer Science , страницы 179–198. Springer, 1998.
  19. ^ Пьер Булье. «Грамматика конкатенации диапазонов». В книге Гарри С. Банта, Джона Кэрролла и Джорджио Сатты, редакторов, Новые разработки в технологии синтаксического анализа , том 23 из Text, Speech and Language Technology , страницы 269–289. Kluwer Academic Publishers, 2004.
  20. ^ Майкл Дж. Фишер. «Грамматики с макроподобными производствами». В Девятом ежегодном симпозиуме по теории коммутации и автоматов , страницы 131–142, Скенектади, Нью-Йорк, США, 1968.
  21. ^ Гюнтер Хотц и Гизела Питч. «О синтаксическом анализе связанных контекстно-свободных языков». Теоретическая информатика , 161(1–2):205–233, 1996.
  22. ^ Оуэн Рэмбоу и Джорджио Сатта. «Двумерная иерархия для систем параллельной перезаписи». Технический отчет IRCS-94-02, Университет Пенсильвании, Филадельфия, США, 1994.
Взято с "https://en.wikipedia.org/w/index.php?title=Умеренно_контекстно-чувствительный_формализм_грамматики&oldid=1170405547"