Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
г — < г, X ) X, (68)
X
над элементами at ^ Vt , где общий коэффициент < г, х > =f(x). Мы скажем, что формальный степенной ряд г — характеристический, если < г, х > для каждогох равно О илні, т.е. если ( г, х > представляет собой характеристическую функцию. Определим основание (support) формального степенного ряда г [=sup (г) ] как множество тех цепочек, для которых <r, X > фО. То есть основание можно получить, если рассматривать знак ,+ как обычное теоретико-множественное объединение, а пх, где п — коэффициент прн х, как хф...+х п раз (что сводится к отождествлению пх с х прн пф0).
1J Под суммой здесь имеется в виду теоретико-множественное объединение.— Прим. перев.
Формальные свойства грамматик
213
Заметим, что формальный степенной ряд становится обычным степенным рядом над переменными O1 ? Vr ,если считать их коммутативными, т.е. еслн отождествлять цепочки, которые могут быть получены друг из друга перестановкой элементов.
Множество формальных степенных рядов замкнуто (среди прочих) относительно следующих операций:
(а) Умножение иа целое число: коэффициент (пг, х У прн х равен п < г,х) .
(б) Сложение: коэффициент < г+г',х > при
х в ряде г+г' равен < г, х > + < г’, х > , (69)
(в) Умножение: коэффициент {гг',х) при х в ряде гг' получается разложением х во всевозможные произведения уг=х и суммированием всех членов {г,у} (г',г),
т.е. ( rr',X > < г,у > {г',г) по всем
уг, таким, что уг=х.
Отметим, что сложение аналогично теоретико-множественному объединению, а умножение — образованию прямого произведения. Таким образом, мы имеем sup (r+ /) = sup(r) Usup(r'), sup(rr') = sup (г) • sup(r'). (70)
Можно также определить операцию, аналогичную пересечению множеств, как операцию ®, такую, что г0г' есть степенной ряд с коэффициентом rfg)r' прих, равным < г,х > < г',х > . Так же легко определяются операции, соответствующие замыканию и —для некоторых случаев — дополнению.
Если дана грамматика G с нетерминальными ..........An, то пусть
/г (л:) — число структурных описаний, приписываемых цепочке х грамматикой G1, которая получится, если в G принять Ai за начальный символ (мы можем для определенности считать, что структурные описання представляют собой системы помеченных скобок, порождаемых грамматикой так, как это описано на стр. 170; в этой случае ft(x) равно числу цепочек, порождаемых грамматикой Gi, которые при опускании скобок дают цепочку х). Пусть гг — формальный степенной ряд, который каждой цепочке х сопоставляет коэффициент (г,-,.х > =ft(x). Тогда Isup(ri),.,.,sup(r„) ] есть последовательность множеств, которая удовлетворяет грамматике О в вышеописанном смысле; sup(r,) есть терминальный язык L(G), порождаемый грамматикой G; < гг,х ) =0 тогда и только тогда, когда X^L(G)-, { гих > —п тогда и только тогда, когда G дает га неэквивалентных выводов и, значит, п различных структурных описаний
для х. Мы говорим, что последовательность (C1....гп) удовлетворяет
грамматике G. Данное выше определение удовлетворяющей последовательности является частным случаем этого определения, при
214
И. Хомский
котором рассматриваются те формальные степенные ряды, которые получаются из определенных здесь рядов отождествлением всех неравных нулю коэффициентов.
Последовательность (г1,...,гп), удовлетворяющая грамматике G, может быть получена, точно так же как и раньше, методом итераций. Рассматривая G в виде системы уравнений вида (66), мы строим бесконечную последовательность o0.°i,-". где Qi = а
r‘j есть формальный степенной ряд (в действительности имеющий лишь конечное число членов; иначе говоря, Ti1 будет полиномиальным выражением над нетерминальными символами G). Как и прежде, считаем, что уравнения (66) определяют функцию /, которая в этом случае отображает последовательность (гх,...,г^ на последовательность l/^.......г„,),...,fn(rt.г„)]. Функция ft задана, как
н прежде, полиномиальным выражением tPi+...+<?*, где (1 </<?) суть все правила G, имеющие А в левой части. Операции + и соединение интерпретируются теперь не как объединение н произведение, но как соответствующие им операции над степенными рядами (см. определение (69)). Определим о0 как последовательность' (/-0J,.../0„), где каждый г°(есть «пустой» степенной ряд, у которого все коэффициенты равны нулю. Примем Ojfl =Z(Oi). Как и прежде, возьмем o=lim Oi= (г“ ,...,г“), где г/“ определен еле-
І-* Од
дующим образом.
Пусть л; — цепочка длины k, а г^, как и выше,—
/-й член последовательности о4. Тогда коэффициент при х в степенном ряде г“ определяется следующим условием:
< /¦;, х ) = { г* , х ) . (71)
В самом деле, нетрудно показать, что в последовательности з0, 0I,... коэффициенты при цепочках длины k не изменяются после оА. Следовательно, о действительно является пределом этой последовательности; г” есть формальный степенной ряд, порождаемый грамматикой G, если A1 есть начальный символ G, а его основание, sup(r“), есть язык, порождаемый G в ранее определенном смысле; '",, кроме этого, ставит в соответствие каждой цепочке х, принадлежащей s up(r“), ее коэффициент < ґ’, X ) , который представляет собой меру степени неоднозначности, приписываемой грамматикой G цепочке х. В дальнейшем, когда мы буд;м говорить о стгпенном ряде, удовлетворяющем G, будет иметься в виду ряд г" .
