Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Аналогично неравенствам (1), (2), (3) из § 2.1 нетрудно получить следующие неравенства (доказательство предоставляется читателю):
(V) Тм(п)^п +1,
(2') SM(n)<±{TM (n)-(n + l)),
SM(n)+l _
(30 TM(n)<r(n + l)(SM(n) + l). k_{ -1 ,
где k, г — мощности рабочего алфавита и множества состояний машины М соответственно.
В главе 1 (теорема 1.2) мы доказали, что для каждой Э-машины М можно построить ДЭ-машину Mi такую, что L{Mi) =L(M). Ясно, что при «детерминиза-ции» машины время вычисления и число используемых ячеек будут, вообще говоря, расти. Просмотр конструкции, примененной в доказательстве теоремы 1.2, дает возможность оценить этот рост. Именно, пусть x^L(M), и при этом то полное лг-вычисление С машины М, имитацией которого заканчивается (единственное) полное х-вычисление Ci машины Mi, имеет длину t, а максимальная длина рабочей ленты в вычислении С равна s. Соответствующие величины для вычисления С1 обозначим ti и Si. На каждом «макрошаге» вычисления Ci имитируется некоторое х-вычисление машины М, длина которого t' не превосходит t; поэтому длина участка рабочей ленты между d и началом Z на данном макрошаге никогда не будет больше t (в начале макрошага она равна 0 и на каждом «М-шаге» может возрасти разве что на 1), а длина Z в точности равна Отсюда
64
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
Si s?S |х| + 2t -f 3. Далее, каждый макрошаг состоит из ? «M-шагов», каждый из которых требует не более 2(\х\ + 2t' + 3 + D) элементарных шагов машины М% (D — постоянная; при выполнении «М-шага» головка должна «прогуляться» из начала цепочки длины не более |х |+2/'4-3 в ее конец и обратно, выполнив «по дороге» ограниченное число Специальных операций — собственно «M-шаг», перенос метки и т. п.); после выполнения последнего «.М-шага» для завершения макро-шага может понадобиться еще не более |х| + 2/'+ 3 + + Di элементарных шагов (Di— постоянная). Всех макрошагов будет не больше, чем различных цепочек в
__ 1
алфавите Р длины, не превосходящей i, т. е. } ;
наконец, до начала первого макрошага машина должна сделать 2(|х|+4) шагов. Это дает U ^ Ак1+Ч(В^ + -f- В21 х | + Вз), где А, Ви В2, В3 — постоянные.
Отсюда непосредственно следует
Лемма 2.3. Для любой Э-машины М можно по-строить ДЭ-машину Mi, допускающую язык Ь(М) и такую, что
TMl (п) < АНТм <п)+1 • Тм (п) ? (Bi Тм (л) + В2п + Вз),
<$м, (п) ^ 2Тм (п) + п -|- 3,
где h — число инструкций машины М и А, Ви В2, В3 — постоянные, зависящие от М.
§ 2.3. Ускорение и сжатие выводов.
Связь между сигнализирующими грамматик и машин
В построениях этого параграфа важную роль будет играть «лемма о сцеплении», которую мы сейчас сформулируем и докажем, введя предварительно! понятие сцепленной грамматики.
Грамматика называется сцепленной, если в каждом ее размеченном полном выводе каждый следующий шаг зацеплен с предыдущим.
Лемма 2.4 (о сцеплении). Для произвольной грамматики Г можно построить эквивалентную ей сцепленную грамматику Г' такую, что
Sr (п) = Sr {п), Тг' («X kTr (п),
§ 2.3]
УСКОРЕНИЕ И СЖАТИЕ ВЫВОДОВ
65
где k — постоянная, зависящая от Г (и допускающая эффективное вычисление).
Доказательство. Пусть Г = (V, W, I, R). Вейлу леммы 2.2 мы можем считать, что левые части правил Г не пусты, и рассматривать только такие выводы в Г, в которых правило с пустой правой частью применяется разве что на последнем шаге. Сопоставим каждому символу а е V, (J W взаимно однозначным образом двух «двойников» — новые символы а и множества «двойников» обозначим соответственно Z и Z0. Каждому правилу
Pi ••• Pp-»Yi ••• <fo,yls=VUW)
сопоставим множество, состоящее из всевозможных правил вида
Р? • • • Р°_,М°+, • • • К-*ЬУ°2 • • • Y°. *•= 1, ..Р
(правила 1-го рода). Каждой паре а, р е V U W сопоставим правило ар°->а°р (правило 2-го рода), каждому cieV — правило а—*а (правило 3-го рода), каждой паре a, 6eV — правило a°b-*ab (правило 4-го рода). Положим Г'— (V, Z\JZ°,T,R'), где R' — совокупность всех правил 1-го—4-го рода.
Сцепленность Г' легко проверяется непосредственно. Докажем эквивалентность Г и Г'. Для каждого упорядочиваемого вывода D = (соо, ..., со„) в Г легко построить вывод в Г/, состоящий из п последовательных кусков:
С40....(\+‘...........'Ч) (Ч-.+1......\>
причем для каждого / = 1, п цепочка г\.^ отличается от со j только наличием черты над одним из вхождений символов и верхнего индекса 0 у остальных. При этом каждый кусок начинается применением правила 1-го рода, а на всех остальных шагах куска, если таковые есть, применяются правила 2-го рода. Поскольку со„ е V*, из т1; можно с помощью правил 2-го, 3-го
и 4-го рода вывести мп- (Сначала следует «загнать» черточку в конец цепочки, затем применить правило 3-го рода, далее пользоваться правилами 4-го рода.)
3 А. В. Гладкий
66
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
Ясно также, что цепочку в словаре V можно вывести в Г из 7 только вышеописанным образом. Ввиду леммы 1.2 из сказанного вытекает эквивалентность Г и Г', а также равенство Sr(n) = Sr(n). Остается оценить Тт'. Пусть ?)' = (%, ..., т^) — произвольный полный вывод в Г', и пусть rrik (k = 1, 2, 3, 4) —число шагов этого вывода, на которых применяются правила рода k (шагов рода k). Нам достаточно найти такую не зависящую от D' постоянную I, чтобы выполнялось неравенство тг ^ Irrii. Действительно, длина соответствующего D' вывода в Г равна ти а так как т3 = 1 и т4 = = |т1т|—1, мы получим т — trii -f т2 + тз + Ш ^ ^ (/+ \)mi -f |т1т| sg: (/ + / + 1)т4 (/— максимум
