Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Замечание. Из теоремы 1.5 и известной теоремы Поста (см., например, [Kleene 1952], стр. 237 русского перевода), в силу которой множество тогда и только тогда рекурсивно, когда оно само и его дополнение рекурсивно перечислимы, следует—поскольку существуют нерекурсивные рекурсивно перечислимые множества — замечание, сделанное в конце § 1.2.
*) Обычно в курсах теории алгоритмов с помощью машин Тьюринга определяются только числовые частично рекурсивные функции, а «словарные» частично рекурсивные функции вводятся с помощью нумерации цепочек. Не составляет большого труда доказать равносильность такого определения используемому нами «непосредственному» (точные формулировки см. в упражнении 1.21).
50
ОСНОВНЫЕ понятия
[ГЛ. г
Упражнения
1.1. Подсчитать число вхождений подцепочек в цепочку длины п.
1.2. Доказать, что для произвольных цепочек ф и tji тогда и
только тогда фор = \|>ф, когда существуют цепочка ю и числа
т, п — 0, 1, ... такие, что ф = ат, ф = со".
1.3. Пусть V = {аи ..., ак] — некоторый словарь. Сопоставим
каждой цепочке (о е V* число v(w) следующим образом: v(A) = 0;
) = ?"-I./I+ ... + k2 ? in_2 + k • in_! + in. (He смешивать с обычным представлением натурального числа в системе счисления! В чем разница?)
Показать, что v — взаимно однозначное отображение V* на
N — {0, 1, ...} и что г(ф) <v(i|)) тогда и только тогда, когда ф предшествует ф в смысле стандартного порядка, отвечающего пересчету а\, ..., ак.
1.4. а) Доказать, что L(L\ U L2) = LL\ U LL2, (L{ U L2)L = = LXL U L2L.
б) Имеют ли место аналогичные тождества для пересечения?
1.5. Сформулировать строгие (индуктивные) определения многочлена и регулярного выражения.
1.6. Представить с помощью бескоэффициентных регулярных выражений от языков {<3i}, ..., {a„}, {Л}:
а) множество цепочек, содержащих вхождения данной непустой цепочки a> = a^ ... at\
б) множество цепочек, начинающихся (оканчивающихся) вхождением данной непустой цепочки со = а, ... а, ;
1 lS
в) множество цепочек, не содержащих вхождений цепочки © = а, *.. а, ;
ч ls
г) множество цепочек, содержащих ровно k вхождений цепочки
*1
1.7. Показать, что для всякого регулярного выражения
<p(Sj, lk) найдется такое выражение -ф (|г =
= f(g*i (ii> • ••> h)..8s (?i> • • •• h)’ ?i> • • •• Ik) (s>°)> Где f,
gi> •••> gs— многочлены, что для любых k языков Li, ..., Lk, каждый из которых содержит пустую цепочку, q>(Li, ..., Lk) = = ф (Z-j, ..., Lk). При этом, если ф не содержит коэффициентов, то это же верно для f, gv ..., gs.
1.8. Выразить объединение, умножение и итерацию языков через подстановку.
1.9. Для того, чтобы каждому выводу в грамматике Г соответствовал единственный размеченный вывод, необходимо и достаточно, чтобы схема Г не содержала правил ф1->г|)1, ф2 -> ф2> Удовлетворяющих одному из следующих двух условий: (i) ЗюЗа/ (о>й/=И=Л &ф2 = о>ф1й/ & г|)2 = CD^jCD'); (ii) 3ф{3ф?3?30[ф, = ф(?&ф2=
= ?ф? & (ф[ = ^0 & фз = 0^2 V "фд = ф)0 & ^ = & Ф1Ф2 ^ .
Доказать,
УПРАЖНЕНИЯ
51
1.10. Назовем характеристикой вывода [Огоцкий 1967] *) последовательность применяемых в этом выводе правил; аналогично для размеченного вывода. (Размеченный вывод имеет, очевидно, единственную характеристику.) Показать, что в грамматике тогда и только тогда существуют различные размеченные выводы с одинаковыми характеристиками, отвечающие одному и тому же выводу, когда ее схема содержит правило вида Фт -*? Ф" (т, п = 0, 1, ...)?
1.11. Могут ли полные выводы в одной и той же грамматике, оканчивающиеся разными цепочками, иметь одинаковые характеристики?
1.12. Назовем вывод в грамматике Г= (V, W, /, R) приведенным налево, если на каждом его шаге соответствующее правило применяется к самому левому вхождению своей левой части (при подходящей разметке вывода). Множество цепочек из V*, выводимых в Г из / с помощью выводов, приведенных налево, обозначим Lji (Г). Показать, что:
а) для произвольной грамматики Г можно построить **) такую грамматику Г7, что L(T) = Ljj(r'); если при этом Г — НС-грамма-тика, то и Г' можно сделать НС-грамматикой;
б) если Г — Б-грамматика, то ?(Г) = (Г).
1.13. Назовем грамматикой со стоп-правилами упорядоченную четверку А = {V, I, R, R'), где V — конечное множество, / s V, R — конечное множество правил такого ‘же вида, как правила обычной грамматики, и R' — подмножество R («множество стоп-правил»). Вывод в А (вывод определяется, как для обычной грамматики) назовем 1-выводом, если в нем применяются только правила из R — R' и к его последней цепочке никакое правило из R не применимо, и 2-выводом, если на всех его шагах, кроме последнего, применяются правила из R — R', а на последнем — правило из R'. Множество цепочек, выводимых из / с помощью 1-(2-) выводов, обозначим Z-i (A) (Z-2 (А)). Показать, что:
а) для любой грамматики Г можно построить такие грамматики со стоп-правилами Д, Дь Аг, что L(T) = Li(A) 1)?г(А) = Z-i(Д1) = = L2( Д2);
б) для любой грамматики со стоп-правилами А можно построить такие грамматики Г, Г[, Гг, что i-i(A) UL2(A) = Z- (Г), Li(A) = = L(rO, L2(A) = /.(Гг).
