Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
п раз
записей элементов произвольного множества натураль-ных чисел М будет всегда отождествляться с самим множеством М.
Пример 3. а) Каковы бы ни были числа k — = 1, 2, ... и / = 0, 1, ..., k — 1, множество Рщ — = {kn1\п = 0, 1,...} (арифметическая прогрессия) порождается А-грамматикой с основным словарем {[}, начальным символом Л0 и схемой {Ао —*-\Ai, ..., Ak-2—*\Ak-i, Ak-i —*-1/40, Ло—*-|Si, Z?i->
—>|B2, ..., Bi—2 * |B;_j, Bi-i-+1} (так при / > 1; при I — 1 последние / правил заменяются правилом А0—*? |, при 1—0 — правилом Au-i —? |).
б) По аналогии с примером 1, б) легко построить А-грамматику, порождающую объединение конечного числа арифметических прогрессий и конечного множества чисел.
Пример 4. Язык а+Ь+ порождается А-грамматикой со схемой {/ —у al, I —? аВ, В —? ЬВ, В —? Ь}.
ПРИМЕРЫ ГРАММАТИК
35
Пример 5. Язык {anbn\n = 1, 2, ...} порождается Б-грамматикой со схемой {l-+alb, /—>ab).
Пример 6. Языки {anbnam\m, п~ 1, 2, ...} и {ambnan\m, п= 1, 2, ...} порождаются Б-грамматика-ми со схемами {/—*Ia, I —? Аа, A-+aAb, А-+аЬ} и {/ —>? al, I —* аА, А —*? ЬАа, А —? Ьа) соответственно.
Пример 7. Множество всевозможных «правильных скобочных последовательностей» порождается Б-грамматикой с основным словарем {), (} и схемой {/->//, /-(/),/-*()}.
Пример 8. Язык L в словаре {а, Ь}, состоящий из всех непустых цепочек, содержащих одинаковое число вхождений а и Ь, порождается Б-грамматикой со схемой {/ —у II, I —* alb, I ~*Ыа, I -+ab, I-+ba}.
Непосредственно ясно, что все цепочки в {а, b}, порождаемые данной грамматикой, принадлежат L. Обратное доказывается возвратной индукцией по длине цепочки; базис этой индукции тривиален, а индукционный шаг основывается на следующем очевидном факте: любая цепочка со eL длины, большей или равной 4, представима по крайней мере в одном из видов а\Ь, Ьца, S1S2, где 1, г], ?1, L.
Для произвольной цепочки со в словаре V — {аи .., ... ,аъ.} назовем ее обращением и обозначим 6 цепочку a,in ... ati, если © = ai( ... ain, и А, если со = Л.
Пример 9. а) Язык L3 — {хх\х^ К+} (з — от «зеркальное отражение») порождается Б-грамматикой со схемой {/-*? ala, / -? aa | a <= V}.
б) Язык C'L3 порождается Б-грамматикой со схемой:
(I) 1->а1Ь (a, beEV)
(И) /->а (аеУ)
(III) /->аЛЬ (a, ieK; аф Ь)
(IV) /-*аЬ (а, 6 е V; а Ф Ь)
(V) А -* aAb (a,b(=V)
(VI)A-+ab (a, 6eF)
Действительно, всякий полный вывод в этой грамматике происходит по одной из трех схем: а) lh II;
б) I* IIIV* VI; в) Ift IV (k, / = 0, 1, ...); по схеме а)
порождаются всевозможные цепочки нечетной длины,
2*
36
ОСНОВНЫЕ понятия
[ГЛ. I
по схемам б) и в)—всевозможные цепочки вида (О1Ы2, ГДе | (Oi | = | (02 | И (02 Ф «1.
Пример 10. Язык {anbnan\ti = 1, 2,...} порождается грамматикой со схемой {I-+aIBa, I —? aba, аВ -* Ва, ЬВ —*• bb}.
Действительно, каков бы ни был полный вывод в этой грамматике, в нем на одном и только на одном шаге должно применяться второе правило, и после этого цепочка будет иметь вид апЬа>, где со содержит п вхождений а и п — 1 вхождений В. Вывод закончится лишь тогда, когда все В превратятся в Ь, но для этого все В должны «собраться вместе» в середине цепочки.
Пример 11. Пусть V = {aj, ..., ak, b}. Язык {xbx I x e {au ..., an}*} порождается грамматикой со схемой {1-*1А{й{, 1 —? b, aiAj-+Ajai, ЬАг-^аф\1,
/= 1, .... к).
Пример 12. Пусть V = {a,........... ak, b}. Язык
{х{Ьх2 \х1,х2^{а1, ..., ak}*, х1 Ф х2} порождается Б-грам-матикой со схемой:
(I) /->/'
(II) /-*/"
(III) /'->/4-
(IV) I'-+Aiat (1= 1, ..., ft)
(V) Ai-+ajAiai (i, j, 1=1, ..., ft)
(VI) At а,В (г, j = 1.ft; 1Ф j)
(VII) В-+a,B (/== 1....ft)
(VIII) B~> b
(IX) At->b (i = 1.......ft)
(X)/"-*C
(XI) C-*atCaj (i, j— 1.........ft)
(XII) C->a,?> (f=l......ft)
(XIII)D—>afD (t=l, ft)
(XIV) D^b
Легко видеть, что любой полный вывод в этой грамматике происходит по одной из схем:
а) I III* IV V* VI VIP VIII; б) I IIIй IV V'IX;
в) IIXXIfeXIIXIII1 XIV (k, I, tn — Q, 1,
ПРИМЕРЫ ГРАММАТИК
ЗГ
По схеме а) получаются всевозможные цепочки вида x'aly'bx"aly", где х', у', х", у'' «ее {alt ak}*, | х' Н х" \,
i Ф j; по схеме б) — всевозможные цепочки вида z'bz", где z', z" ^{аи ..., ak}* и [ z' | < [ z" |; по схеме в) — то же с противоположным неравенством. Объединение этих трех множеств цепочек и есть нужный язык.
Пример 13. Множество {п2\п=\, 2, ...} порождается грамматикой со схемой:
(I) I-> ABBDF
(И) BD -? DC В
(III) ВС-+СВ
(IV) AD -> ААЕ
(V) ЕС -> АЕ
(VI) ЕВ-+ВЕ
(VII) EF-+BBDF
(VIII) DF-+ |
(IX) в -> |
(X) Л-Ч
(XI) /-Ч
Нетрудно видеть, что полный вывод в этой грамматике происходит следующим образом. Сначала из 1 по правилу I получается цепочка ABBDF = Al*B2iDF, а затем выполняется произвольное число циклов, на каждом из которых цепочка An!B2nDF преобразуется в д(п+1?д31п+1)рр Цикл состоит в том, что каждое вхождение В с помощью «стимулятора» D порождает «двойника»— вхождение С (правило II), которое затем переходит влево (правило III), после чего превращается в А (правило V) — причем до начала превращений С в А появляется еще одно вхождение А. (правило IV), —и, наконец, появляются еще два вхождения В (правило VII).; как раз в этот момент «стимулятор» снова Принимает «исходное! положение». После окончания каждого очередного цикла можно, вместо того чтобы начинать новый, применить правила . УЩт—X, превращающие An*B2nDF в (n-fl)2. (Впрочем, правило X можно начать
