Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
q2 (г) а2 q3 (г), q3 (г) -> BqA (г), q4 (г) а3 -> q}\
5) правилу вида А -> аха2а3В С (ах,а2,а3 В, С е?)
сопоставляется система -> ^ (г), Aq 1 (г) -> д2 (О»
q2{r)a2-+q3(r), q3{r)->Cq4(r), q^r) а3-> q5(r), q5(r)->Bq}.
Здесь qi(r) — состояния, различные при разных i и при разных г. Единственным заключительным состоянием является q0.
Из самой конструкции ясно, что каждое вычисление машины М' удовлетворяет нужному условию. Эквивалентность Г и М' доказывается без труда; мы предоставляем это читателю. [Указание. Между вычислениями М' и упорядоченными размеченными выводами в Г устанавливается соответствие таким образом, что каждой промежуточной цепочке вывода, имеющей вид хХ, где х е 1/*, 1е №*, отвечает участвующая в вычислении ситуация, при которой прочитанная часть входной цепочки есть х, а на рабочей ленте записана цепочка Я.]
Замечания. 1. Теорему 6.4 нетрудно было бы усилить, потребовав, чтобы между каждыми двумя «рабочими» шагами читалось не менее s входных символов, где s — произвольное фиксированное натуральное число.
2. Машина, удовлетворяющая требованию теоремы 6.4, является Э-машиной без растяжения (§ 3.2). Таким образом, иерархии основных классов грамматик: ГгэНСгэБ^зА отвечает иерархия классов Э-машин: произвольные Э-машины :э Э-машины без растяжения
МП-машины без растяжения гэ конечные автоматы. Можно было бы включить в эту иерархию также и соответствующие машины для классов языков, рассмотренных в §§ 5.3 и 5.4 (упражнение 6.9).
200 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ 6 Б-ГРАММАТИКАХ [f\)l. 6
§ 6.3. Доминационные грамматики
Для лингвистических приложений . полезно иметь возможность задавать язык таким образом, чтобы каждой его цепочке сопоставлялось описание ее синтаксической структуры в виде дерева подчинения, подобно тому, как с помощью НС-грамматики цепочкам сопоставляются описания в виде систем составляющих. Ввиду наличия простой связи между системами составляющих и проективными деревьями подчинения (§ П1.3) для этой цели можно использовать те же НС-грамматики, некоторым образом «иерархизуя» их, так, чтобы для каждой системы составляющих, которую «выдает» данная грамматика, автоматически указывалась некоторая иерархизация и тем самым определялось дерево подчинения. Примером могут служить упоминавшиеся в § 6.1 прямая и обратная иерархизации категориальных грамматик. Сейчас мы проведем соответствующие построения в общем виде, ограничиваясь, впрочем, случаем Б-грам-матик (о распространении на произвольные НС-грамматики см. упражнение 6.18).
Будем называть доминационной грамматикой (Д-г р а м м а т и к о й) упорядоченную пару G =
— (Г, }), где Г = (У, W, /, R)— Б-грамматика без правил вида А-+В, A, B^W, я А-*a, A^W — {/}, йеУ (такие Б-грамматики будут в дальнейшем называться удлиняющими), и f — отображение, сопоставляющее каждому правилу f = кроме правил
вида / —>? а, а е V, некоторое непустое подмножество f(r) множества {1, ..., | со |}.
Если г = А—*? срспр е R, а е V U W и | фа | е f (г), мы будем называть вхождение ф *• а * гр символа а в правую часть г отмеченным.
Пусть Т — дерево полного вывода в Г и С — соответствующая система составляющих; поскольку грамматика Г удлиняющая, дерево Т, рассматриваемое как дерево без меток, изоморфно системе С. Пусть далее а — произвольный невисячий узел Т и — правило, при-
меняемое на шаге вывода, отвечающем узлу а. Назовем отмеченными те из подчиненных а узлов, которые соответствуют отмеченным вхождениям символов в ы.
ДОМИНАЦИОННЫЕ .ГРАММАТИКИ
201
Будем называть иврархизацию С' системы С допустимой (для G), если все главные (т. е. принадлежащие С/) составляющие отвечают отмеченным узлам Т. По теореме П1.2 существует единственное связанное с (С, С') (и определяемое по (С, С') эффективно) дерево подчинения D для цепочки х = ц{Т) \ мы скажем, что D сопоставляется цепочке х грамматикой G.
Замечание. Возможен другой способ определения Д-грамматик, при котором они трактуются как частный случай удлиняющих Б-грамматик. Для этого нужно:
а) ввести для каждого символа ае KU W «двойника» — новый вспомогательный символ а'; б) заменить каждое правило r^/->-a(ael/) системой правил, отличающихся от г тем, что в правой части каждого нового правила одно вхождение символа отмечается штрихом, а также добавить правила а'—*а для всех ае У1)W. Каждому дереву выводу в такой грамматике отвечает единственная иерархизованная система составляющих: главными составляющими в ней будут те, которые соответствуют узлам, помеченным штрихованными символами.
Будем говорить, что Д-грамматики Gi = (Г1, fi) и G2 = (Гг, /г) сильно эквивалентны, если Г1 эквивалентна Гг и при этом дерево подчинения тогда и только тогда сопоставляется цепочке грамматикой Gi, когда оно сопоставляется той же цепочке грамматикой G2. Скажем, кроме того, что Б-грамматика Го и Д-грам-матика G = (Г, f) слабо эквивалентны, если Го эквивалентна Г, и сильно эквивалентны, если они слабо эквивалентны и при этом: а) для всякой системы составляющих С, отвечающей полному выводу какой-либо цепочки в Г, найдется дерево подчинения, сопоставляемое той же цепочке грамматикой G и согласованное с С; б) для всякого дерева подчинения Т, сопоставляемого какой-либо цепочке грамматикой G, найдется система составляющих, отвечающая некоторому полному выводу той же цепочки в Го и согласованная с Т. Будем говорить, наконец, что Б-грамматика Г вкладывается в Д-грамматику (Г, f).
