Гладкий - Формальные грамматики и языки - 1973 (947381), страница 49
Текст из файла (страница 49)
Кроме того, для каждого А ~ )у' — (1) будем полагать Г,» — — ()', )«' — (1), А, )7'), где 1»»' получается из 17 изъятием правил, содержащих в левой или правой части вхождения 1. Для каждой грамматики Г,» можно по индуктивному предположению построить эквивалентную ей А-грамматику, и то же верно для правосторояней линейной грамматики 1', однако поскольку в цепочках вывода в Г, начинающегося символом 1, этот символ может стоять только на последнем месте, язык Ь(Г) получается из Ь(Г) подстановкой вместо каждого А ее )Р' — (1) языка 1.(ГА), и мы можем воспользоваться теоремой 5.4.
Доказательство теорем ы 76. Пусть Г = = ()«л йт,1, 17) — Б-грамматика. Мы можем считать, что она не имеет правил вида А-»-В, В ее )»т. Кроме того, нам удобно будет полагать, что основные символы могут содержаться лишь в правых частях правил вида А — а, а ее )т; действительно, если ввести для каждого и ~ )1 «двойник໠— новый символ а, заменить в правых частях всех правил из 17 не вида А-1-а, а ее )т, все вхож-.
дения основных символов вхождениями их «двойников» и добавить к 17 всевозможные правила вида а-» а, то это ие изменит ни порождаемого грамматикой языка, ни ее степени гнездования, ни степени самовставления. Введем теперь для каждого символа А ее )Р' 5(А+1) новых символов: Ал" ' («левые неуглубляющие» символы), АЛУ ' («левые углубляющие»), Апн ' («правые неуглубляющие»), АНУ ' («правые углубляющие»), Ас ' («средние»); здесь О ~(1( й. Каждому правилу А-+ — >ВЕ! ... Е,0, где В, Е„..., Е„1л~)Р', з)О, сопоставим 5й новых правил: 1ЛН, 1 ЛН, 1 С, 141 С, 1+11уПУ, 1+1 1пн, 1 „лУ, 1+1 с, 141 с, 1+117пн, 1 24В СЛОЖНОСТЬ ВЫВОДА В Е.ГРАММАТИКАХ 1гл. 7 степень гнездОВАния и слмОВстАВления э47 4 7.3! Кроме того, каждому правилу А-р а, где а ен 17, сопоставим всевозможные правила вида Ль'-+ а, где Ъ=ЛН, ЛУ, ПН, ПУ, С и 7=0, ..., й.
Положим теперь Г'=(17, йг', 7с ', 14'), где )47' состоит из всех новых символов и 1!1' — из всех новых правил. Из самого вида новых правил непосредственно усматривается, что при любом ! = О, . „ й — 1 цепочка, выводимая в Г' из символа Алн ', соответственно А"н ', может содержать вхождение того же символа только на первом, соответственно последнем, месте; символы же АЛР,! Апл'.' Ас ' (! =О й) а также Алн,л и Апн,л не являются даже циклическими.
Поэтому Г' — грамматика без самовставления, и по лемме 7.3 можно построить эквивалентную ей А-грамматику. Вспомнив индуктивное определение степени гнездования составляющей (стр, 289), можно без всякоготруда показать индукцией по 7, что в любом дереве полного вывода в Г' степень гнездования каждой составляющей, «происходящей» от узла, помеченного символом с индексом 1, равна 7; поэтому степени гнездования деревьев полных выводов в Г' (точнее, отвечающих им си!угем составляющих) не превосходят й.
В то же время, если в дереве вывода в Г' лишить все символы- метки индексов, получится дерево вывода в Г, имею7цее, очевидно, ту же степень гнездования; следовательно, Л (Г') «и !.А (Г). С другой стороны, легко показать, что во всякол! дереве полного вывода в Г, степень гнездования которого не превосходит Й, можно так снабдить символы-метки индексами, чтобы получилось дерево полного вывода в Г' (следует приписывать индексы «сверху вниз», переходя от каждого узла к подчиненным ему).
Отсюда !'.А (Г') ': — Е(Г'). Займемся теперь степенью самовставления. Пусть Ур' = (Н» ..., Нр). Каждому А = Н! е= йг мы сопосзавнл! систему новых символов, которые будут запи- 1'з! ...Е1 сываться в виде Аь( . ~. где Ъ = ЛН, ЛУ, ПН, ~0, ... 7,/' ПУ, С; з, = О, 1; 7, = О...,, Й.
(Содержательный смысл Ъ вЂ” тот же, что и в первой части доказательства; 7! означает «степень Н;-самовставления» составляющей, происходящей от узла с меткой А, т. е. наибольшую глубину гнезда, все члены которого«происходят»отузлов с меткой Н; н содержат данную составляющую; з, — вспомогательный «индекс готовности», смысл которого будет ясен из дальнейшего.) Далее, каждому правилу г = А — а7 ~ 14, где 7» = ВЕ! ... ... Е,К В, Е„..., Е„Нее Ю', з) О, будет сопоставляться система новых правил, каждое из которых отличается от г только наличием индекса Ъ и матрицы с 3! .
° ° яр!! при каждом вхождении символа в левую и 1,...7,/ правую часть; при этом в левой части возможны любые комбинации индексов и матриц, а в правой индексы и матрицы выбираются следующим образом. 1. Значение Ъ для каждого вхождения символа в лл выбирается в зависимости от расположения этого вхождения и от значения того же индекса при А точно так же, как в первой части доказательства. П. Правила выбора значений зр 1) Для всех средних вхождений з! = 1 (1 1..., " , р). 2) Если А = Н; нли значение з! при А равно О, то неуглубляющие левые и правые вхождения символов в 7» получают значения аь равные О, а углубляющие— равные !.
3) Если А чь Н; и значение з; при А равно 1, то все вхождения символов в ы получают значения зь равные 1. П1. Правила выбора значений 7Е 1) Если А = Нь то значения 1! для тех вхождений символов в «7, для которых з! = О, такие же, как для А, а для тех, для которых з! = 1, — на единицу больше. 2) Если А ~ Нь то для всех вхождений символов в ел значения 7! такие же, как для А. При этом, если А = Н; и значение 7; для А равно й, то те из описанных выше правил с соответствующей ле.
вой частью, у которых в правой части имеются вхождения Н! со значениями зь равными 1, изымаются из чис. ла сопоставляемых правил. 248 сложность ВыВОдА В Б-ГРАммАтикАх [ГЛ, т 249 УПРАЖИВНИЯ Кроме того, каждому правилу вида А- а, где и ~ У, сопоставляем всевозможные правила видз Аь, . -+а. Положим Г'=()т, Ф',1с( ), Р'~, где В" со. стоит из всех новых символов и Я' — из всех новых правил. Из приведенного только что описания новых правил легко усматривается, что: а) если левая часть правила имеет вид лн(з1 . зр ) Нт ( ., ), то у всех вхождений символов в прай ". 1,1' вую часть, кроме первого (также имеющего ЛН в качестве значения Ъ) значения (; больше, чем в*левой части, а значения зь ..., (7 ь (1+ь ..., (р такие же; б) для пн з1 ° ° ° ар правил с левой частью Н) ( ., ) рассмотрение (,1, ... (р/ симметрично; в) если левая часть имеет вид ъ(з! '' ер Ну ( ..
(, где Ъ равно ЛУ, ПУ нли С, то в правой (,1, ... (р)( части перрое и последнее вхождения символов имеют в качестве значений Ъ ЛН и ПН соответственно, и значения й, ..., (р у этих вхождений такие же, как в левой части, а у средних вхождений значения (, больше, чем в левой части, и значения остальных 1 такие же. Отсюда, в свою очередь, ясно, что символы, для которых Ъ равно ЛУ, ПУ или С, не циклические н что в цепочке, выводимой из символа, для которого Ъ = ЛН (соответственно Ъ = ПН), вхождение того же символа может стоять только на первом (соответственно послед- ' нем) месте. Таким образом, Г' есть грамматика без ' самовставления.
Нетрудно, далее, показать, исходя опять-таки из самого определения новых правил, что если а — произвольный узел дерева полного вывода в Г', Б — узел, подчиненный а, 1; — «степень Нксамовставления» узла а (т. е. наибольшая глубина гнезда, все члены которого «ПрОИСХОдят» От УЗЛОВ, НЕСущИХ ПОМЕтКу Н вЂ” С раэиыт ми, вообще говоря, индексами и матрицами,— и содержат составляющую, «происходяшую» от а) и 187— «степень Н;-самовставления» узла Б, то 18; =1 ь когда значения 1) для меток при «х и Б равны, н 18; = 1;+ 1 в противном случае (т. е.
когда значение (7 для метки при Б на единицу больше, чем для метки при а). Отсюда очевидной нндукцией получается, что максимум «степеней Н,-самовставления» узлов дерева полного вывода в Г', взятый по всем узлам и по всем 1' = 1, ..., р, равен наибольшему из значений 1„..., (р для меток в узлах данного дерева, так что ни для какого дерева полного вывода в Г' этот максимум — обозначим его М вЂ” не может превосходить й. В то же время, лишив в таком дереве все символы-метки индексов и матриц, получим дерево полного вывода в Г, степень самовставления которого равна М.
Поэтому 1. (Г )ы(.е (Г). С другой стороны, нетрудно показать, что в дереве полного вывода в Г, степень самовставления которого не превосходит к, можно так снабдить символы-метки индексами и матрицами, чтобы получилось дерево полного вывода в Г'; отсюда Т.ь (Г)ы1. (Г ). Доказательство закончено. Следствие.
В) Для любой В-грамматики Г, для котодой Фг (и) огРаничена числом Й, можно, если известно й, построить эквивалентную ей А-грамматику. б) Аналогично для Хг(п). Упрвжиения 7.(. е) Показать, что левая глубина и разброс любой Б-грвммвтики, порождаюшей язык Дика, мажорируют подходяшие линейные функции. б) То же для скобочното языке 7.2. Показать, что левая глубина любой однозначной Б-трзмматики, порождающей неавтомвтный язык, мзжорирует подходяшую линейную функцию. 7.3. Показать, что для произвольных Б-грвммзтик Г1 и Гз можно построить Б-грвммвтику Г, порождающую язык ь(Г~)ь(Г») и такую, что хзг(л)(шах(чл'гл (и) ч1гп (и)) 7.4. Определим «центральную глубину» и «крзевую глубину» цепочки в ш (У 0 (У)' соответственно кек наименьшее знзченне левой и правой глубины в и кзк наименьшее число л, для которого в представнма в виде е»хвь гле х ш У' и (в~( + ~вт) = и.
Дзлее обыч. ным способом определим центральную и краевую глубину грамматики. 251 УПРАЖНЕНИЯ 259 ОЛОЖНООТЬ ВЫВОДА В В.ГРАММАТИКАХ [ГЛ. 2 Показать, что для центральной и краевой глубины справедливы аналоги теоремы 7.2. 7Л. а) Показать, что для любой НС-грамматики Г н любого действительного числа с, 6 ( с ( 1, можно построить НС-грамма- тику Г', эквивалентную Г и такую, что 9Г. (и) ~ (ся. л б) Можно ли распространить на случай произвольных НС-грам- матик теорему 7.47 7.6. Показать, что для любого й = 1, 2,... и любого 1= 5+ 1„ А+ 2, ...
можно построить такую Б-грамматику Г, что 5(Г) щ гм Ы~ь<ь, (Б) — ЫА~ (Б) и при этом!о(Г) = 1 7.7. а) Показать, что если И вЂ” высота дерева подчинения, согла- сованного с некоторой системой составляющих густоты р (т. е. та- кой, что густота соответствуюгцего дерева составляющих равна р), то р.б й, б) Показать, что для Б-грамматики Г тогда и только тогда су. ществует (и может быть построена) сильно (соответственно слабо) эквивалентная ей Д-грамматика 6 ограничеапой высоты, когда ак- тивная емкость Г ограничена константой (соответственно А(Г) яв- ляется ОАЕ-языком).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
