Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
г)г, где коэффициент ( я(х, i, j), г > представляет собой число различных путей, переводящих T из S1 в Sj, прн которых г получается на выходе. Тогда можно представить преобразователь Т, имеющий п состояний, при помощи гомоморфизма отображающего Vr в кольцо квадратных матриц n-го порядка, элементы которых есть полиномиальные выражения над выходным алфавитом Т.
Матрица у.х с элементами (рх)0 =к(х, i, j) представляет поведение преобразователя T при его переходе из состояния S1 в состояние Sj под действием цепочки х. Многие задачи теории преобразовании сводятся прн этом к проблемам оперирования с матрицами, что позволяет применить хорошо разработанную технику [61, 66]. Более того, при этом общем подходе возникают некоторые новые проблемы. Так, в этом изложении мы ограничились лишь положительными степенными рядами, т.е. рядами с неотрицательными коэффициентами. Обобщая этот подход, можно рассматривать алгебраические элементы (элементы кольца степенных рядов), имеющие как положительные, так и отрицательные коэффициенты н удовлетворяющие системам уравнений, которые могут иметь н отрицательные коэффициенты в полиномиальных выражениях.
218
И. Хомский
Степенной ряд г с положительными н отрицательными коэффи--циентами можно представить в виде разности двух положительных степенных рядов г' H г’’. Коэффициент прн цепочке X в ряде г будет при этом равен разности между числом способов, которыми грамматика, соответствующая ряду г', порождает цепочку х, и числом способов, которыми порождает эту же цепочку грамматика, соответствующая ряду г''. Основание ряда г есть множество тех цепочек, которые порождаются этими двумя грамматиками неодинаковым числом способов.
Шюценберже исследовал семейство формальных степенных рядов г—г'— г", где г’ и г" удовлетворяют односторонней линейной грамматике н, следовательно, основаниями их являются регулярные языки ( эти формальные степенные ряды соответствуют рациональным функциям, еслн отождествить цепочки, получаемые друг из друга перестановкой их элементов), н охарактеризовал основания этих формальных рядов в терминах допустимости некоторым классом ограниченно-бесконечных автоматов [611. Он показал также, что подобный ряд г может иметь в качестве основания язык, не являющийся бесконтекстным, и, с другой стороны, что существуют бесконтекстные языки, не являющиеся основанием какого-либо подобного степенного ряда [66 ]. Дальнейшее обсуждение этих и связанных с этими вопросов можно найти в вышеприведенных работах и в работе Шюценберже и Хомского [69].
Чтобы показать на примере использование введенных выше понятий, приведем следующий общий результат, относящийся к регулярным языкам и связанный с вопросами неоднозначности бесконтекстных языков, обсуждавшихся в разд. 4.5.
Теорема 35. Пусть G — односторонняя линейная грамматика, которой удовлетворяет формальный степенной ряд г и которая порождает язык L(G)=sup(r). Пусть Lk — 'x\{r, x)-^k\. Тогда при каждом k Lk есть регулярный язык (Шюценберже, личное сообщение).
Пусть N — множество натуральных чисел, k — фиксированное целое число, a Nm— полукольцо квадратных матриц порядка M с элементами из N. Доказано [66], что если G и г удовлетворяют условиям теоремы 35, a U — множество всех цепочек в Vt (т.е. свободная полугруппа с образующими а ? Vt), то
существует такое М<со и такой гомоморфизм іл: U в Nm, что< г, к > =(Jax)i_ w . (78)
Пусть /C=IiOC1Cfe) и N->K, определенное условиями
P (п) — п для п С ft; р (n) = ft для п > k. (79)'
Формальные свойства грамматик
219
Определим сложение и умножение на множестве к, положив
і®У-[Ц» + /). І®І = НЧІ (80)
К есть полукольцо н легко показать, что Jj есть гомоморфизм, отображающий N на К- Пусть Km будет множеством (даже полукольцом) матриц порядка M с элементами из К- Тогда [) естественным образом распространяется в гомоморфизм fi: Nm-^Km-
Определим ср(дг)=р [;л(jc) I, где ji удовлетворяет условиям предложения (78). Тогда ср(х) принадлежит Km для x^U. Очевидно, что
(ср X), . = < Г, X > , если < Г, X > k,
/О 1 \
*)l, M = k' если < Г, X ) >k.
Ho Km есть мультипликативная полугруппа конечного порядка, и для k'<k
Lf = \х\ (г, х > <й'| -
-¦ )-=\xW(x) ? Q);
здесь первый знак равенства имеет место по определению, а второй — в силу предложения (78); Q есть подмножество множества <p(U), содержащее у(х) в том н только в том случае, когда (yx)ilA)^fe'. Хорошо известно, что еслн і —• гомоморфизм, отображающий подмножество множества U на конечную полугруппу Я, то множество ¦і-1(Н) = {хіф(х) ?Я| является регулярным языком. Следовательно, Lk' также есть регулярный язык.
Из того, что при каждом k Lk есть регулярный язык, в снлу основных свойств регулярных множеств, следует (см. теорему 1), что для каждого k множество цепочек х, для которых <r,x)=k, и множество цепочек, для которых < Г, X ) будут регулярными языками. В частности, множество тех цепочек х, для которых
< г,X > >2, также есть регулярный язык. Это—множество цепочек, неоднозначных относительно G в смысле разд. 4.5.
