Гладкий - Формальные грамматики и языки - 1973 (947381), страница 7
Текст из файла (страница 7)
а) Любой непустой конечный язык ', (вь ..., оо ), емчьЛ, порождается Б-грамматикой со схемой (1- ыь ..., 1 — ооо). б) Тот же язык, если ы, = а,, ... а АР порождается А-грамматикой со схемой (Аи — »апАИ, ..., А, А,-о-рано,-~Аь о,-~ Аь Аа, -р аь А, ~ 1= 1, ..., и), '.. где А~о= ° .. — — А„о — — 1. в) Пустой язык порождается А-грамматикой со схемой (1- а1). Таким образом, любой конечный язык, не содержащий Л, является А-языком. Пример 2. Для любого словари Ь' язык )Еа порождается А-грамматикой со схемой (1- а1, 1- а1а ~ 1').
Будем называть простейшей записью натурального числа и цепочку !~...~. Множество простейших а раа записей элементов произвольного множества натуральных чисел М будет всегда отождествляться с самим множеством М. П р и м е р 3. а) Каковы бы ни были числа й = = 1, 2..., и 1= О, 1, ..., Й вЂ” 1, множество Рм —— = (йи+ 11и = О, 1, ...) (арифметическая и рог р ее с и я) порождается А-грамматикой с основным словарем (~), начальным символом А, и схемой (Ао +~Аа ° ° °, Ад-о +~А»-а АА-о +)Ао, Ао-»~Вь Ва-» -~~В», ..., В~ о- )В~ ь В~ о- )) (так при 1) 1; при 1 = 1 последние 1 правил заменяются правилом Аопри 1 = 0 — правилом АА-~ — ~ ) б) По аналогии с примером 1,б) легко построить А-грамматику, порождающую объединение конечного числа арифметических прогрессий и конечного множества чисел.
Пример 4. Язык а'Ь' порождается А-грамматикой со схемой (1- а1, 1- аВ, В- ЬВ, В- Ь). (а, Ь ее)') (а еи 'р') (а, Ь ее Ь', а Ф Ь) (а, ЬепУ; аМЬ) (а, ЬяУ) (а, ЬепУ) (1) 1-+аЕЬ (П) 1-+а (П1) 1-+ аАЬ (1У) 1 — »аЬ (Ч) А-+ аАЬ (111) А-+аЬ Действительно, всякий полный вывод в этой грамматике происходит по одной из трех схем: а) 1А П; б) 1А П1Ъ~'111; в) 1" 1Ч (й, 1= О, 1, ...); по схеме а) порождаются всевозможные цепочки нечетной длины, Пример 5. Язык (а"Ь" ~и = 1, 2, ...) порождается Б-грамматикой со схемой (1 — аЕЬ, 1- аЬ). Пример 6. Языки (ааЬ"а""~т, и = 1, 2, ...) и (а'"Ь"а" ~т, и = 1, 2, ...) порождаются Б-грамматиками со схемами (1- Еа, 1- Аа, А- аАЬ, А — +аЬ) и (1- а1, 1- аА, А- ЬАа, А- Ьа) соответственно.
П р я м е р 7. Множество всевозможных «правильных скобочных последовательностей» порождается Б-грамматикой с основным словарем (), () и схемой (1-+П, 1 (1),1 0) Пример 8. Язык Е. в словаре (а, Ь), состоящий из всех непустых цепочек, содержащих одинаковое число вхождений а и Ь, порождается Б-грамматнкой со схемой (1- 11, 1- аЕЬ, 1- Ыа, 1- аЬ, 1- Ьа). Непосредственно ясно, что все цепочки в (а, Ь), порождаемые данной грамматикой, принадлежат Е..
Обратное доказывается возвратной индукцией по длине цепочки; базис этой индукции тривиален, а индукционный шаг основывается на следующем очевидном факте: любая цепочка оо ы Е. длины, большей или равной 4, представима по крайней мере в одном из видов а$Ь, Ьо1а, чя,о, где $, П, ьь ьо еи Е,.
Для произвольной цепочки оо в словаре р' = (аь ...,ао) назовем ее о б р а щ е н и е м и обозначим й цепочку а~„... а,, если «о=а,, ... а,, и Л, если оо=Л. П р и м е р 9. а ) Язык Е,а = (хх ~ х ее Г") (з — от «зеркальное отражение») порождается Б-грамматикой со схемой (1 — аЕа, 1-+ аа1а еи 'р').
б) Язык С'Е., порождается Б-грамматикой со схемойо ПРИМГРЫ ГРАММАТИК основныв понятия Егл. 2 « 1.2! зе по схемам б) где ~со,~ = ~ы2~ н а2 Ф й» ) и в) — всевозможные цепочки вида 222ЫМ Пример !О. Язык (а"'6"а"~и= 1,2,...) дается грамматикой со схемой (1- а1Ва, 1— порож- аВ-+Ва, 6В- 66). -а а, -а6а, Действительно, каков бы ни был полн этой грамматике, в нем на одном полный вывод в ном и только на одном шаге должно применяться второе п равило, и после этого цепочка будет иметь вид а"Ьа, где ы со е ы содержит и вхожи — вхождений В. Вывод закончится лишь тогда, когда все В превратятся в 6, но для этого все В должны «собраться вместе» в сере и а„)*) порождается грамматикой со Пример 12.
Пусть Ч=(а„..., а Ь). Я (х Ьх ~х х ен(а а )' матикой со схемой: ( о ..., а»), х, чь х2) порождается Б-грам- (1) 1- 1' (П) 1-+ 1« (1П) Р-+1'а; (2'=1, ..., й) (1Ч) 1'- А;а; (Е = 1, ..., й) ('Ч) А2-»аЕА2а2 (Е, 1, 1=1, ..., й) (Ч1) А2-+аеВ (Е, 1=1, ..., й; ЕФ 1) (ЧП) В-+аеВ (1=1, ..., Й) (ЧШ)  — » Ь (1Х) А2-+Ь (Е=!, ..., 6) (Х) 1" -+С (Х1) С-»а2Сае (Е, 1=1, ..., й) (ХП) С-+а20 (1=1, ..., й) (ХП1) 0-+а,0 (1=1, ..., 6) (Х1Ч) 0-+Ь Легко видеть, что любой полный вывод в этой грамматике происходит по одной из схем: а) 1 П1 1ЧЧ'ЧЕЧП ЧП1; б) 1 П1" 1ЧЧ'1Х; в) ПХХ1АХПХП1'Х1Ч (й, 1, т О, 1...,).
По схеме а) получаются всевозможные цепочки вида х'аеу'Ьх"а2у", где х', у', х", у" ен (а„..., а»)', ! х' 1~ х" ~, 1Ф1; по схеме б) — всевозможные цепочки вида г'6г", где г', г" ен(ап ..., а»)' и !г'~(~г»|; по схеме в)— то же с противоположным неравенством. Объединение этих трех множеств цепочек и есть нужный язык. Пример 13. Множество (и'~и=1, 2, ...) порождается грамматикой со схемой; (1) 1-+ АВВОР (П) В0-»0СВ (П1) ВС вЂ” » СВ (1Ч) А0-+ ААЕ (Ч) ЕС вЂ” АЕ (Ч1) ЕВ -» ВЕ (ЧП) ЕР-+ ВВОР (ЧП1) 0Р -+ ! (1Х) В-» ! (Х) А-+ ~ (Х1) 1-+ ! Нетрудно видеть, что полный вывод в этой грамматике происходит следующим образом. Сначала из 1 по правилу 1 получается цепочка АВВ0Р = А'В2'0Р, а затем выполняется произвольное число циклов, на каждом из которых цепочка А" В'"0Р преобразуется в Аы+ РВ "+н0Р.
Цикл состоит в том, что каждое вхождение В с помощью «стимулятора» 0 порождает «двой. ник໠— вхождение С (правнло П), которое затем пере-. ходит влево (правило П1), после чего превращается в А (правило Ч) — причем до начала превращений С в А появляется ещеодно вхождение А.(правило 1Ч), — и, наконец, появляются еще два вхождения В (правило ЧП); как раз в этот момент «стимулятор» снова принимает «исходное положение».
После окончания каждого очередного цикла можно, вместо того чтобы начинать новый, применить правила Ч1П Х, превращающие А" В2" 0Р в (и+1)2. (Впрочем, правило Х можно начать За МАШИНЫ аЬЮРННГА ОСНОВНЫВ ПОНЯТИЯ $ 1.41 [ГЛ. 3 применять и раньше — это ничего не изменит). Так получается любая цепочка вида (и+1)', и ясно, что только такие цепочки в словаре Ц) выводимы из 1 по правилам 1 — Х. Цепочка >=13 получается по правилу Х!. Дальнейшие примеры «абстрактных» грамматик см, в упражнениях 1,14 и 1.15 (см. также упражнение 3.6).
Пример 14. Пусть Г = (У, 'ар', ПРЕДЛ, !г), где 1) У состоит из словоформ русского языка; 2) %' состоит из символов ПРЕДЛ, Я!худ 3!хука Аху, Ухчю 1.осп где г' = одУш, неодУш; х = мУж, жен, сР; у = ед, мн; х = им, род, дат, вин, твор, предл; ! = 1, 2, 3, 4, 5; Ч" есть произвольная подпоследовательность последовательности 12345 (возможно, пустая).
Содержательная интерпретация вспомогательныхсимволов: ПРЕДЛ вЂ” «предложение»; 84,д, — «группа существительного, одушевленного или неодушевленного в зависимости от 1, рода х в числе у и падеже э»; Еа„у,— «существнтельное» (смысл индексов тот же); А,,— «прилагательное в роде х, числе д и падеже х»; Уку— «(непереходный) глагол в изъявительном наклонении, прошедшем времени, роде х и числе у вместе с обстоятельствами тех типов (см. ниже), номера которых входят в Ч'»; 1.ос! — «обстоятельства различных типов, характеризующие движение», а именно 1.ос, — «путь» (по дороге, по воздуху), Ьосд — «отправной пункт» (иэ деревни, от реки), Ьосд — «пункт назначения» (в лес, на концерТ), Ьосл †«придорожные предметы» (мимо деревни, вдоль опушки), 1.осд — «способ передвижения» (пеидком, в карете). 3) Й состоит из следующих правил (всюду, где не оговорено противное, индексы принимают все допустимые значения): !.
ПРЕДЛ- 5!хе..У.у ! 3343 П ПРЕДЛ-+Ухну' 34хунм П1а. У у-»Уху 'Ьос! (здесь предполагается, что Ч' содержит 4; Ч" — 3' означает последовательность, получаемую из Ч' выбрасыванием !) ШП. УкуБ!куин-»Уху Е4хуим 1Ч. Уху и Уху вин, либо у =ед > если х=муж или у мн Читатель легко проверит, что язык Ь(Г) содержит такие„например, цепочки, как Ехал ямщик мимо деревни, Ехала деревня мимо ямщика, Молодая очаровательная ведьма летела на межобластной шабаш на сверхскоростном турбореактивном помеле. й 1.4.
Машины Тьюринга Машины Тьюринга н различные нх разновидности играют в теории грамматик чрезвычайно важную роль. С одной стороны, выявление связей н параллелей между теорией машин и теорией грамматик позволяет лучше понять главные идеи последней; с другой — прн научении грамматик машины Тьюринга нередко оказываются удобным техническим средством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
