Гладкий - Формальные грамматики и языки - 1973 (947381), страница 6
Текст из файла (страница 6)
188), но «охрипнем сокращение, ставшее уже общеупотребительным. «') Иногда используется термин «гркмматика с конечным числам состояний», по нашему мнению, неудачный (см, [Глкдкнй — Мельчук ГРАММАТИКИ ОСНОВНЫЕ ПОНЯТИЯ 1ГЛ. 80 имеет вид А — аВ или А - а, где А,  — вспомогател ные символы и а — основной символ. Языки, порождаемые НС-, Б- и А-грамматиками, на зываются соответственно НС-, Б- и А-я з ы к а м и. Классы произвольных грамматик, НС-, Б- и А-грам матик мы будем иногда обозначать соответственно че рез Г (так же мы часто обозначаем конкретные грамма тики, однако эта омонимия всегда устраняется контек етом), НС, Б и А. Кроме того, для произвольного класс грамматик У через 2" (У ) будет обозначаться клас языков, порождаемых грамматиками класса В .
Приме ры НС-, Б- и А-грамматик будут приведены в $1.3. Введем еще некоторые понятия н отметим несколь' ко полезных для дальнейшего простых фактов. Правило гр- «р грамматики Г называется з а к л ю ч и тел ь н ы м, если «р~А и никакой символ, входярдий в «(г не может входить в левую часть какого-либо правила Г. Перестройкой вывода 0 = (сзз, взг, ..., ш„): в грамматике Г мы будем называть (вообще говоря многозначную) операцию, сопоставляющую выводу 0 какой-либо другой вывод цепочки ш„из свз в Г, в котором применяются в точности те же правила, что и в 0„ но в другом порядке. Л ем м а 1.1, Всякий вывод в произвольной грамма тике можно перестроить так, чтобы ни одно заключ тельное правило не применялось раньше какого-либ незаключительного.
Доказательство очевидно. Пусть (шэ, ш'„..., гв'„Р ш„), где ш',. = 9,. «гр, э т)' (О ( 1( и), — размеченный вывод в некоторой грамма тике, и пусть правило, применяемое на 1-м шаг (1=1, ..., п), есть грг г- «рз г. Тогда для каждого 1 = 1, ..., и — 1 имеет место Равенство йпР«т)г = 9«зфг гт)г б при этом выделенное вхождение г)ч может находиться либо целиком левее выделенного вхождения «рг ь либо целиком правее, либо пересекаться с. ним.
В этих случаях мы будем говорить соответственно,- что !+ 1-й шаг данного размеченного вывода п ро ис-- 19б91, стр. 184). Лучше всего было бы, пожалуй, говорить «конечко. автоматная грамматика», поскольку А грамматики тссяо связаны с к оп с як ы м в автоматами (см. ниже, й 51), вс мы вс будем' этого делать, чтобы нв увелвчвввть в бсз того слишком большов' число термквплогвческвх вариантов ход одит левее гго, происходит правее 1-го, за- цепЛЕН С 1-М. Назовем размеченный вывод у п о р я д о ч е н н ы м, если никакой следующий шаг не происходит в нем левее предыдущего. Вывод, становящийся при подходящей раз- метке упорядоченным, назовем у п о р я д о ч и в а е м ы м. Л е м м а 1.2. Всякий велвод в произвольной грал«ма- тике можно перестроить в упорядочиваемый.
l г Д оказ атель ств о. Пусть 0'=(ыс, ..., ш„и гв„), где ьз'.=$, э<р, «Ч, (О(! < и), — неупорядоченный раз- ГДЕ ЬЗ,— 9, « меченный вывод в грамматике Г и !э=!с(0) — наи- меньшее из чисел 1, для которых !+1-й шаг в 0' про- исходит левее г-го. Очевидно, ~ йи, ~ '-Ъ(5, «рг ~. Пусть 1 — наименьшее число, обладающее тем свойством, что с для каждого ), удовлетворяющего условию !э » (! ( !с, выполняется неравенство ~ 91, ~ ) ~ 9, ~, ~. Для каждого 1=!с, !э+1, !эимеемй1-~~р1 Лу-~=йг,р,,в1 РТ,Ч1 и Преобразуем 0' следующим образом: шаги до ),— 1-го включительнооставим без изменения, затем в полученной таким образом цепочке 9, ~р, $',гр,з)1, применим к выв 0' деленному вхождению ~рг правило, применявшееся в иа гэ+ 1-м шаге, затем будем производить все за- мены, как на шагах 0' от )э-го до гэ-го включительно,— после чего, очевидно, получится цепочка Ц, Чз,т), — и, 0'О наконец, преобразуем эту цепочку в вз„, как в О.
Ясно, что такое преобразование дает новый размеченный вы- вод 0" в Г, и если он не упорядочен, то гэ(0 ) > гэ(0 ). Повторяя это преобразование нужное число раз, получим упорядоченный размеченный вывод. Два вывода в грамматике Г назовем р а в н о с и л ь- и ы м и, если их первые и последние цепочки соответ- ственно совпадают. Вывод, в котором никакая цепочка не встречается бо- лее одного раза, назовем б е с п о в т о р н ы м. Л е м м а 1.3.
Для произвольного вывода в любой грамматике суи)ествует равносильный ему бесповгорный вывод, который можно получить из исходного выбрасы- ваниелг некоторых цепочек. Доказательство очевидно. Грамматики Г. и Г' называются э квивалентны- ми, если Ь(Г) !.(Г'). ПРИМЕРЫ ГРАММАТИК а ьз! !Гл. основные понятия 2 А. В. Гаадкяз Лемма 1.4.
Для произвольной грамматики Г жег быть построена *) эквивалентния ей грамматика Г, левые части правил которой не содержат вхождени основных символов. Если при этом à — НС-грамматик то и Г' может быть сделана НС-грамматикои. Доказательство. Пусть Г = (У, )Р',1,к). Сопо, ставим каждому символу а ~ У «двойник໠— новы символ а уй У 0 )У вЂ” так, чтобы разным символам от вечали разные «двойники». Положим Р=(а!а~ У) Г'=(У, )У()У, 1, ДОЩ, Где й=(а- а~!аенУ) и получается из Д заменой в каждом правиле все вхождений основных символов вхождениями их «двой ников». Легко видеть, что Г' и есть нужная грамматика В грамматике, удовлетворяющей условию леммы 1.4, каждое правило, правая часть которого непуста и со . стоит нз основных символов, является заключительным.
Пусть У вЂ” некоторый класс грамматик и ср — й-местная операция над языками. Допуская языковую воль- ' ность, будем говорить, что класс ль(У ) з ф ф е к т н в но: вам кнут относительно гр, если по любым й грамма-,';. тикам Гь ..., ГА ен!Г можно постРоить такУю гРамма-.' тику Г ен Ьг, что 1,(Г) = ~р(Е(Г«), ..., Е(ГА)) *"). Теорема 1.1. Класс язвите, порождаемых всевоз- ' иожнылги грамматиками, эффективно замкнут относительно операций объединения, пересечения, умножения,, итерации, усеченной итерации, левого и правого деления, и подстановки. Доказательств о. 1) Пусть Г' = ( У', %", 1', Д') и Г" = (У",)У",!",Д") — произвольные грамматики. В силу леммы 1.4 мы можем считать, что левые части правил Г' и Г" не содержат вхождений основных симво. лов.
Будем считать, кроме того, что )У'Д Ф'л = кэ; если зто не так, переименуем символы, входящие в И", что не изменит языка Е(Го). При выполнении зтнх условий очевидно, что грамматики (У, Ф, 1, Д () Дэ 0 (! -+ 1', ') «Постронть» будет нз протяжении всей книги означать «эфектнвно постронть». Здесь, например, «по произвольной грзммагнке может быть построенз Г'» овнзчзет «сунгествует алгоритм, строяпгнй по произвольной грзммвгнке Г нужную Г'»; в дзльнейюем всюду аналогично. »а] Таким обрезом, эффективная замкнутость есть нв свмом деле свойство класса У'; з не класса ж'(К).
1")) (У, )«,1, )('() Дм0 (1- !'1")), где У= =* У' 0 Ум Ф'= Ф" 0 %™ 0 (1), 1Ф У' У" 0(Р'() )Р", ! 1. Г" и порождают соответственно языки 1. (Г ) Е(Г')Е(Гь). Чтобы построить грамматику, порождаюю пересечение, сопоставим взаимно однозначным об- щую разом каждому символу а ~ У новый символ и I а каж- дому символу Ь е= Ум новый символ Ь.
Положим У'= = (а!а ~ У), У" = (Ь~Ь ен У ) (У'П УУЬ' = кг). Обо- значим через Д', соответственно через Д", множество прави , л, полученное из Д' (нз Д") заменой каждого ж ое вхождения каждого основного символа а в ка д п авила вхождением символа а(а). Пусть теперь 1 Ф У' 0 У ь () У' () У ь () Ю' () %'м и Г=(У'ПУ", )У'() )Уп()У'()Ум()(1), 1, !!'() Дм() ()(1 !'1л)() Д,()а>, где й,=(аЬ- Ьа ~аяУ', бенуа), !Гз=(аа — а (аееУ'ПУ"). Нетрудно видеть, что Е(Г) =1,(Г')П1.(Г"). 2) Пусть Г=(У, Ю, 1, Д) — произвольная грамма- тика.
Как и выше, считаем, что левые части ее правил не содержат вхождений основных символов. Пусть х — про- извольная цепочка из У". Положим 1У = ',, д где Р,4~ ~У () )У, д =(1-4~14Р,4ф 4Р-4ф14ф,4ф 4Р-Л) () ()(Чра — »ацр !аееУ), Д„=(!'-» Чр1, Чфх-»Л). Легко / 1/ и видеть, что грамматики Г = Г, == (У, Я7', 1', Я () к,) порождают соответственно языки Е(Г)+ и х'~Е (Г). Чтобы получить язык Е(Г)', достаточно добавить к схеме грамматики Г' правило !1-+Л.
Грам- матика для Е(Г),"х строится аналогично Г„. 3) Доказательство для подстановки предоставляется читателю. 3 а м е ч а н и е. Относительно операций вычитания и взятия дополнения рассматриваемый класс языков не 1.4 . замкнут (см. ниже замечание в конце $ . ). к ! й Примеры грамматик Во всех приводимых здесь и далее примерах грамматик мы у б дем, если не оговорено противное, обознаб квами, чать основные символы строчными латинскими у основные понятия 1гл. о ', З4 пРимеРы ГРАммлтик О ь»1 вспомогательные — заглавными латинскими буквами (те и другие буквы могут иметь индексы н надстрочные знаки), начальный символ — буквой 1. Это позволит нам ограничиться выписыванием схем грамматик. П р и м е р 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
