Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Хомский Н. -> "Формальные свойства грамматик " -> 35

Формальные свойства грамматик - Хомский Н.

Хомский Н. Формальные свойства грамматик — Москва, 1963. — 100 c.
Скачать (прямая ссылка): formalsvoystvagrammatik1963.djvu
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 45 >> Следующая


Теорема 34 фактически доказана только для нормальных грамматик, удовлетворяющих дополнительному условию, что если А-* -*BC есть правило, то ВфС, и если A-^fBty и Л-+);?ш суть правила, то x=tP и ty=®-і Нетрудно показать, что этн дополнительные условия не влияют на порождающую способность. Кроме того, только от деталей доказательства зависит вопрос об отбрасывании этих ограничений (и даже многих, если не всех ограничений, которые обусловливают нормальность).

Доказательство теоремы 34 слишком сложно, чтобы излагать его здесь, но мы опишем процедуру ЧГ и проиллюстрируем ее на примере. Посмотрим сначала, чем теорема 34 отличается от теоремы 19 в разд. 4.2, которая утверждает, что если задана модифицированная нормальная грамматика G1 то существует конечный преобразователь Т, обладающий следующим свойством: T преобразует х в цепочку г, которая сводится к е тогда и только тогда, когда г есть структурное описание, поставленное в соответствие цепочке х грамматикой Q. В этом случае Ф есть тождественное преобразование, т. е. выход преобразователя T имеет в точности вид структурного описания, определяемого грамматикой G. Кроме того, здесь мы не ограничены только грамматиками без самовставления.

Однако преобразователь, существование которого гарантируется теоремой 19, не является сильно эквивалентным G в смысле определения 9. Таким образом, Ty имея на входе х, может возвращаться в S0 и закончить работу с цепочкой у на ленте памяти, которая не сводится к г (и не является структурным описанием, поставленным в соответствие X грамматикой G).

В действительности, причина, по которой преобразователь Т, сопоставленный с бесконтекстной грамматикой в теореме 19, представляется на первый взгляд более мощным, чем преобразователь T', сопоставленный с бесконтекстной грамматикой в теореме 33, состоит в том, что Т, но не Т’ эффективно использует потенциально бесконечную память прн решении вопроса о допущении цепочки с заданным структурным описанием, так как это решение требует анализа сводимости к е (неограниченной) цепочки на ленте памяти. Из теоремы 33 мы знаем, что теорема 34 является самым сильным возможным результатом, касающимся сильной эквивалентности бесконтекстных грамматик и устройств со строго ограниченной памятью.

Чтобы проиллюстрировать теорему 34, предположим, что G — нормальная грамматика без самовставления, удовлетворяющая
206

И. Хомский

дополнительному условию, приведенному сразу после теоремы 34. Пусть К — множество последовательностей ((Ль ... ,Ат)\, удовлетворяющих следующему условию: для каждой пары І, /, такой,

что I имеет место А[-*'рАи1$ и A1Ф Aj. Теперь

мы можем построить грамматику С* с нетерминальными символами, представленными в виде [S1... BJ1 (1=1, 2), где Bj — нетерминальные символы G, следующим образом ¦).

Пусть (B1.......Bn) ? К.

1) Если Bn -э- а, то [B1. . . BJ1-S- a [B1. . . В„]2.

2) Если В„-»-СО, где С ф B1 ф D (i п), то

а) [B1... B11J1-HB1... B11CJ1,

б) [B1. . . BnCJ2 -s. [B1. . . BnDj1,

в) [B1. . . BDJ2 -S- [B1. . . BnJ2.

3) Если Bn-S-CD, где B1 = D для некоторого то (59)

а) [B1. . . BnJ1 -S- JB1. . . BnCJ1,

б) [B1. ..BnCJa [B1... BjJ1.

4) Если Bn -S- CD, где Bi = С для некоторого і п, то

а) [B1. . . BiJ2 —>¦ [B1. . . BftDj1,

б) [В]. . . BnDJ2 [B1.. . BnJ2.

Теперь мы можем доказать, что в G существует S-вывод цепочки z тогда и только тогда, когда' в G* существует [SJi-вывод цепочки z[SJ2 (теорема IO в работе [81), где S— начальный символ в G.

Правила в G все имеют вид А-*аВ, где а=е, если онн не являются правилами, полученными по пункту 1) конструкции (59). Следовательно, мы можем рассматривать О* как конечный автомат. Предположим теперь, что мы снабдили автомат новым состоянием

S0 н дополнительными правилами

S0-MSJ1, [S2J -s. S0. (60)

Если S0 считать начальным состоянием, то устройство становится

г) Мы можем использовать символ одинаково для грамматики GhG*, так как вид их нетерминальных си\ґволов различен.
Формальные свойства грамматик

207

слабо эквивалентным G. Чтобы превратить это устройство в преобразователь, мы должны снабдить его правилами выдачи выходного символа при переходе из состояния Q1 в состояние Qj и считывании символа ak. Мы считаем, что выходной алфавит состоит из множества нетерминальных символов G* (т. е. множества символов вида IBv--BnIi, которые теперь означают состояния автомата). Мы будем говорить, что когда устройство переходит в состояние Q, оно печатает выходной символ Q. Этим завершается конструкция lIr, требуемая теоремой 34, которая связывает конечный преобразователь T с грамматикой без самовставления G. Если G порождает х, то T преобразует входную цепочку х в выходную'цепочку о, где а есть запись последовательных состояний, через которые T проходит, допуская (порождая) х.

Эта последовательность а в действительности содержит полную информацию о структурном описании, сопоставленном х грамматикой G, и обратно, для каждого структурного описания, сопоставленного цепочке X грамматикой G, существует последовательность состояний о, в которую T преобразует х и которая точно представляет строение этого структурного описання. Дело в том, что названия состояний в действительности содержат информацию о некотором поддереве размеченного дерева, сопоставленного цепочке х грамматикой G; из данной последовательности состояний это размеченное дерево может быть полностью восстановлено. Можно построить процедуру Ф такого типа, как это описано в определении 9, которая будет превращать выход T в структурное описание (скажем в структуру помеченных скобок) его входа и обратно. Такое построение подробно описано у Лангендоена [37Iі). Следовательно, преобразователь T, построенный при помощи процедуры ЧГ из конструкций (59) и (60), сильно эквивалентен G.
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 45 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed