Jump to content

Контекстно-зависимая грамматика

Контекстно -зависимая грамматика ( CSG ) — это формальная грамматика , в которой левая и правая части любых правил производства могут быть окружены контекстом терминальных и нетерминальных символов . Контекстно-зависимые грамматики являются более общими, чем контекстно-свободные грамматики , в том смысле, что существуют языки, которые можно описать с помощью CSG, но не с помощью контекстно-свободной грамматики. Контекстно-зависимые грамматики менее общие (в том же смысле), чем неограниченные грамматики . Таким образом, CSG занимают место между контекстно-свободными и неограниченными грамматиками в иерархии Хомского . [1]

Формальный язык , который может быть описан контекстно-зависимой грамматикой или, что то же самое, несжимающей грамматикой или линейным ограниченным автоматом , называется контекстно-зависимым языком . В некоторых учебниках CSG фактически определяются как незаключенные, [2] [3] [4] [5] определил их не так хотя Ноам Хомский в 1959 году. [6] [7] Этот выбор определения не имеет значения с точки зрения создаваемых языков (т. е. два определения слабо эквивалентны ), но имеет значение с точки зрения того, какие грамматики структурно считаются контекстно-зависимыми; последний вопрос был проанализирован Хомским в 1963 году. [8] [9]

Хомский представил контекстно-зависимые грамматики как способ описания синтаксиса естественного языка , где часто бывает, что слово может подходить или не подходить в определенном месте в зависимости от контекста. Уолтер Сэвич раскритиковал терминологию «контекстно-зависимая» как вводящую в заблуждение и предложил термин «нестирание» как лучшее объяснение различия между CSG и неограниченной грамматикой . [10]

Хотя хорошо известно, что некоторые особенности языков (например, межпоследовательная зависимость ) не являются контекстно-свободными, остается открытым вопрос, какая выразительная сила CSG необходима для того, чтобы уловить контекстную чувствительность, присущую естественным языкам. Последующие исследования в этой области были сосредоточены на более вычислительно управляемых, умеренно контекстно-зависимых языках . [ нужна ссылка ] Синтаксис некоторых языков визуального программирования можно описать с помощью контекстно-зависимых граф-грамматик . [11]

Формальное определение

[ редактировать ]

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

[ редактировать ]

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

Строка непосредственно дает или непосредственно наследует строку , обозначенный как , если v можно получить из u применением некоторого правила производства в P , то есть если и , где является производственным правилом, и — это незатронутая левая и правая часть строки соответственно.В более общем смысле u говорят, что дает или приводит к , v , обозначаемому как , если v можно получить из u повторным применением правил производства, т. е. если для некоторого n ≥ 0 и некоторых строк . Другими словами, отношение есть рефлексивное транзитивное замыкание отношения .

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

Контекстно-зависимая грамматика

[ редактировать ]

Формальная грамматика является контекстно-зависимой , если каждое правило в P имеет форму где пустая строка или форма

а А б → агв

с A N , [примечание 1] , [примечание 2] и . [примечание 3]

Название «контекстно-зависимый» объясняется α и β, которые образуют контекст A и определяют, можно ли A заменить на γ или нет.Напротив, в бесконтекстной грамматике контекст отсутствует: левая часть каждого правила производства является просто нетерминалом.

Строка γ не может быть пустой. Без этого ограничения результирующие грамматики становятся равными по мощности неограниченным грамматикам . [10]

(Слабо) эквивалентные определения

[ редактировать ]

Несжимающая грамматика это грамматика, в которой для любого производственного правила формы u v длина u меньше или равна длине v .

Каждая контекстно-зависимая грамматика является несжимающей, тогда как каждая несжимающая грамматика может быть преобразована в эквивалентную контекстно-зависимую грамматику; эти два класса слабо эквивалентны . [12]

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

Грамматики , чувствительные к левому и правому контексту, определяются путем ограничения правил только формой α A → αγ и только A β → γβ соответственно. Языки, созданные с помощью этих грамматик, также представляют собой полный класс контекстно-зависимых языков. [13] Эквивалентность устанавливалась по нормальной форме Пенттонена . [14]

а н б н с н

[ редактировать ]

Следующая контекстно-зависимая грамматика с начальным символом S генерирует канонический неконтекстно -свободный язык { a н б н с н | п ≥ 1 } : [ нужна ссылка ]

