Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ 6.2, Нормальная форма Б-грамматики
Замечание 2 к теореме 6.1 мы используем для доказательства следующей теоремы о Б-грамматиках.
Теорема 6.2 (теорема о нормальной форме). Для всякой Ъ-грамматики можно построить эквивалентную ей Ъ-грамматику, все правила которой>имеют один из следующих видов: А—*-а, А-+аВ, А->аВС, где А, В, С — вспомогательные символы и а — основной символ.
Доказательство. Пусть Г° = (V°, W°,/°,R0) — стандартная бинарная Б-грамматика. Будем сопоставлять символам из W0 (не обязательно всем) числа, которые назовем их левыми степенями, следующим образом: (i) левая степень считается равной нулю для тех А е ддя которых не существует правил вида А -* -* ВС (так что всякое правило с левой частью А имеет вид А г± а, где aeF°); (ii) если для каждого k = О, ,..
5 6.2]
НОРМАЛЬНАЯ ФОРМА,Б-ГРАММАТИКИ
197
..., п-1 определено понятие символа левой степени k, то символу A e-W70 приписывается левая степень п, если ему не приписано в качестве левой степени ни одно из чисел 0, ..., п — 1 и в каждом правиле вида А —*? -+ВС, В, С е W0, символ В имеет левую степень, меньшую п.
Если всем символам из W° можно приписать левые степени и наибольшая из них равна N, будем называть Г° грамматикой левой степени N. Ясно, что если Г° — приведенная грамматика, то она имеет левую степень N тогда и только тогда, когда N есть точная верхняя граница длин левых путей в деревьях полных выводов в Г°.
Пусть теперь Г — произвольная Б-грамматика с основным словарем V. По замечанию 2 к теореме 6.1 можно построить эквивалентную Г стандартную бинарную Б-грамматику Г1 = {V, Wl,I\ R1) такую, что дли-«ы левых путей в деревьях полных выводов в Г1 не превосходят 2. Перейдем от Г1 к эквивалентной приведенной грамматике Г° = (V, IP, /°, R0), где FsF и R°^Rl (лемма 4.8). При этом множество деревьев полных выводов не изменится, и по предыдущему Г° будет грамматикой левой степени, не превосходящей 2.
Пусть r = A~*BC^R°. Тогда левая степень символа В равна 0 или 1. Сопоставим правилу г всевозможные правила вида А —*? ЬС, где V и В —? 6 е R0, а если левая степень В равна 1, — еще и всевозможные правила вида А—*Ь\В2С, где Ь\ и В2 удовлетворяют условию
6, е= V & В2 е Г° &
& (3 Si е= W°) [В В,В2 е R° & Bi -* b{ e= R°]
Если заменить в Г° каждое правило вида А—*ВС совокупностью сопоставленных ему новых правил, то полученная грамматика будет, очевидно, эквивалентна Г°, а следовательно, и Г. Доказательство закончено.
Грамматика, удовлетворяющая требованию теоремы 6.2, называется Б-грамматикой в нормальной форме Грейбах (или просто в нормальной форме).
Теорему 6.2 можно усилить следующим образом.
198 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
Т*е орема 6.3. Для всякой Ъ-грамматики Г и всякого целого положительного числа s можно построить Ъ-грамматику Г' ={V,W', Г, R'), эквивалентную Г, все правила которой имеют один из следующих видов:
А -> х, А->уВ, А-> у ВС, где А, В, С е W',
х, t/e=y+,UKs, \y\ = s.
Доказательство. Пусть T = {V,W,I,R) — Б-грамматика в нормальной форме. Если | х | = s,Ief и цепочка хХ выводима в Г из Л, то jXj^s + 1. Сопоставим каждой цепочке Хе87+,
I X |<!s + 1, новый символ Р(Х); совокупность всех таких символов обозначим W. Пусть Г/==(У, W, р (/), R'), где R' состоит из всевозможных правил следующих видов:
1) р(Л, ... Ак)-+х, где l=^?^s + l; | х | ^ s; А\ ... Ак I— х;
2) р(Л, ... Ak)^»y$(At+l ... Ак), где 1 < г < ? < <s+ 1;\у | = s; Л, ... Лг I- у;
3) Р(Л, ... Ak)^>-uv§(Z)§{Ai+l ... Ак), где 1<г'< <С k ^ s Ц- 1; | uv | = s\ Z (= W , Ах ... Ai_i 1— и\ А{ 1— vZ\
4) Р(Л! ... Ак)-> uv$(Z), где 1 <k + 1; | uv | = s\ Z ?= W+] Aj ... Ак—i Ь- u\ Ак 1— vZ.
г г
Эти правила строятся по R эффективно. Легко видеть, что Г' эквивалентна Г.
Теорему 6.3 мы используем для доказательства следующего утверждения о МП-машинах.
Теорема 6.4. Для всякой МП-машины М можно построить эквивалентную ей МП-машину Ш', обладающую тем свойством, что ни в одном ее вычислении ни разу не выполняются подряд два элементарных шага на рабочей ленте (иначе говоря, между каждыми двумя «рабочими» шагами читается хоть один входной символ).
Доказательство. При построении машины М' мы можем отправляться не от МП-машины М, а от Б-грамматики Г = (У, W,I,R) и при этом имеем право считать, что Г удовлетворяет требованию теоремы 6.3 при s = 3. Входным и рабочим алфавитами М' будут V и W соответственно. Программа М будет представлять робой объединение систем инструкций, сопоставляемых
Нормальная форма б-грамматики
199
правилам Г указываемым далее способом, с добавлением инструкций <7i#—*q, Q^-*qo- Сопоставление правилам систем инструкций производится следующим образом:
1) правилу вида г = Л->а(аеК) сопоставляется система {qa^qx{r), Aqx{r)->q}\
2) правилу вида А-у аха2 (ах, а2 еК) сопоставляется
система {qax -* q{ (г), qx (г) а2 -> q2 (г), Aq2 (г) q};
3) правилу вида А-> аха2а3(ах, а2, а3 <= V) сопоставляется система {qax qx (г), qx (г) а2 -> q2 (г), q2 (г) а3 q3 (г), Aq3 (г) -> q}\
4) правилу вида А ->? аха2а3В (с,, а2, а3, е V; В elF)
сопоставляется система {qax -> (г), {r)-*q2 (г),
