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

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

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

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

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

Формальное определение [ править ]

Формальная грамматика [ править ]

Обозначим формальную грамматику как $G=(N,\Sigma ,P,S)$ , с $N$ набор нетерминальных символов, $\Sigma$ набор терминальных символов, $P$ набор производственных правил и $S\in N$ стартовый символ.

Строка $u\in (N\cup \Sigma )^{*}$ непосредственно дает или непосредственно наследует строку $v\in (N\cup \Sigma )^{*}$ , обозначенный как $u\Rightarrow v$ , если v можно получить из u применением некоторого правила производства в P , то есть если $u=\gamma L\delta$ и $v=\gamma R\delta$ , где $(L\to R)\in P$ является производственным правилом, и $\gamma ,\delta \in (N\cup \Sigma )^{*}$ — это незатронутая левая и правая часть строки соответственно. В более общем смысле , что u говорят дает или приводит к , v , обозначаемому как $u\Rightarrow ^{*}v$ , если v можно получить из u повторным применением правил производства, т. е. если $u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v$ для некоторого n ≥ 0 и некоторых строк $u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}$ . Другими словами, отношение $\Rightarrow ^{*}$ есть рефлексивное транзитивное замыкание отношения $\Rightarrow$ .

Язык : грамматики G представляет собой набор всех строк терминальных символов, выводимых из ее начального символа, формально $L(G)=\{w\in \Sigma ^{*}\mid S\Rightarrow ^{*}w\}$ . Возможны производные, которые не заканчиваются строкой, состоящей только из терминальных символов, но не вносят вклад в L ( G ).

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

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

а А б → агв

с A ∈ N , ^{[примечание 1]} $\alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}$ , ^{[заметка 2]} и $\gamma \in (N\cup \Sigma \setminus \{S\})^{+}$ . ^{[заметка 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.	с	С	→	с	с

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

С

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ ₉ aaabb bc CC

→ ₁₀ aaabbb cc C

→ ₁₀ aaabbbc cc

а ^нб ^нс ^нд ^ни т. д. [ править ]

Для анализа { a ^нб ^нс ^нд ^н| n ≥ 1 } и другие языки с еще большим количеством букв. Здесь мы показываем более простой подход с использованием несжимающих грамматик: ^{[ нужна цитата ]} Начните с ядра регулярных продукций, генерирующих формы предложений. $(ABCD)^{n}abcd$ а затем включить неконтрактную продукцию $p_{Da}:Da\rightarrow aD$ , $p_{Db}:Db\rightarrow bD$ , $p_{Dc}:Dc\rightarrow cD$ , $p_{Dd}:Dd\rightarrow dd$ , $p_{Ca}:Ca\rightarrow aC$ , $p_{Cb}:Cb\rightarrow bC$ , $p_{Cc}:Cc\rightarrow cc$ , $p_{Ba}:Ba\rightarrow aB$ , $p_{Bb}:Bb\rightarrow bb$ , $p_{Aa}:Aa\rightarrow aa$ .

а ^мб ^нс ^мд ^н[ редактировать ]

Несжимающаяся грамматика (для которой существует эквивалентная CSG) для языка $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}\mid m\geq 1,n\geq 1\}$ определяется

p_{1}:R\rightarrow aRC|aC

,

p_{3}:T\rightarrow BTd|Bd

,

p_{5}:CB\rightarrow BC

,

p_{0}:S\rightarrow RT

,

p_{6}:aB\rightarrow ab

,

p_{7}:bB\rightarrow bb

,

p_{8}:Cd\rightarrow cd

, и

p_{9}:Cc\rightarrow cc

.

С помощью этих определений вывод для $a^{3}b^{2}c^{3}d^{2}$ является: $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ . ^{[ нужна цитата ]}

а ^{2 ^я}[ редактировать ]

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

$S\rightarrow [ACaB]$
${\begin{cases}\ [Ca]a\rightarrow aa[Ca]\\\ [Ca][aB]\rightarrow aa[CaB]\\\ [ACa]a\rightarrow [Aa]a[Ca]\\\ [ACa][aB]\rightarrow [Aa]a[CaB]\\\ [ACaB]\rightarrow [Aa][aCB]\\\ [CaB]\rightarrow a[aCB]\end{cases}}$
$[aCB]\rightarrow [aDB]$
$[aCB]\rightarrow [aE]$
${\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\rightarrow [ADa]a\\\ a[DaB]\rightarrow [Da][aB]\\\ [Aa][DaB]\rightarrow [ADa][aB]\end{cases}}$
$[ADa]\rightarrow [ACa]$
${\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}$
$[AEa]\rightarrow a$

Нормальная форма Курода [ править ]

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

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

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

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

