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