Гладкий - Формальные грамматики и языки - 1973 (947381), страница 14
Текст из файла (страница 14)
Непосредственной нндукцней по и легко показать, что для любого | = О, ..., п — 1 справедливо !$;я|о!,~ ( пд ( 2!П, где д — максимум длин левых и правых частей правил Г (здесь используется сцеплен- ность Г!). Поэтому число размеченных выводов, удовлетворяющих условиям (а) и (р), конечно. Сопоставим каждому такому размеченному выводу правило р = = $о|роно- о| и положим Г'= ()г,'еУ,1,)с'), где Р' состоит из всех р. Пусть Р = (о|о, ..., оь,), т ) 1,— полный вывод в Г.
Разобьем Р на куски, длина каждого из которых не меньше 1 и не больше 21; число кусков будет не больше тД. Но каждый из этих кусков вывода можно, очевидно, выполнить с помощью одного из правил р; мы получаем, таким образом, полный вывод в Г' длины, не большей т/1, с той же последней цепочкой ы . Вывод в Г длины, меньшей 1, можно заменить выводом в Г' длины !. С другой стороны, из определения правил р ясно, что каждый вывод в Г' можно заменить выводом в Г. Неравенство 5г(и)(5г(п) очевидно. Итак, Г' — нужная грамматика.
С л е д с т в и е. Для любой грамматики Г и любого натурального числа Й можно построить грамматику Г, эквивалентную Г и таку|о, что Тг (п)(шах(1, Тг(п) — Й); 5г (и) (~5г(п). СЛОЖНЫЕ РЕКУРСИВНЫЕ ЯЗЫКИ » зл! [гл. » то СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ Для машин Тьюринга также имеют место теоремы о сжатии и ускорении, а именно: Теор ем а 2.1' (о сжатии вычислений). Для любой Э-машины М и любого положительного действительного числа с можно поствоить Э-машину М', эквивалентную М и такую, что 5м (п)«»шах(1, с5м(и)); Тм (а)- Тм(п). Если при этом М вЂ” ДЭ-машина, то и М' можно сделать ДЭ-машиной.
Теорема 2.2' (об ускорении вычислений). Для любой Э-машины М и любого положительного действительного числа с можно построить Э-машину М', эквивалентную М и такую, что Тм (и) «( (и + 1) + с (Тм (и) — (и + 1)); 5м (а) (» 5м(а). Если ири этом М вЂ” ДЭ-машина, то и М' можно сделать ДЭ-машиной. Теорема 2.1' доказывается совершенно аналогично теореме 2.!. Что касается теоремы 2.2', то ее доказательство аналогично доказательству теоремы 2,2 со следующими отличиями: а) не требуется предварительной переделки машины (в случае грамматики переделка обеспечивается леммой 2.4); б) любая Э-машина при обработке цепочки длины п должна прочесть ее с начала до конца— это и приводит к выделению слагаемого и+ 1; в) поскольку никакой элементарный шаг Э-машины не затрагивает более двух ячеек, при построении новой машины придется прибегнуть к кодированию цепочек в рабочем алфавите (аналогично тому, как это делается при доказательстве теоремы о сжатии).
Займемся теперь вопросом о соотношении между сигналнзирующими грамматик и машин. Обратимся сначала к доказательству пункта а) теоремы 1.4. Нетрудно видеть (см, доказательство леммы 1.5), что если машина М, работая с цепочкой длины а, затрачивает ! = а + !' шагов и максимальная длина рабочей ленты будет при этом равна э, то для М! при обработке той же цепочки (подходящим способом) максимальная длина рабочей ленты э, и число шагов !! будут удовлетворять условиям: э! = э+ а+ 1, 1, ((э+а+ 1)гп1п(п, Г)с+! (пнп(п, Г) — максимально возможное число «переключений» с имитации «входной» команды на имитацию «рабочей»; с — постоянная).
Соответствующие величины для Мх будут таковы: з, зь !х ( 6!+ п+ с, ~ ((э+и+ 1)пнп(а, У)с»+! (с!, с» — постоянные). На. конец, длина (подходящего) вывода той же цепочки в грамматике Г и максимальная длина цепочки, входящей в этот вывод, будут равны !з+ 2 н э»+ 1 соответственно. Обратившись теперь к доказательству пункта б) теоремы 1.4, мы увидим, что если длина вывода цепочки х,!х~ = а, в Г равна й а максимальная цепочка этого вывода имеет длину з, то в М найдется х-вычисление, длина которого не превосходит й!п+й»1(й»! (й!, й», йх — постоянные; й! шагов нужно на переписывание входного символа на рабочую ленту, йз шагов — на имитацию применения одного правила), причем максимальная длина фигурирующей в нем рабочей ленты равна э. Отсюда с учетом теорем 2.1, 2.2, 2.2' и того факта, что все упоминавшиеся постоянные эффективно определимы по соответствующей грамматике (машине), получается Теорема 2.3.
а) Для любой Э-машины М можно построить эквивалентную грамматику Г такую, что 5г(п) ~5м(а); Тг (п) («(5м (п) + п) ' пйп (а, Тм (п) — а) + Тм(п). б) Для любой грамматики Г можно построить эквивалентную Э-машину М такую, что 5м (и) 5г (и); Тм(п) «шах((а+ !), Тг(п)). $2.4. Существование сколь угодно сложных рекурсивных языков Если р — некоторый достаточно «хороший» снгнализнрующий оператор для грамматик и ) — вычислимая функция, то факт принадлежности какого-либо языка классу У! может рассматриваться как определенная характеристика сложности этого языка: если Ь! чей'! и СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ СЛОжНЫВ РВКУРСИВНЫВ ЯЗЫКИ ЕячиЫ~Н то Еа сложнее ?ь поскольку при некотором способе порождения ?ч можно обойтись более простыми выводами, чем те, которые понадобятся при л ю б о м способе порождения ?.я.
Для сигнализирующих наиболее важных типов — Т и 5 — правомерность указанного подхода к определению сложности становится особенно наглядной, если обратить внимание иа следующее: прн Р = Т, 1(п) > 1 и прн Р = 5, ) (п) = п из Е ф Ы)~ следует, что для любой грамматики Г, порождающей язык ?., найдется бесконечно м н о г о чисел п, удовлетворяющих неравенству Рг (п) = > [(и) *). Действительно„если, например, существует лишь конечное число таких пь 1 = 1, ..., р, для которых Тг (пс) >1(пс), и при этом 1(п) > 1, то можно, положив й = гпах (Тг (п~) — 1(п~)) и воспользовавшись след~=ь ..., р станем из теоремы об ускорении выводов, построить грамматику Гь эквивалентную Г и такую, что Тг, (и) ( ~(шах(1, Тг(п) — й)» )(п); аналогично при Р=5, 1(п) > и.
Возникает вопрос: сколь сложным может быть язык в этом смысле? Иначе говоря, можно ли при заданном Р указать такую общерекурсивную функцию 1, чтобы все рекурсивно перечислимые языки оказались в классе 2'~ "г В такой форме этот вопрос немедленно получает отрицательный ответ; действительно, по лемме 2.1 всякий язык, для которого какая-либо снгиализирующая мажорируется вычислнмой функцией, рекурсивен, так что никакой нерекурсивный язык не может принадлежать классу 2'~ ни для какого сигнализирующего оператора Р и ни для какой вычислимой функции 1.
Однако наиболее важны и в теоретическом, и в прикладном аспекте как раз рекурсивные языки, и естественно поставить вопрос для них. Оказывается, что и в этом случае он решается отрицательно: имеет место Т ео р е м а 2.4, Для любого сигнализирующгго опгритора Р(Г, и) и любой общгрекурсивной функции [(и) можно построить грамматику Го, порождающую ргкурсивный язык и такую, что Е (Го) Ф Ы)~. *) 'Аналогичный факт имеет место и для Р='?г'"', Иг'", О, 1 (упрааснение 2.9). ' Д о к а з а т е л ь с т в о. Напомним, что рассматриваются лишь такие грамматики, основные и вспомогательные словари которых содержатся в счетных множествах Е и Е, соответственно (что не уменьшает общности).
Пусть Е=(аы иа, аа, ...), Е,= =(па, аь аа, ...). Положим а, =а, аз= Ь и введем некоторое эффективное кодирование грамматик цепочками в словаре (а, Ь). [Можно, например, считать кодом цепочки айа, ... ац цепочку Ьа'+ ЬЬа Ь ... Ьа а+ Ь, кодом цепочки Л цепочку ЬаЬ, кодом правила ф- ф цепочку х(ф)Ьх(ф), где х(ф), х(ф) — коды ф и ф соответственно, и кодом грамматики (?", ??7, ?, Д) цепочку ЬайЬ ... Ьа)'ЬаЬЬЬх(г,) ...
х(г,), где аи ..., а, и г„... ..., г„— некоторые пересчеты множеств $' () )Р' и Я соответственно, а, = ? и х(г~) — код г,.] Грамматику, имеющую код х, обозначим Г„. Пусть Ео — множество всех цепочек х в словаре (а, Ь), не удовлетворяющих конъюнкции следующих условий: а) существует грамматика Г„; б) хе=А(Г„); в) Р(Г„, х)([()х)). Для всякой грамматики Г, порождающей язык ?,о, найдется число и такое, что Р(Г, п) >1(п). В самом деле, если ?.о=?. (Г), то для некоторой цепочки г будет Г = Г,; при этом ген й(Г,)=Ее, так как из г ей Е(Г,) следовало бы по определению языка Еа, что г епйе=й(?",).
Но тогда Р(Г„г) >1([г)), откуда Р(Г„)г)) >?(!г)). В то же время язык Ео рекурсивен; действительно, х енй тогда и только тогда, когда не выполняется ни одно из равенств Р(Г„, х)=0, ..., Р(Г„х)=1()х)), каждое из которых эффективно проверяемо. Грамматику, порождающую Е„нетрудно построить, зная алгоритмы, вычисляющие функцию 1(п), и график функции Р(Г, х) (упражнения 2.11, 2.12). Итак, теорема 2.4 доказана.
Но справедливо и более сильное утверждение: Теорема 2.5. Для любого сигнализирующего оператора Р(Г, п) и любой общерекурсивной функции [(и) можно построить грамматику, порождающую рекурсивный язык и такую, что для любой эквивалентной гй грамматики Г при всех достаточно больших и имеет место неравенство Рг(п) ) 1(п). 1гл. 3 СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ УПРАЖНЕНИЯ Д о к а з а ! е л ь с т в о. Закодируем грамматики, как в доказательстве теоремы 2.4. Если и — стандартный номер цепочки х в словаре (а, Ь) (стр. 22), будем писать х„вместо х н Г„вместо Г,. Искомый язык Г.е мы будем строить индуктивно, решая последовательно для каждого и = О, 1, ..., следует ли причислить к Лз цепочку х„. Одновременно будет определяться некоторая вспомогательная частичная числовая функция Ь(п) — «функция опровержения», не принимающая никакого значения более чем один раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
