Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
4.7. Определимость языков системами уравнений
Пусть G — бесконтекстная грамматика; ее нетерминальные символы обозначим по порядку /I1........An, где A1— выделенный на-
чальный символ. Каждому Ai соответствует множество S1 терминальных цепочек, доминируемых символом Аг; т. е. Ei= IxlAi-^x) в наших обычных обозначениях. Сопоставим грамматике G последовательность множеств (E1,...,Eri), состоящих из терминальных цепочек, где E1— терминальный язык, порождаемый грамматикой G. Мы скажем, что данная последовательность множеств удовлетворяет грамматике G при данном порядке нетерминальных символов. Очевидно, каждый член удовлетворяющей последовательности будет терминальным языком, порождаемым некоторой бесконтекстной грамматикой, а именно грамматикой, отличающейся от G только выбором начального символа.
Предположим теперь, что мы рассматриваем нетерминальные символы G как переменные, значениями которых являются множества цепочек в терминальном словаре. Мы определяем полиномиальное выражение над переменными A1,...,An как выражение вида
9i + • • • + ?*. (64)
где каждая <рг есть цепочка в К, а единственные нетерминальные символы, встречающиеся в выражении (64), суть Ax....,An. С помощью такого полиномиального выражения, как выражение (64), можно задать функцию /, отображающую последовательность мно-
Формальные свойства грамматик
211
жеств цепочек в Vt на множество цепочек в Vr следующим образом. Если дана последовательность где Ei есть множество
цепочек в Vt, то пусть /(E1,...,En) будет множеством'цепочек, которое получится^ если в выражении (64) заменить каждое вхождение A1 знаком Eil обозначающим множество Ei, н затем интерпретировать знак + как теоретико-множественное объединение, а соединение (конкатенацию) — как теоретико-множественное (прямое)
произведение (т.е. если А и В — два множества, то АВ—{уг\у?Л,
г?В); хА = (ху1у?А}; Ax=Iyxjy ^Aj). Например, функция [(А, В), заданная полиномиальным выражением
а + А а + В аА, (65)
отображает пару множеств \х, у}, (г, OiJ на множество [а, ха, уа, zax, гау, шах, иау).
Если дана бесконтекстная грамматика G с нетерминальными Ai,...,An. сопоставим каждому А,¦ полиномиальное выражение
-f-ера, где Ai-Vtp1,.суть все правила G1 в которых Ai встречается в левой части. Рассмотрим теперь систему уравнений
Ai — fi (A1........А„),
' (66)
Л„ = /„(А.........An),
где /;—функция, заданная полиномиальным выражением, сопоставленным символу Ai. Известно, что такая система уравнений имеет единственное минимальное решение; иначе говоря, существует единственная последовательность множеств ElllillEn, удовлетворяющая этой системе уравнений (в качестве значений для A1,... ...,An соответственно), и такая, что если E'lt.есть другое решение этой системы, то EiCE',. для каждого /. Далее, ясно, что последовательность множеств, являющаяся минимальным решением для уравнений (66) (в дальнейшем мы будем называть ее просто решением [the soiutionj), есть та самая последовательность множеств, которая удовлетворяет грамматике G в смысле первого абзаца этого раздела, a E1 есть терминальный язык, порождаемый грамматикой G.
Несколько иначе сформулировав это замечание, мы можем рассматривать уравнения (66) как задающие функцию /, такую, что
f (A1,..., An)^ IfAA1,..., А„).../„ (A1,..., An)]. (67)
Неподвижной тонкой функции / называется такая последовательность (E1....,?„), что /(E1,...,?„)=(?!,...,?„). Тогда у функции / существует единственная минимальная неподвижная точка, совпа-14*
212
Н. Хомский
дающая с решением уравнений (66); т.е. это последовательность множеств, удовлетворяющая грамматике G.
Для нахождения решения уравнений (66) можно определить следующий рекурсивный процесс. Будем строить последовательность вй, O1,..., каждый член которой представляет собой кортеж п множеств, следующим способом: O0 есть кортеж (0,...,0), где 0 есть пустое множество. Для каждого (>0 положим ог+1 =/(о,). Если теперь 0,=(0'!,...,о'л), определим о так: O=Iim о,=(о»........о"),
л ^ 05
где O1J=Zjo/1)- Эта последовательность о и будет решением уравнений (66). Она будет также неподвижной точкой для функций f из (67) н последовательностью множеств, удовлетворяющей грамматике G, а о“ будет терминальным языком, порождаемым G. Будем говорить, что каждое определимо из уравнений (66): определи.' мый язык есть множество, определимое подобной системой уравнений. Очевидно, что определимые языки суть в точности бесконтекстные языки.
Кратко обрисованная здесь схема рассмотрена подробнее Гинзбургом и Райсом [20] и служит основой для исследований, проведенных в этой работе и продолженных в статьях [21, 22]. Эта работа первоначально выросла из исследований по языкам вычислительных машин (в частности, по АЛГОЛу) н привела к некоторым интересным результатам, касающимся этих систем; к ним мы вернемся в разд. 4.8.
Этот подход к бесконтекстным языкам был обобщен Шюценбер-же (см., в частности, работы [63, 65, 691). Пусть имеется отображение/, сопоставляющее каждой цепочке х в Vt неотрицательное целое число f(x). Можно представить f формальным степенным рядом г.