1.       С    →     а Б С
2. С а С Б С
3. С Б С С
4. С С В С
5. В С В С
6. В С Б С
7. а Б а б
8. б Б б б
9. б С б с
10. с С с с

1 и 2 допускают раздутие S до Правила н БК ( БК ) п -1 ; правила с 3 по 6 позволяют последовательно обменивать каждое CB на BC ( четыре правила для этого необходимо , так как правило CB BC не укладывается в схему α A β → αγβ); правила 7–10 позволяют заменять нетерминал B или C соответствующим терминалом b или c соответственно, при условии, что он находится в правильном месте.Цепочка генерации aaabbbccc такова:

С
2 aSBC
2 a aSBC BC
1 aa aBC BCBC
3 aaaB CZ CBC
4 aaaB WZ CBC
5 aaaB WC CBC
6 aaaB BC CBC
3 aaaBBC CZ C
4 aaaBBC WZ C
5 aaaBBC WC C
6 aaaBBC BC C
3 aaaBB CZ CC
4 aaaBB WZ CC
5 aaaBB WC CC
6 aaaBB BC CC
7 aa ab BBCCC
8 aaa bb BCCC
8 aaab bb CCC
9 aaabb bc CC
10 aaabbb cc C
10 aaabbbc cc

а н б н с н д н , и т. д.

[ редактировать ]

Для анализа { a н б н с н д н | n ≥ 1 } и другие языки с еще большим количеством букв. Здесь мы показываем более простой подход с использованием несжимающих грамматик: [ нужна ссылка ] Начните с ядра регулярных продукций, генерирующих формы предложений. а затем включить неконтрактную продукцию , , , , , , , , , .

а м б н с м д н

[ редактировать ]

Несжимающаяся грамматика (для которой существует эквивалентная CSG) для языка определяется

,
,
,
,
,
,
, и
.

С помощью этих определений вывод для является: . [ нужна ссылка ]

Несжимающая грамматика языка { a 2 я | i ≥ 1 } строится в примере 9.5 (стр. 224) из (Hopcroft, Ullman, 1979): [15]

Курода нормальная форма

[ редактировать ]

Любую контекстно-зависимую грамматику, которая не генерирует пустую строку, можно преобразовать в слабо эквивалентную в нормальной форме Курода . «Слабо эквивалент» здесь означает, что две грамматики порождают один и тот же язык. Нормальная форма, как правило, не будет контекстно-зависимой, а будет несжимающей грамматикой . [16] [17]

Нормальная форма Курода — это реальная нормальная форма для несжимающихся грамматик.

Свойства и использование

[ редактировать ]

Эквивалентность линейному ограниченному автомату

[ редактировать ]

Формальный язык может быть описан контекстно-зависимой грамматикой тогда и только тогда, когда он принимается некоторым линейным ограниченным автоматом (LBA). [18] В некоторых учебниках этот результат приписывается исключительно Ландвеберу и Куроде . [7] Другие называют это теоремой Майхилла -Ландвебера-Куроды. [19] (Майхилл представил концепцию детерминистического LBA в 1960 году. Питер С. Ландвебер опубликовал в 1963 году, что язык, принятый детерминистическим LBA, является контекстно-зависимым. [20] Курода ввел понятие недетерминированного LBA и эквивалентности между LBA и CSG в 1964 году. [21] [22] )

По состоянию на 2010 год [ нужно обновить ] до сих пор остается открытым вопрос, может ли любой контекстно-зависимый язык быть принят детерминированным LBA . [23]

Свойства замыкания

[ редактировать ]

Контекстно-зависимые языки закрыты под дополнением . Этот результат 1988 года известен как теорема Иммермана – Селепшени . [19] При этом они замкнуты при объединении , пересечении , конкатенации , подстановке , [примечание 4] обратный гомоморфизм и Клини плюс . [24]

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

Вычислительные проблемы

[ редактировать ]

Проблема решения , которая спрашивает, принадлежит ли определенная строка s языку данной контекстно-зависимой грамматики G , является PSPACE-полной . Более того, существуют контекстно-зависимые грамматики, языки которых являются PSPACE-полными. Другими словами, существует контекстно-зависимая грамматика G, такая, что решение о том, принадлежит ли определенная строка s языку G, является PSPACE-полной (поэтому G фиксирована, и только s является частью входных данных задачи). [26]