Формальный язык может быть описан контекстно-зависимой грамматикой тогда и только тогда, когда он принимается некоторым линейным ограниченным автоматом (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 .
^ Перейти обратно: ^а ^б Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. стр. 330–331. ISBN 978-0-08-050246-5 .
^ Хомский, Н. (1963). «Формальные свойства грамматики» . В Люсе, РД; Буш, Р.Р.; Галантер, Э. (ред.). Справочник по математической психологии . Нью-Йорк: Уайли. стр. 360–363.
^ Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 125–126. ISBN 978-90-272-3250-2 .
^ Перейти обратно: ^а ^б ^с Карлос Мартин Виде, изд. (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, а именно:
1. $S\rightarrow ACaB$ ,
2. $Ca\rightarrow aaC$ ,
3. $CB\rightarrow DB$ ,
4. $CB\rightarrow E$ ,
5. $aD\rightarrow Da$ ,
6. $AD\rightarrow AC$ ,
7. $aE\rightarrow Ea$ ,
8. $AE\rightarrow \varepsilon$ .
В контекстно-зависимой грамматике строка, заключенная в квадратные скобки, например $[ACaB]$ $[ACaB]$ , считается одним символом (аналогично, например, <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
^ Перейти обратно: ^а ^б Сатнер, Клаус (весна 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 г.
^ Перейти обратно: ^а ^б Калмейер, Лаура (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 1–5. ISBN 978-3-642-14846-0 .

Дальнейшее чтение [ править ]

Медуна, Александр ; Швец, Мартин (2005). Грамматики с контекстными условиями и их применение . Джон Уайли и сыновья. ISBN 978-0-471-73655-4 .

Внешние ссылки [ править ]

Анализ Эрли для контекстно-зависимых грамматик

[12] т. е. A - единственный нетерминал

[13] т.е. строки α и β нетерминалов (кроме начального символа) и терминалов

[14] т.е. γ — непустая строка нетерминалов (кроме начального символа) и терминалов

[27] более формально: если L ⊆ Σ ^* является контекстно-зависимым языком, и f отображает каждый a ∈Σ в контекстно-зависимый язык f ( a ), f ( L ) снова является контекстно-зависимым языком

[32] Это также следует из того, что (1) контекстно-свободные языки также являются контекстно-зависимыми , (2) контекстно-зависимые языки замкнуты при пересечении , но (3) непересекаемость контекстно-свободных языков неразрешима .

[1] (Хопкрофт, Ульман, 1979); п.9.4, стр.227

[Linz2011-2] Линц, Питер (2011). Введение в формальные языки и автоматы . Издательство Джонс и Бартлетт. п. 291. ИСБН 978-1-4496-1552-9 .

[Meduna2000-3] Медуна, Александр (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 730. ИСБН 978-1-85233-074-3 .

[DavisSigal1994-4] Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. п. 189. ИСБН 978-0-08-050246-5 .

[5] Мартин, Джон К. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. п. 277. ИСБН 9780073191461 .

[Levelt2008-6] Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. п. 26. ISBN 978-90-272-3250-2 .

[DavisSigal1994b-7] Перейти обратно: ^а ^б Дэвис, Мартин ; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Морган Кауфманн. стр. 330–331. ISBN 978-0-08-050246-5 .

[8] Хомский, Н. (1963). «Формальные свойства грамматики» . В Люсе, РД; Буш, Р.Р.; Галантер, Э. (ред.). Справочник по математической психологии . Нью-Йорк: Уайли. стр. 360–363.

[Levelt2008-126-9] Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 125–126. ISBN 978-90-272-3250-2 .

[Vide1999-10] Перейти обратно: ^а ^б ^с Карлос Мартин Виде, изд. (1999). Проблемы математической лингвистики: семинар по математической лингвистике, Государственный колледж, Пенсильвания, апрель 1998 г. Издательство Джона Бенджамина. стр. 186–187. ISBN 90-272-1556-1 .

[11] Чжан, Да-Цянь, Кан Чжан и Цзяньнун Цао. « Контекстно-зависимый формализм графовой грамматики для спецификации визуальных языков ». Компьютерный журнал 44.3 (2001): 186–200.

[15] Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 9780201029888 . ; п. 223–224; Упражнение 9, с. 230. В издании 2003 года глава о РГС была опущена.

[Hazewinkel1989-16] Хазевинкель, Мишель (1989). Энциклопедия математики . Том. 4. Springer Science & Business Media. п. 297. ИСБН 978-1-55608-003-6 . также на https://www.encyclepediaofmath.org/index.php/Grammar,_context-sensitivity

[ItoKobayashi2010-17] Ито, Масами; Кобаяши, Юдзи; Сёдзи, Кунитака (2010). Автоматы, формальные языки и алгебраические системы: материалы AFLAS 2008, Киото, Япония, 20–22 сентября 2008 г. Всемирная научная. п. 183. ИСБН 978-981-4317-60-3 . цитируя Пенттонен, Мартти (август 1974 г.). «Односторонний и двусторонний контекст в формальных грамматиках» . Информация и контроль . 25 (4): 371–392. дои : 10.1016/S0019-9958(74)91049-3 .

[18] Они получили грамматику путем систематического преобразования неограниченной грамматики , приведенной в Exm. 9.4, а именно:
$S\rightarrow ACaB$ ,

$Ca\rightarrow aaC$ ,

$CB\rightarrow DB$ ,

$CB\rightarrow E$ ,

$aD\rightarrow Da$ ,

$AD\rightarrow AC$ ,

$aE\rightarrow Ea$ ,

$AE\rightarrow \varepsilon$ .
В контекстно-зависимой грамматике строка, заключенная в квадратные скобки, например $[ACaB]$ , считается одним символом (аналогично, например, <name-part>в форме Бэкуса–Наура ). Имена символов выбраны так, чтобы напоминать неограниченную грамматику. Аналогично, группы правил в контекстно-зависимой грамматике нумеруются по правилу неограниченной грамматики, из которого они произошли.

[21] $S\rightarrow ACaB$ ,

[22] $Ca\rightarrow aaC$ ,

[23] $CB\rightarrow DB$ ,

[24] $CB\rightarrow E$ ,

[25] $aD\rightarrow Da$ ,

[26] $AD\rightarrow AC$ ,

[27] $aE\rightarrow Ea$ ,

[28] $AE\rightarrow \varepsilon$ .

[19] Курода, Сиге-Юки (июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы» . Информация и контроль . 7 (2): 207–223. дои : 10.1016/s0019-9958(64)90120-2 .

[20] Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты классической теории языка». В Розенберге, Гжегож ; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Спрингер-Верлаг. стр. 175–252. ISBN 3-540-61486-9 . , Здесь: Теорема 2.2, с. 190

[21] (Хопкрофт, Ульман, 1979); Теоремы 9.5, 9.6, с. 225–226

[flac-22] Перейти обратно: ^а ^б Сатнер, Клаус (весна 2016 г.). «Контекстно-зависимая грамматика» (PDF) . Университет Карнеги Меллон . Архивировано из оригинала (PDF) 3 февраля 2017 г. Проверено 29 августа 2019 г.

[23] П. С. Ландвебер (1963). «Три теоремы о грамматиках фразовой структуры типа 1» . Информация и контроль . 6 (2): 131–136. дои : 10.1016/s0019-9958(63)90169-4 .

[24] Медуна, Александр (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 755. ИСБН 978-1-85233-074-3 .

[25] Левелт, Виллем Дж. М. (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 126–127. ISBN 978-90-272-3250-2 .

[26] Мартин, Джон К. (2010). Введение в языки и теорию вычислений (4-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. п. 283. ИСБН 9780073191461 .

[28] (Хопкрофт, Ульман, 1979); Упражнение S9.10, с. 230–231

[29] (Хопкрофт, Ульман, 1979); Упражнение S9.14, с. 230–232. h отображает каждый символ сам на себя или на пустую строку.

[30] Пример такой грамматики, предназначенной для решения проблемы QSAT , приведен в Лита, резюме (01.09.2016). «О сложности проблемы обнаружения полиморфных вирусов ограниченной длины». 2016 18-й Международный симпозиум по символьным и числовым алгоритмам для научных вычислений (SYNASC) . стр. 371–378. дои : 10.1109/SYNASC.2016.064 . ISBN 978-1-5090-5707-8 . S2CID 18067130 .

[31] (Хопкрофт, Ульман, 1979); Упражнение S9.13, с. 230–231

[33] Калмейер, Лаура (2011). «Слегка контекстно-зависимые грамматические формализмы: естественные языки не являются контекстно-свободными» (PDF) . Архивировано (PDF) из оригинала 19 августа 2014 г.

[34] Калмейер, Лаура (2011). «Слегка контекстно-зависимые грамматические формализмы: линейные контекстно-свободные системы переписывания» (PDF) . Архивировано (PDF) из оригинала 19 августа 2014 г.

[Kallmeyer2010-35] Перейти обратно: ^а ^б Калмейер, Лаура (2010). Синтаксический анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 1–5. ISBN 978-3-642-14846-0 .

[44] $S\rightarrow ACaB$ ,

[45] $Ca\rightarrow aaC$ ,

[46] $CB\rightarrow DB$ ,

[47] $CB\rightarrow E$ ,

[48] $aD\rightarrow Da$ ,

[49] $AD\rightarrow AC$ ,

[50] $aE\rightarrow Ea$ ,

[51] $AE\rightarrow \varepsilon$ .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[примечание 1]

[заметка 2]

[заметка 3]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[примечание 4]

[24]

[25]

[26]

[27]

[примечание 5]

[28]

[29]

[30]