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

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

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 136 >> Следующая

Если 0 <г; i < / <г; п, Р — интервал цепочки шг- и Q — множество всех точек со3-, являющихся потомками точек Р (очевидно, Q также есть интервал), мы будем называть Р точным предком Q в a Q — точным ПОТОМКОМ Р В COj.
Пусть далее D = (®0, со„) — вывод в НС-грам-матике Г, D' = (co', ..., <о„) — некоторый соответ-
ствующий D размеченный вывод и Т' — некоторое соответствующее D' растянутое дерево вывода. Если Т' фик-
*) Имеет смысл ставить вопрос лишь об усилении верхней оценки — нижнюю, очевидно, усилить нельзя.
ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ НС-ЯЗЫКОВ
95
сировано, то в каждой цепочке со», 1,
имеется единственная «активная точка», отвечающая «ядру» применяемого на i + 1-м шаге правила, т. е. такая точка, из которой в дереве Т' либо выходит более одной дуги, либо выходит одна дуга, но конец ее помечен иным символом, чем начало. Пусть эта «активная точка» есть ц * е» * 0* (напомним, что точка — это вхождение символа). Если на t-м шаге применяется правило ф!_1 -> так ЧТО СОг = 1Т]г—1 (прИЧеМ ВЫ-
деленное вхождение грг—i «то самое»), и если при этом < 1х<1 < U<-l'pi-il (т. e. «активная точка» содержится в грг-i), мы будем говорить, что i + 1-й шаг сильно зацеплен с i-м по отношению к размеченному выводу D' и дереву Т'.
Если в НС-грамматике каждому полному выводу D отвечает единственное растянутое дерево Т' и при этом каждый следующий шаг D сильно зацеплен с предыдущим по отношению к Т' и любому соответствующему размеченному выводу D', мы будем называть эту грамматику сильно сцепленной.
Лемма 3.1 (о сильном сцеплении). Для любой НС-грамматики Г можно построить сильно сцепленную НС-грамматику Г', эквивалентную Г и такую, что ТГ(п)^Тт{п).
Чтобы убедиться в справедливости этой леммы, достаточно заметить, что построенная при доказательстве теоремы 3.6 грамматика Г' станет сильно сцепленной, если к правилам 3-го рода фигурирующей в ее построении грамматики Г3 добавить всевозможные правила вида (а(со1))0а(со2) ->(a(®i))°P(<»2)> (сх (to,))° р (со2) —»? -> Y(®i)P(®2). y(®i)P(®2)^ y(®i)®2, где со|, ю2 — непустые цепочки длины, не большей 21, в основном словаре Гг и Р((о2), y(®i) — новые вспомогательные символы, а правила 4-го рода (а (со))0 а-> соа заменить правилами вида (а (со,))0 у (®2)-* (а (coi))0б (<о2), (а (щ))°б (со2)е (со,) б (со2), е (со,) б (<в2) -? е (®i) «г, е (со,) со2 -> Y (®i) ®2, е (®i) ®i.
где со,, со2, Y означают то же, что и раньше, а б(сог), e(coi) — новые вспомогательные символы. При этом временная сложность грамматики, вообще говоря, возрастает, но не более чем вчетверо, так что подбором постоянной с2 можно добиться выполнения нужного неравенства для временной сложности.
96
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
Введем еще следующее понятие. Для произвольной цепочки © будем называть ее сечением любой (собственный) пустой интервал (а, Р), где аир — соседние точки со. В качестве обозначения для сечения (а, р) будет использоваться также любая пара вида (А, В), где А—отрезок со с правым концом а и В — отрезок со с левым концом р.
Пусть теперь Г — сцепленная грамматика и D = = (со0....со„)—вывод в Г, являющийся отрезком пол-
ного вывода. Пусть ги ..., гт — некоторый пересчет правил Г и g — максимум длин правых частей правил Г. Пусть далее со0 = со'со" и ©" — соответственно точные потомки ©' и со^' в сог Обозначим через й' и й" соответственно наибольший конец со, и наибольшее начало со", длины которых не превосходят g. Отрезок й^й" назовем i-я зоной влияния сечения (ю^, со") = А.
Если В = х*Р*? — точка цепочки й!иС = т] * у * 0 — точка цепочки й", то расстоянием точки В, соответственно С, от центра зоны будет называться число—| Р? |, соответственно | туу | (таким образом, расстояние никогда не равно нулю).
Пусть t‘i, ..., ip — последовательность, составленная из номеров тех шагов вывода D, на которых «активные точки» содержатся в соответствующих зонах влияния сечения А. Следом вывода D на сечении А мы назовем последовательность ((k\,U\), ..., (kp, ир)), где k} — расстояние «активной точки» цепочки co^-i от центра зоны и Uj — номер правила, применяемого на шаге с номером ij. Возможен и пустой след.
Лемма 3.2 (о замещении). Пусть О{ = (а)0, ..., со„) и D<i = (0О, ..., 0т) — выводы в сильно сцепленной НС-грамматике Г, являющиеся отрезками полных выводов, U ПуСТЬ (00 = (0'(0", % = «„ = «> 0m = 0m0m>
еде со' и 0' — точные предки для со' и 0^ соответственно. Если при этом след вывода Dx на сечении (сод, со") совпадает со следом вывода D2 на сечении (0^, 0"), то из цепочки со'0" выводима в Г цепочка со'0".
Доказательство. Пусть ((kuU\)............(kp, uv)) —
общий след и (i\.......ip), (ji, ..., jp) — соответствую-
§ 3.4] оценка - Временной сложности нс-языков 97
щие последовательности шагов выводов Di и ?>2. Пусть для определенности k\ < 0. Тогда на шагах вывода Du предшествующих м (если такие имеются), может преобразовываться только цепочка Если при некотором i— 1, ..., р— 1 числа kt и kt+i имеют разные знаки, то обязательно г(+1 = it + 1. Если же kt и kt+1, например, оба положительны, то между шагами it и it+i может преобразовываться только правая половина цепочки (т. е. потомок (о^). То же верно и для вывода Dr Поэтому со'0" можно вывести из ©'б^ так: сначала преобразовывать ©', как в выводе D\, до шага i\\ затем проделать шаги, входящие в след, до первого шага — с номером it в и jt в ?>2,— Для которого числа kt и kt+i имеют одинаковые знаки; затем, если, для определенности, эти числа положительны, преобразовывать правую половину цепочки Qjt, как в выводе D2, до шага /(+1 и т. д.
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed