Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
ВСВСА, ВСВСВСА, BCDCA, BCDCBCA, BCDCbcA, BCabcA, bcabcA, bcabc). Соответствующий размеченный вывод (в данном случае единственный): (*Д *, ВС *, ВСВС* А «, ВС * ВСВ * СА, BCDC * А *, BCDC * ВС*А, BC*DC*bcA, *BC*abcA, bcab*cA*, bcabc). Легко видеть, что L(T) = {а, Ьс}+.
Грамматика T=(V,W,I,R) называется грамматикой составляющих, или НС-гр а м м а т и к о й *), если каждое ее правило имеет вид ?И?2—1 где 1и |2 — произвольные цепочки в словаре V (J W, /1е^и 0 — произвольная непустая цепочка в V U W.
Правила вида \iA\2-+l$h, где h, |г, А и 0 имеют указанный только что смысл, иногда называют НС-п р а-вилами; цепочка gi, цепочка Ъ. и пара цепочек (gi, g2) называются соответственно левым контекстом, правым контекстом и контекстом НС-прави-ла 1И^2 —*? ?i6?2. При применении НС-правила фактически заменяется только одно вхождение символа А, но возможность замены зависит от наличия нужного контекста. Если = |г = А, то правило называется бесконтекстным (или контекстно-свободным), сокращенно Б-правилом (или КС-правилом).
НС-грамматика называется бесконтекстной (или контекстно-свободной), сокращенно Б-rp а м м а т и к о й (или КС-гр а м м а т и ко й), если все ее правила бесконтекстные.
(Б-)грамматика называется автоматной, сокращенно А-гр ам м а т и ко й **), если каждое ее правило
*) Вместо «грамматика составляющих» часто говорят «грамматика непосредственно (или непосредственных) составляющих»; отсюда и сокращение «НС-грамматика». Мы опускаем слово «непосредственно», так как никаких других составляющих не бывает (ср. [Гладкий — Мельчук 1969], стр. 185), но сохраняем сокращение, ставшее уже общеупотребительным.
**) Иногда используется термин «грамматика с конечным числом состояний», по нашему мнению, неудачный (см. [Гладкий — Мельчук
30
ОСНОВНЫЕ понятия
1ГЛ.
имеет вид А -* аВ или А —*? а, где А, В — вспомогател ные символы и а — основной символ.
Языки, порождаемые НС-, Б- и А-грамматиками, на зываются соответственно НС-, Б- и A-я зыками.
Классы произвольных грамматик, НС-, Б- и А-грам матик мы будем иногда обозначать соответственно че рез Г (так же мы часто обозначаем конкретные грамма тики, однако эта омонимия всегда устраняется контек стом), НС, Б и А. Кроме того, для произвольного класс грамматик через 9? {3~) будет обозначаться клас языков, порождаемых грамматиками класса 0~. Приме ры НС-, Б- и А-грамматик будут приведены в § 1.3: Введем еще некоторые понятия и отметим несколь ко полезных для дальнейшего простых фактов.
Правило ф—ир грамматики Г называется заключи, тельным, если и никакой символ, входящий в
не может входить в левую часть какого-либо правила Г* Перестройкой вывода D= (юо, coi, ..., (on) в грамматике Г мы будем называть (вообще говоря' многозначную) операцию, сопоставляющую выводу D какой-либо другой вывод цепочки а„ из ыо в Г, в кото* ром применяются в точности те же правила, что и в D* но в другом порядке.
Лемма 1.1. Всякий вывод в произвольной грамма; тике можно перестроить так, чтобы ни одно заключ тельное правило не применялось раньше какого-либ незаключительного. Доказательство очевидно.
Пусть (во', ..., <*>„), где а' = g, * <р, * rfc
(0 ^ i С п), — размеченный вывод в некоторой грамма тике, и пусть правило, применяемое на г-м шаг (i=l, п), есть фг—1 —»? "фг—1- Тогда для каждого
t = l, п—1 имеет место равенство ?гфгГ]г =
= при этом выделенное вхождение <р* мо-
жет находиться либо целиком левее выделенного вхождения г|з*_1, либо целиком правее, либо пересекаться с, ним. В этих случаях мы будем говорить соответственно,* что t+ 1-й шаг данного размеченного вывода проис-*
1969], стр. 184). Лучше всего было бы, пожалуй, говорить «конечноавтоматная грамматика», поскольку А-грамматики тесно связаны с конечными автоматами (см. ниже, § 5.1), но мы не будем' этого делать, чтобы не увеличивать и без того слишком большой число терминологических вариантов
ГРАММАТИКИ
31
ходит левее i-го, происходит правее t'-ro, зацеплен с г-м.
Назовем размеченный вывод упорядоченным, если никакой следующий шаг не происходит в нем левее предыдущего. Вывод, становящийся при подходящей разметке упорядоченным, назовем упорядочиваемым.
Лемма 1.2. Всякий вывод в произвольной грамматике можно перестроить в упорядочиваемый.
Доказательство. Пусть D' = (со', ..., соп), где (о' = |(. *фг *г|г (0 ^ г < п), — неупорядоченный размеченный вывод в грамматике Г и г0 = i0(D') — наименьшее из чисел г, для которых г + 1-й шаг в D' происходит левее г'-го. Очевидно, | g.Q_, | 1гоф(-о|- Пусть
j0 — наименьшее число, обладающее тем свойством, что для каждого /, удовлетворяющего условию j0 ^ ^ г0> выполняется неравенство 1| ?гоФго|- Для каждого / = /0. /0+ г'о имеем|/_1Ф/_1т]у_1”=|г|)фг(11у_1ф/_1г1/_1-
Преобразуем D' следующим образом: шаги до jQ— 1-го включительно оставим без изменения, затем в полученной таким образом цепочке ^г-0Фг0Е/0_1Ф/0_1'П/0_1 применим к выделенному вхождению фго правило, применявшееся в D' на t0 + 1-м шаге, затем будем производить все замены, как на шагах D' от jo-то до /о-го включительно, — после чего, очевидно, получится цепочка ^ф^д.^ — и, наконец, преобразуем эту цепочку в со„, как в D'. Ясно, что такое преобразование дает новый размеченный вывод D" в Г, и если он не упорядочен, то io(D") > io(D'). Повторяя это преобразование нужное число раз, получим упорядоченный размеченный вывод.