Проблема пустоты для контекстно-зависимых грамматик (при условии, что контекстно-зависимая грамматика G равна L ( G )=∅ ?) неразрешима . [27] [примечание 5]

Как модель естественных языков

[ редактировать ]

Савич доказал следующий теоретический результат, на котором он основывает свою критику CSG как основы естественного языка: для любого рекурсивно перечислимого множества R существует контекстно-зависимый язык/грамматика G , который можно использовать как своего рода прокси для проверки членство в R следующим образом: для данной строки находится в s s R тогда и только тогда, когда существует целое положительное число n, для которого sc н находится в G, где c не являющийся частью R. — произвольный символ , [10]

Было показано, что почти все естественные языки в целом могут характеризоваться контекстно-зависимыми грамматиками, но весь класс CSG, по-видимому, намного больше, чем естественные языки. [ нужна ссылка ] Хуже того, поскольку вышеупомянутая проблема принятия решений для CSG является PSPACE-полной, это делает их совершенно непригодными для практического использования, поскольку алгоритм с полиномиальным временем для PSPACE-полной задачи подразумевал бы P=NP .

было доказано, что некоторые естественные языки не являются контекстно-свободными . На основе выявления так называемых перекрестных зависимостей и неограниченного скремблирования феномена [ нужна ссылка ] Однако это не обязательно означает, что класс CSG необходим для отражения «контекстной чувствительности» в разговорном смысле этих терминов на естественных языках. Например, линейные системы контекстно-свободной перезаписи (LCFRS) строго слабее, чем CSG, но могут учитывать явление перекрестных последовательных зависимостей; можно написать грамматику LCFRS для { a н б н с н д н | n ≥ 1}, например. [28] [29] [30]

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

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ т. е. A - единственный нетерминал
  2. ^ т.е. строки α и β нетерминалов (кроме начального символа) и терминалов
  3. ^ т.е. γ — непустая строка нетерминалов (кроме начального символа) и терминалов
  4. ^ более формально: если L ⊆ Σ * является контекстно-зависимым языком, и f отображает каждый a ∈Σ в контекстно-зависимый язык f ( a ), f ( L ) снова является контекстно-зависимым языком
  5. ^ Это также следует из того, что (1) контекстно-свободные языки также являются контекстно-зависимыми , (2) контекстно-зависимые языки замкнуты при пересечении , но (3) непересекаемость контекстно-свободных языков неразрешима .
  1. ^ (Хопкрофт, Ульман, 1979); п.9.4, стр.227
  2. ^ Линц, Питер (2011). Введение в формальные языки и автоматы . Издательство Джонс и Бартлетт. п. 291. ИСБН  978-1-4496-1552-9 .
  3. ^ Медуна, Александр (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 730. ИСБН  978-1-85233-074-3 .
  4. ^ Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж . (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. п. 189. ИСБН  978-0-08-050246-5 .
  5. ^ Мартин, Джон К. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. п. 277. ИСБН  9780073191461 .
  6. ^ Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. п. 26. ISBN  978-90-272-3250-2 .
  7. ^ Jump up to: а б Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж . (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. стр. 330–331. ISBN  978-0-08-050246-5 .
  8. ^ Хомский, Н. (1963). «Формальные свойства грамматики» . В Люсе, РД; Буш, Р.Р.; Галантер, Э. (ред.). Справочник по математической психологии . Нью-Йорк: Уайли. стр. 360–363.
  9. ^ Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 125–126. ISBN  978-90-272-3250-2 .
  10. ^ Jump up to: а б с Карлос Мартин Виде, изд. (1999). Проблемы математической лингвистики: семинар по математической лингвистике, Государственный колледж, Пенсильвания, апрель 1998 г. Издательство Джона Бенджамина. стр. 186–187. ISBN  90-272-1556-1 .
  11. ^ Чжан, Да-Цянь, Кан Чжан и Цзяньнун Цао. « Контекстно-зависимый формализм графовой грамматики для спецификации визуальных языков ». Компьютерный журнал 44.3 (2001): 186–200.
  12. ^ Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN  9780201029888 . ; п. 223–224; Упражнение 9, с. 230. В издании 2003 года глава о РГС была опущена.
  13. ^ Хазевинкель, Мишель (1989). Энциклопедия математики . Том. 4. Springer Science & Business Media. п. 297. ИСБН  978-1-55608-003-6 . также на https://www.encyclepediaofmath.org/index.php/Grammar,_context-sensitivity
  14. ^ Ито, Масами; Кобаяши, Юдзи; Сёдзи, Кунитака (2010). Автоматы, формальные языки и алгебраические системы: материалы AFLAS 2008, Киото, Япония, 20–22 сентября 2008 г. Всемирная научная. п. 183. ИСБН  978-981-4317-60-3 . цитируя Пенттонен, Мартти (август 1974 г.). «Односторонний и двусторонний контекст в формальных грамматиках» . Информация и контроль . 25 (4): 371–392. дои : 10.1016/S0019-9958(74)91049-3 .
  15. ^ Они получили грамматику путем систематического преобразования неограниченной грамматики , приведенной в Exm. 9.4, а именно:
    1. ,
    2. ,
    3. ,
    4. ,
    5. ,
    6. ,
    7. ,
    8. .
    В контекстно-зависимой грамматике строка, заключенная в квадратные скобки, например , считается одним символом (аналогично, например, <name-part> в форме Бэкуса–Наура ). Имена символов выбраны так, чтобы напоминать неограниченную грамматику. Аналогично, группы правил в контекстно-зависимой грамматике нумеруются по правилу неограниченной грамматики, из которого они произошли.
  16. ^ Курода, Сиге-Юки (июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы» . Информация и контроль . 7 (2): 207–223. дои : 10.1016/s0019-9958(64)90120-2 .
  17. ^ Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты классической теории языка». В Розенберге, Гжегож ; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Спрингер-Верлаг. стр. 175–252. ISBN  3-540-61486-9 . , Здесь: Теорема 2.2, с. 190
  18. ^ (Хопкрофт, Ульман, 1979); Теоремы 9.5, 9.6, с. 225–226
  19. ^ Jump up to: а б Сатнер, Клаус (весна 2016 г.). «Контекстно-зависимая грамматика» (PDF) . Университет Карнеги-Меллон . Архивировано из оригинала (PDF) 3 февраля 2017 г. Проверено 29 августа 2019 г.
  20. ^ П. С. Ландвебер (1963). «Три теоремы о грамматиках фразовой структуры типа 1» . Информация и контроль . 6 (2): 131–136. дои : 10.1016/s0019-9958(63)90169-4 .
  21. ^ Медуна, Александр (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 755. ИСБН  978-1-85233-074-3 .
  22. ^ Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 126–127. ISBN  978-90-272-3250-2 .
  23. ^ Мартин, Джон К. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. п. 283. ИСБН  9780073191461 .
  24. ^ (Хопкрофт, Ульман, 1979); Упражнение S9.10, с. 230–231
  25. ^ (Хопкрофт, Ульман, 1979); Упражнение S9.14, с. 230–232. h отображает каждый символ сам на себя или на пустую строку.
  26. ^ Пример такой грамматики, предназначенной для решения проблемы QSAT , приведен в Лита, резюме (01.09.2016). «О сложности проблемы обнаружения полиморфных вирусов ограниченной длины». 2016 18-й Международный симпозиум по символьным и числовым алгоритмам для научных вычислений (SYNASC) . стр. 371–378. дои : 10.1109/SYNASC.2016.064 . ISBN  978-1-5090-5707-8 . S2CID   18067130 .
  27. ^ (Хопкрофт, Ульман, 1979); Упражнение S9.13, с. 230–231
  28. ^ Калмейер, Лаура (2011). «Слегка контекстно-зависимые грамматические формализмы: естественные языки не являются контекстно-свободными» (PDF) . Архивировано (PDF) из оригинала 19 августа 2014 г.
  29. ^ Калмейер, Лаура (2011). «Слегка контекстно-зависимые грамматические формализмы: линейные контекстно-свободные системы переписывания» (PDF) . Архивировано (PDF) из оригинала 19 августа 2014 г.
  30. ^ Jump up to: а б Калмейер, Лаура (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 1–5. ISBN  978-3-642-14846-0 .

Дальнейшее чтение

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 607d6f85ede190130c3c6ba94751cc1a__1710394080
URL1:https://arc.ask3.ru/arc/aa/60/1a/607d6f85ede190130c3c6ba94751cc1a.html
Заголовок, (Title) документа по адресу, URL1:
Context-sensitive grammar - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)