Гладкий - Формальные грамматики и языки - 1973 (947381), страница 20
Текст из файла (страница 20)
Пусть Из — подмножество И„состоящее из всех цепочек, для которых каждое из сечений Л„Л„А удовлетворяет условию (4). Из (5) следует, что при достаточно больших допустимых 1 будет [4(Из))2опб. Пусть теперь И,— наибольшее по мощности подмножество Из, для любых двух цепочек которого х„х, следы вывода Е)', на сечениях Л[, А„бз соответственно совпадают со следами вывода В'„, на этих сечениях. В силу (4) при достаточно больших допустимых 1 будет р (И,) -«2"['. Для произвольной цепочки х ~ И4 представим ого= аз[4(х) в виде [о[ = ь[ (Х) ~2 (Х) ьз(Х) ьб(Х), где (Ь[(х), Ь[+1(х)) = Л[ (1 = 1, 2, 3).
Поскольку И, = Иг и все три сечения Л[, Лг, Аз принадлежат п(Х), отрезки ьг(х) и ьз(х) для всех х ~ И, соответственно совпадают; будем обозначать их ф и ф Точный потомок отрезка ь[(х) (1 1, 2, 3, 4) в цепочке у(х) будет обозначаться г[(х). Пусть Из — наибольшее по мощности подмножество И„для любых двух цепочек которого х„х, прк каждом 1=1, 2, 3, 4 длины отрезков г[(х,) и г,(хг) совпадают. При достаточно больших допустимых 1 будет р(И,)~2'". Общее значение длины г[(х) для хенЯ цепочек, принадлежащих Иг, для которых при данном Ь выполняется (4); число сечений, принадлежащих 5„, для которых (4) выполняется при фиксированной цепочке х, будет обозначаться у„. Очевидно, ~ [д ~ д . Но Д~З 2ММ для любой цепочки х онИ2 имеем д„~~[4(5,) (1 — — 1, ! 1 Поэтому в 5„найдется хотя бы одно сечение Ь, для которого обозначим 11.,' Поскольку Л[ ен 51« Лг я 52+1, Ьз еи54„ имеем (6) 11~ 14 С 1~ (7) 11 + 1г 1з+ 14 ) 1 Кроме того, имеет место хотя бы одно из двух неравенств: ,(8) 1, + 12 ) 21, (8') 1, + 14 ) 21.
Для определенности будем считать, что выполняется (8), Пусть теперь Иб — наибольшее по мощности подмно- жество И,„для любых двух цепочек которого х„х, от- резки г[(х[) и г,(хг) совпадают. Очевидно, [2(Иб)~~2~п~ 1'. Общее значение' г,(х) для х ~И обозначим го[. Покажем, что в Иб найдутся две цепочки х, и хг такие, что (9) гз(Х1) г4(Х1) ~ гз(Х2) г4(Х2) В самом деле, если х, и хг — различные цепочки иа Иб, то равенство гз(Х[) г4(Х[) — гз(Х2) г4(Х2) = й возможно только тогда, когда 12+ 1, < 21 — 1„так что гб[а~г Х ии г~ы~~г и при этом и['чь в". Но различных цепочек длины 21 — 1, — 1,— 1, имеется 2 ' * ' =2' ' (в силу (7)). Поэтому в И, найдется не менее 2 цепочек х, не удо1[б влетворяющих условию г, (х) г4(х) = г.
Пусть х„хг — цепочки из Яб, удовлетворяющие (9). Из цепочек ОЗ[ (Х,) = Ь[ (Х,) фф, (Х[) и [,(х ) г (х ) гогот (х ) в Г вывоДимы соответственно цепочки у(х,)=гог (х,)г,(х,)г,(х,) и у (Х,) г[гг (Хг) гз(Х~ гб (Х ). ГРАММАТИКИ СОСТАВЛЯЮЩИХ 4оа 4гл. з 4 за! оцвнка врвмвниоп сложности нс-языков юз По лемме 3.2 из оз! (х,), а значит и из 1, должна быть выводима также цепочка д=г',гз(х)г (х,)г,(х,). Но в силу (8) и (9) цепочки р(хз) и у не могут одновременно принадлежать (,ч. С лу ч ай 2. Пусть для определенности найдутся сколь угодно большие и такие, что бесконечно много чисел 1, кратных и', удовлетворяют условию: по крайней мере для четверти всех цепочек х длины 21 длйны всех отрезков озь, ..., «з~ меньше д. Рассуждая совершенно аналогично случаю 1 (с очевидными уярощениями), можно для достаточно большого 1 найти две цепочки х, и х, такие, что ози(х,) и со! (хз) пРедставимы в виде 4о~ (х,)=ь",ьз(х,), со~ (х)=ь",ь (х ), где а) следы «хвостов» выводов 1)„п начинающихся с азl (х,), на сечениях (Ьои Ь (х,)) при 4'=1 и при 4"=2 одинаковы; б) если г, (хз), гз(хз) — соответственно точные потомки отрезков ьои ь (х,) в цепочках у(хз) (4 =1, 2), то ! г, (х,) ! =! г, (хз) ! = 1„! г,(х,) ! = ! гз(хз) ! 1з, причем 1„ 14 )1 и хотя бы одно из чисел 1и 14 больше 21; в) гз(х,) ~ гз(хз) (4 = 1, 2).
По лемме 3.2 из оз! (х,), а значит и из 1, должна быть выводима цепочка г,(хз)г,(х,), которая в силу в) не может принадлежать 1 одновременно с у(хз), если 1, ) 21, и одновременно с у(х,), если 1з) 21. Теорема доказана. 3 а меч а ни я. !) Среди языков, удовлетворяющих условию теоремы 3.7, имеются такие, для которых доставляемая этой теоремой нижняя оценка временнбй сложности является точной, т. е. в принципе не может быть улучшена.
Так, легко убедиться, что для грамматики примера 11 из 5 1.3 временная сложность меньше и', а по теореме 3.6 для порождаемого этой грамматикой языка можно построить и НС-грамматику не большей сложности. (Это верно и при упомянутой на стр. 97 модификации.) Другие примеры указаны в упражнении 3.!9. Как уже отмечалось, примеры языков, для которых вытекающая из теоремы 3.7 оценка не является точной, неизвестны, 2) Если функция зр ни для какой постоянной Ы не удовлетворяет условию !зр(х)~ ~ 41-!х(, то утверждение теоремы 3.7 может не иметь места (упражнение 3.20).
Остановимся еще на классе 2'„(НС) (совпадающем, г в силу теоремы 3.6, с,У~4«и(НС), где (с.и) — класс всех линейных функций). Ввиду теоремы 3.7 этот класс является собственной частью,У(НС); с другой стороны, она»одержит все Б-языки (см. ниже, замечание к упраж- нению 4.1). Естественно спросить, является ли Ы'(Б) собственной частью ж.~(НС). Положительный ответ на этот вопрос вытекает из следующего примера.
П р и м е р 1. Пусть à — НС-грамматика со схемой 1-+ ЬА,Ь ЬА~ -+ ЬАзАз АзА1-~ А,АзАз Азй-» А,АзЬ АзАз -» Аз 4зАз ЬАз 4' ЬА4А4 А4Аз-+ ААА4А4 ААЬ -» А,А,Ь А,А, -» А,А,А, А,-+а Очевидный подсчет показывает, что Тг (и) а-) = 2(и — 2). В то же время1 (Г)=(Ьаз Ь~Й=О, 1, ...)! в следующей главе будет доказано утверждение (следствие из теоремы 4.5), из которого непосредствен» но вытекает, что этот язык не является бесконтекстным.
Рассмотрим еще один пример языка, принадлежаще- го разности Ы,"(НС) — 2'(Б). Пример 2. Язык примера 10 из 9 1.3 — (а"Ьааа~ и = 1, 2, . ) — не является Б-языком (см. ниже, 9 4.3, пример !). Покажем, как построить неукорачивающую грамматику с линейной временнбй сложностью, порож- дающую этот язык *). '! Это построение принадлежит Р. В. Фрейвалду.
ГРАММАТИКИ СОСТАВЛЯЮЩИХ югл, в !ой $ В.Я НС.ГРАММАТИКИ С ОДНОСТОРОННИМ КОНТЕКСТОМ !об Прежде всего легко построить неукорачивающую грамматику Гю, порождающую язык (йй'й1п = 1, 2, ...), где й — двоичная запись числа и и й' — тоже двоичная запись и, но состоящая из цифр О' и 1' (чтобы можно было различить «зоны» цепочки); эта грамматика строится аналогично грамматике примера 11 из 3 1.3, и, как в этом примере, Гю можно построить так, чтобы цепочка х=йй'й была выводима в Гю не более чем за с~к~в шагов, где с — некоторая постоянная (ср.
замечание ч»1) после теоремы 3.7). Поскольку 1йй'й1- 3(1ойюп+1), число с! йй'й Г мажорируется линейной функцией от Зп = !а"Ь"ся~. Поэтому нам достаточно построить неукорачивающую грамматику Гв, в которой для любого и = 1, 2, ... из цепочки й будет выводима не более чем за с,п шагов, где сю — постоянная, цепочка а", и не будет выводима никакая другая цепочка в словаре (а). Мы не будет выписывать схему. грамматики Гв ввиду ее громоздкости; ограничимся описанием принципа ее работы — вполне достаточным, впрочем, для фактического построения схемы *). Пусть й = ю,ю,, ... ю,юо, где 1ю — — О, 1 и ю',= 1. Вывод в Гм начинающийся цепочкой й, будет состоять из з+! «макрошагов».
Цепочка, выведенная к началу й-го макро- шага (й = О, ..., в), будет иметь вид 1,...юь+ююьаююа'А-ю "' 'о, где юь ~ ° ° ° юо=юь-ю '2А ю+ ° ° ° + (о' 2о и ф= А,АоААоА»АоА' ... Л,А'А ' '. Макрошаг состоит в следующем:. а) Если юь=. О, то юь превращается в Ао, каждое «старое» вхождение Ао — в А,А и каждое вхождение А — в АА. В результате получается цепочк ' (ю ... юь+,А,АоААоА' ... ЛоА'"- 'а'А "' " (поскольку в этом случае 1А, ...
юо=юь .. юо). б) Если юь ='1 и й < в, то юь превращается в ЛоАоЛ, каждое «старое» вхождение Ао, кРоме последнего, — в АоАА, каждое вхождение А л е в е е последнего вхождения Ао — в Аю, а цоследнее вхождение А, и каждое вхождение А правее него — в аа. В результате получается опять-таки це- ') Нв самом деле для осупюествлення прнволнмой ниже конструкцнн первый н последний снмнолы цепочки Л должны быть' првдвврнтсльно квк-то помечены. почка 1» ... !АР,А,А,ААоАА ... АоА' -'а А '" ".
в) Если й=в, то ю, и все вхождения символов Ао и А заменяются на а. Получается цепочка а" "' Легко видеть, что схему описанной грамматики можно построить так, чтобы'на каждом шаге, не входящем в последний макрошаг, цепочка удлинялась. Поэтому длина вывода цепочки а" нз и не будет превышать 2п шагов. Построение примера закончено, Заметим еще, что любой язык из Ы~(НС) распознается ДЭ-машиной с ограниченным растяжением (теорема 2.3, б), лемма 2.3, упражнение 3.14), так что его дополнение является НС-языком.
В то же время даже дополнение к Б-языку, как и пересечение двух Б-языков, может не принадлежать Ы (НС) (упражнение 3.21). $3.б. НС-грамматики с односторонним контекстом В настоящем параграфе будет рассмотрен один специальный класс НС-грамматик, выделяемый с помощью некоторого иа первый взгляд весьма сильного ограничения, но тем ие менее оказывающийся эквивалентным по «порождающей силе» классу всех НС-грамматик. Будем называть НС-грамматику левоконтекстиой, соответственно пра вако нтекстно й, если правые (левые) контексты всех ее правил пусты. Лево- контекстные и правоконтекстные НС-грамматики будем называть также НС-грамматиками с одностор о н н и м контекстом. Довольно долго стоял вопрос о существовании НС-грамматик с односторонним контекстом, порождающих не бесконтекстные языки (см.
библиографические замечания). Тем не менее имеет место ' Теорем а 3.8, Для любой НС-грамматики может бьють построена эквивалентная ей левоконгексгная НС- грамматика. Доказав эту теорему, мы, разумеется, будем вправе заключить о справедливости аналогичного факта для правокрнтекстных грамматик, . Э КЗ[ НС-ГРАММАТИКИ С ОДНОСТОРОННИМ КОНТВКСТОМ [07 ГРАММАТИКИ СОСТАВЛЯЮЩИХ [оз [ГЛ. 3 Чтобы сделать основную идею доказательства теоремы 3.8 более ясной, рассмотрим сначала пример.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
