В теории формальных языков , А грамматика является несжимающей (или монотонной ) , если все его продукционными правила имеют вида α → β , где & alpha ; и & beta ; являются строками из нетерминальных и терминальных символов, а длина альфа меньше или равно β, | α | ≤ | β |, то есть β не короче α. Грамматика по существу не сжимает, если может быть одно исключение, а именно правило S → ε, где S - начальный символ, а ε - пустая строка, и, кроме того, S никогда не встречается в правой части любого правила.
Ни одно из правил грамматики без сжатия не уменьшает длину переписываемой строки. Если каждое правило даже должным образом увеличивает длину, грамматика называется растущей контекстно-зависимой грамматикой .
История
Хомский (1963) назвал несжимающую грамматику грамматикой первого типа ; в той же работе он назвал контекстно-зависимую грамматику « грамматикой типа 2» и доказал, что эти две грамматики слабо эквивалентны (в этой работе контекстно-зависимые грамматики были обозначены как «тип 4»). [1] Схема нумерации типов в этой работе Хомского 1963 года не совпадает с более ранней, известной сегодня как иерархия Хомского, потому что он пытался подчеркнуть различие между слабой [порождающей] и сильной [структурной] эквивалентностью; в своей работе 1959 года он использовал «грамматику типа 1» для обозначения контекстно-зависимой грамматики и «тип 2» для обозначения контекстно-независимой. [2] [3]
Пример
S | → | abc |
S | → | aSBc |
cB | → | До н.э |
bB | → | BB |
Эта грамматика с начальным символом S порождает язык { a n b n c n : n ≥ 1} , [4] который не является контекстно-независимым из-за леммы о накачке .
Контекстно-зависимая грамматика для того же языка показан ниже .
Преобразование в контекстно-зависимую грамматику
Каждую несжимающую грамматику ( N , Σ, P , S ) можно преобразовать в контекстно-зависимую грамматику ( N ', Σ, P ', S ) следующим образом:
- Для каждого терминального символа a ∈ Σ введем новый нетерминальный символ [ a ] ∈ N 'и новое правило ([ a ] → a ) ∈ P '.
- В правилах P замените каждый терминальный символ a его соответствующим нетерминальным символом [ a ]. В результате все эти правила имеют вид X 1 ... X m → Y 1 ... Y n для нетерминалов X i , Y j и m ≤ n .
- Замените каждое правило X 1 ... X m → Y 1 ... Y n с m > 1 на 2 m правил: [примечание 1]
Х 1 Х 2 ... X м -1 X м → Z 1 Х 2 ... X м -1 X м Z 1 Х 2 ... X м -1 X м → Z 1 Z 2 ... X м -1 X м : Z 1 Z 2 ... X м -1 X м → Z 1 Z 2 ... Z м -1 X м Z 1 Z 2 ... Z м -1 X м → Z 1 Z 2 ... Z м -1 Z м Y м +1 ... Да нет Z 1 Z 2 ... Z м -1 Z м Y м +1 ... Да нет → Y 1 Z 2 ... Z м -1 Z м Y м +1 ... Да нет Y 1 Z 2 ... Z м -1 Z м Y м +1 ... Да нет → Y 1 Y 2 ... Z м -1 Z м Y м +1 ... Да нет : Y 1 Y 2 ... Z м -1 Z м Y м +1 ... Да нет → Y 1 Y 2 ... Г м -1 Z м Y м +1 ... Да нет Y 1 Y 2 ... Г м -1 Z м Y м +1 ... Да нет → Y 1 Y 2 ... Г м -1 Г м Y м +1 ... Да нет
Например, приведенная выше несжимающая грамматика для { a n b n c n | n ≥ 1} приводит к следующей контекстно-зависимой грамматике (с начальным символом S ) для того же языка:
[ а ] | → | а | с шага 1 | ||||
[ b ] | → | б | с шага 1 | ||||
[ c ] | → | c | с шага 1 | ||||
S | → | [ а ] | [ b ] | [ c ] | с шага 2, без изменений | ||
S | → | [ а ] | S | B | [ c ] | с шага 2, без изменений | |
из шага 2, с дополнительными изменениями ниже | |||||||
[ c ] | B | → | Z 1 | B | изменено выше на шаге 3 | ||
Z 1 | B | → | Z 1 | Z 2 | изменено выше на шаге 3 | ||
Z 1 | Z 2 | → | B | Z 2 | изменено выше на шаге 3 | ||
B | Z 2 | → | B | [ c ] | изменено выше на шаге 3 | ||
из шага 2, с дополнительными изменениями ниже | |||||||
[ b ] | B | → | Z 3 | B | изменено выше на шаге 3 | ||
Z 3 | B | → | Z 3 | Z 4 | изменено выше на шаге 3 | ||
Z 3 | Z 4 | → | [ b ] | Z 4 | изменено выше на шаге 3 | ||
[ b ] | Z 4 | → | [ b ] | [ b ] | изменено выше на шаге 3 |
Выразительная сила
Точно так же существует простая процедура для приведения любой несжимающей грамматики в нормальную форму Куроды . [7] [8] И наоборот, каждая контекстно-зависимая грамматика и каждая грамматика нормальной формы Куроды тривиально также является несжимающей грамматикой. Следовательно, неконтактные грамматики, грамматики в нормальной форме Курода и контекстно-зависимые грамматики обладают одинаковой выразительной силой. Чтобы быть точным, грамматики без контракта описывают в точности контекстно-зависимые языки, которые не включают пустую строку, в то время как грамматики без контракта описывают точно набор контекстно-зависимых языков .
Смотрите также
Заметки
- ^ Для удобства неконтекстная часть левой и правой части выделена жирным шрифтом.
Рекомендации
- ^ Ноам Хомский (1963). «Формальные свойства грамматики». В RD Luce и RR Bush and E. Galanter (ed.). Справочник по математической психологии . II . Нью-Йорк: Вили. стр. 323 -418. Здесь: стр. 360–363 и 367.
- ↑ Хомский, Н. 1959a. О некоторых формальных свойствах грамматик. Информация и контроль 2: 137–67. (141–42 для определений)
- ^ Виллем Дж. М. Левелт (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. С. 125–126. ISBN 978-90-272-3250-2.
- ^ Mateescu & Salomaa (1997) , пример 2.1, стр. 188
- ^ Матееска & Salomaa (1997) , теорема 2.1, стр. 187
- ^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 0-201-02988-X.Упражнение 9.9, стр. 230. В издании 2003 г. была опущена глава о недоговорных / контекстно-зависимых языках.
- ^ Сигэ-Юки Курода (июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы» . Информация и контроль . 7 (2): 207–223. DOI : 10.1016 / s0019-9958 (64) 90120-2 .
- ^ Матееска & Salomaa (1997) , теорема 2.2, стр. 190
- Книга, Р. (1973). «О структуре контекстных грамматик». Международный журнал компьютерных и информационных наук . 2 (2): 129–139. DOI : 10.1007 / BF00976059 . ЛВП : 2060/19710024701 .
- Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты теории классического языка». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Springer-Verlag. С. 175–252. ISBN 3-540-61486-9.