Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 25

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 136 >> Следующая

Sr'(n)^Sr(n).
Доказательство. Пусть Г = (V, W, I, R). В силу леммы о сцеплении мы можем считать грамматику Г сцепленной. Фиксируем натуральное число /, большее 1/с, и рассмотрим всевозможные размеченные выводы в грамматике Г: D' = (со', ..., со'_,, соп), м' = lt * <р(. * Т1г, удовлетворяющие условиям: (а) 1 ^ п ^ 21; (р) существуют такие ii и k из ряда 0, ..., п— 1, что I* =11^= = Л. Непосредственной индукцией по п легко показать, что для любого i — О, ..., п — 1 справедливо ||гфгть| ^ пё ^ 2/g, где g— максимум длин левых и правых частей правил Г (здесь используется сцеплен-ность Г!). Поэтому число размеченных выводов, удовлетворяющих условиям (а) и ({3), конечно. Сопоставим каждому такому размеченному выводу правило р = = |офот1о —>• соп и положим Г' = (V, W, I, R'), где R' состоит из всех р.
Пусть D = (мо, со™), m ^ /, — полный вывод в Г. Разобьем D на куски, длина каждого из которых не меньше I и не больше 2/; число кусков будет не больше m/l. Но каждый из этих кусков вывода можно, очевидно, выполнить с помощью одного из правил р; мы получаем, таким образом, полный вывод в Г' длины, не большей m/l, с той же последней цепочкой мт. Вывод в Г длины, меньшей I, можно заменить выводом в Г' длины 1. С другой стороны, из определения правил р ясно, что каждый вывод в Г' можно заменить выводом в Г. Неравенство Sr{n)^Sr(n) очевидно. Итак, Г' — нужная грамматика.
Следствие. Для любой грамматики Г и любого натурального числа k можно построить грамматику Г7, эквивалентную Г и такую, что
7V (п) ^ max (1, Гг (п) — k);
70
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
Для машин Тьюринга также имеют место теоремы
о сжатии и ускорении, а именно:
Теорема 2. Г (о сжатии вычислений). Для любой
Э-машины М и любого положительного действительного числа с можно построить Э-машину М', эквивалентную М и такую, что
5м'(п)<шах(1, cSM{n))\
Тм' {п) ^ Тм (п).
Если при этом М — ДЭ-машина, то и М' можно сделать ЛЭ-машиной.
Теорема 2.2' (об ускорении вычислений). Для любой Э-машины М и любого положительного действительного числа с можно построить Э-машину М', эквивалентную М и такую, что
Тм’{п)^{п + 1) + с(Гм(п) — (п + 1));
Sm' (п) ^ Sm (п).
Если при этом М — ДЭ-машина, то и М' можно сделать ДЭ-машиной.
Теорема 2.1' доказывается совершенно аналогично теореме 2.1. Что касается теоремы 2.2', то ее доказательство аналогично доказательству теоремы 2.2 со следующими отличиями: а) не требуется предварительной переделки машины (в случае грамматики переделка обеспечивается леммой 2.4); б) любая Э-машина при обработке цепочки длины п должна прочесть ее с начала до конца— это и приводит к выделению слагаемого п-{-\\ в) поскольку никакой элементарный шаг Э-машины не затрагивает более двух ячеек, при построении новой машины придется прибегнуть к кодированию цепочек в рабочем алфавите (аналогично тому, как это делается при доказательстве теоремы о сжатии).
Займемся теперь вопросом о соотношении между сигнализирующими грамматик и машин. Обратимся сначала к доказательству пункта а) теоремы 1.4. Нетрудно видеть (см. доказательство леммы 1.5), что если машина М, работая с цепочкой длины п, затрачивает t = п +1' шагов и максимальная длина рабочей ленты будет при этом равна s, то для Mi при обработке той же цепочки (подходящим способом) максимальная длина
СЛОЖНЫЕ РЕКУРСИВНЫЕ ЯЗЫКИ
71
рабочей ленты Si и число шагов t\ будут удовлетворять условиям: si = s + n+l, ti sg: (s + ti + l)min(n, t')c -f- t (min(n, t') — максимально возможное число «переклк> чений» с имитации «входной» команды на имитацию «рабочей»; с — постоянная). Соответствующие величины для М2 будут таковы: s2 = su t2 ^ U + п + й ^
sg: (s + п -f l)min(n, t')c2 + t (cj, C2 — постоянные). Ha*-конец, длина (подходящего) вывода той же цепочки в грамматике Г и максимальная длина цепочки, входящей в этот вывод, будут равны t2 + 2 и s2 + 1 соответ* ственно.
Обратившись теперь к доказательству пункта б) теоремы 1.4, мы увидим, что если длина вывода цепочки х,\х\ = п, в Г равна t, а максимальная цепочка этого вывода имеет длину s, то в М найдется х-вычисление, длина которого не превосходит din + d2t ^ d3t (du d2, d3 — постоянные; d\ шагов нужно на переписывание входного символа на рабочую ленту, d2 шагов — на имитацию применения одного правила), причем максимальная длина фигурирующей в нем рабочей ленты равна s.
Отсюда с учетом теорем 2.1, 2.2, 2.2' и того факта, что все упоминавшиеся постоянные эффективно определимы по соответствующей грамматике (машине), получается
Теорема 2.3. а) Для любой Э-машины М можно построить эквивалентную грамматику Г такую, что
Sr (п) ^ Sm (п);
Гг(«X(Sm(п) + п) ? min (п, Тм(п) — п) + Тм(п).
б) Для любой грамматики Г можно построить эквивалентную Э-машину М такую, что
Sm (п) = Sr (я);
Тм{п)^. шах ((п + 1), Гг (п)).
§ 2.4. Существование сколь угодно сложных рекурсивных языков
Если F — некоторый достаточно «хороший» сигнализирующий оператор для грамматик и / — вычислимая функция, то факт принадлежности какого-либо языка классу может рассматриваться как определенная характеристика сложности этого языка: если L\ е j?/ и
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed