Несжимающая грамматика
В формальной теории языка грамматика ) , является несжимающей (или монотонной если для всех ее правил производстваα → β (где α и β — строки нетерминальных что и терминальных символов), верно, |α| ≤ |β|, то есть β имеет по крайней мере столько же символов, сколько и α. Грамматика по существу является несжимающей, если может быть одно исключение, а именно правило. С → εгде S — начальный символ , а ε — пустая строка , и, кроме того, S никогда не встречается в правой части любого правила.
Контекстно -зависимая грамматика — это несжимающая грамматика, в которой все правила имеют вид αAβ → αγβ, где A — нетерминал, а γ — непустая строка нетерминальных и/или терминальных символов.
Однако некоторые авторы используют термин « контекстно-зависимая грамматика» для обозначения несжимающих грамматик в целом. [1]
Несжимающая грамматика, в которой |α| < |β| для всех правил называется растущей контекстно-зависимой грамматикой .
История
[ редактировать ]Хомский (1959) представил иерархию Хомского , в которой контекстно-зависимые грамматики встречаются как грамматики «типа 1»; общие несжимающие грамматики не встречаются. [2]
Хомский (1963) называет несжимающую грамматику «грамматикой типа 1», а контекстно-зависимую грамматику — «грамматикой типа 2» и, представляя преобразование первой во вторую, доказывает их слабо эквивалентность . [3]
Курода (1964) ввел нормальную форму Курода, в которую можно преобразовать все несжимающиеся грамматики. [4]
Пример
[ редактировать ]| С | → | абв |
| С | → | АСБк |
| КБ | → | до нашей эры |
| ББ | → | бб |
Эта грамматика с начальным символом S генерирует язык { а н б н с н : n ≥ 1 } , [5] который не является контекстно-свободным из-за леммы о накачке .
показана контекстно-зависимая грамматика для того же языка Ниже .
Выразительная сила
[ редактировать ]Любая контекстно-зависимая грамматика является несжимающей грамматикой.
Существуют простые процедуры для
- приведение любой несжимающей грамматики к нормальной форме Курода , [4] [6] и
- преобразование любой несжимающей грамматики в нормальной форме Курода в контекстно-зависимую грамматику.
Следовательно, эти три типа грамматики равны по выразительной силе, и все они описывают именно контекстно-зависимые языки , которые не включают пустую строку; по существу несжимающие грамматики описывают именно набор контекстно-зависимых языков .
Прямое преобразование
[ редактировать ]Прямое преобразование в контекстно-зависимые грамматики без нормальной формы Курода:
Для произвольной несжимающей грамматики ( 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 ... Х м -1 Х м → З 1 х 2 ... Х м -1 Х м З 1 х 2 ... Х м -1 Х м → З 1 З 2 ... Х м -1 Х м : З 1 З 2 ... Х м -1 Х м → З 1 З 2 ... С м -1 Х м З 1 З 2 ... С м -1 Х м → З 1 З 2 ... С м -1 С м М +1 ... Затем З 1 З 2 ... С м -1 С м М +1 ... Затем → Д 1 З 2 ... С м -1 С м М +1 ... Затем Д 1 З 2 ... С м -1 С м М +1 ... Затем → Д 1 Д 2 ... С м -1 С м М +1 ... Затем : Д 1 Д 2 ... С м -1 С м М +1 ... Затем → Д 1 Д 2 ... м -1 С м М +1 ... Затем Д 1 Д 2 ... м -1 С м М +1 ... Затем → Д 1 Д 2 ... м -1 Их М +1 ... Затем
Например, приведенная выше несжимающая грамматика для { a н б н с н | n ≥ 1 } приводит к следующей контекстно-зависимой грамматике (с начальным символом S ) для того же языка:
| [ а ] | → | а | с шага 1 | ||||
| [ б ] | → | б | с шага 1 | ||||
| [ с ] | → | с | с шага 1 | ||||
| С | → | [ а ] | [ б ] | [ с ] | начиная с шага 2, без изменений | ||
| С | → | [ а ] | С | Б | [ с ] | начиная с шага 2, без изменений | |
| из шага 2, дополнительно изменено ниже | |||||||
| [ с ] | Б | → | З 1 | Б | изменено сверху на шаге 3 | ||
| З 1 | Б | → | З 1 | З 2 | изменено сверху на шаге 3 | ||
| З 1 | З 2 | → | Б | З 2 | изменено сверху на шаге 3 | ||
| Б | З 2 | → | Б | [ с ] | изменено сверху на шаге 3 | ||
| из шага 2, дополнительно изменено ниже | |||||||
| [ б ] | Б | → | З 3 | Б | изменено сверху на шаге 3 | ||
| З 3 | Б | → | З 3 | З 4 | изменено сверху на шаге 3 | ||
| З 3 | З 4 | → | [ б ] | З 4 | изменено сверху на шаге 3 | ||
| [ б ] | З 4 | → | [ б ] | [ б ] | изменено сверху на шаге 3 |
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Для удобства неконтекстная часть левой и правой части выделена жирным шрифтом.
Ссылки
[ редактировать ]- ^ Виллем Дж. М. Левельт (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 125–126. ISBN 978-90-272-3250-2 .
- ^ Хомский, Н. 1959а. О некоторых формальных свойствах грамматик. Информация и контроль 2: 137–67. (141–42 для определений)
- ^ Ноам Хомский (1963). «Формальные свойства грамматики». В Р. Д. Люсе, Р. Р. Буше и Э. Галантере (ред.). Справочник по математической психологии . Том. II. Нью-Йорк: Уайли. стр. 323–418 . Здесь: стр. 360–363 и 367.
- ^ Перейти обратно: а б Сиге-Юки Курода (июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы» . Информация и контроль . 7 (2): 207–223. дои : 10.1016/s0019-9958(64)90120-2 .
- ^ Мэтьюз и Соломон (1997) , Пример 2.1, с. 188
- ^ Мэтьюз и Соломон (1997) , Теорема 2.2, с. 190
- ^ Мэтьюз и Соломон (1997) , Теорема 2.1, с. 187
- ^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 0-201-02988-Х . Упражнение 9.9, с.230. В издании 2003 года глава о несжимающихся/контекстно-зависимых языках была опущена.
- Книга, Р.В. (1973). «О структуре контекстно-зависимых грамматик». Международный журнал компьютерных и информационных наук . 2 (2): 129–139. дои : 10.1007/BF00976059 . hdl : 2060/19710024701 . S2CID 31699138 .
- Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты классической теории языка». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Спрингер-Верлаг. стр. 175–252. ISBN 3-540-61486-9 .