Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Пусть, например, имеется грамматика G с правилами
А-уАА, А^-а, А->-Ь\
(72)
Формальные свойства грамматик
215
ей соответствует система уравнений, состоящая из одного следующего уравнения:
А = а + Ь +Да. (73)
В этом простейшем случае имеем Oi=(^i1)1 где
a + b -V 02 — а Ь ,
A— a i- b -1- (г])2 = a + b + (а + Щ1 =
— а + Ь + a2 -f ab -)- ba + b'z,
г3,= a + b + ( г?)2 = < г і , х ) *, где (74)
< г\ , х > =I для каждой цепочки длины 1, 2 и 4,
< /¦?, х > =2 для каждой цепочки длины 3,
г\ = а 1 Ь + ( г?)2 н т. д.
Коэффициенты при каждой цепочке длины 3 остаются равными 2 в любом ri1(t>3), при цепочках большей длины коэффициенты увеличиваются. Таким образом, в этой грамматике имеется только один
А А А
/\ /\ / \
AA AAAA
1I Al' Л
а Ь AAa а А А
/\ /\ /\/\ /\
AA RA AAAA AA
AA / \ I / \ I I / \ I А
AAAA AAb AAb а А А а А А
IIIIAI IA IA Al
а Ь а Ь AAa а А А Ь A A AAb
M Il и и
Qb Ъ a a b Ь о
Рис. И. С-маркеры, иллюстрирующие неоднозначность грамматики (72).
способ порождения для каждой цепочки длины 2, ровно два способа порождения цепочки длины 3, пять способов порождения цепочки длины 4 и т.д., как можно видеть из примеров, приведенных на рис. II. Ряд гх, являющийся пределом так определенных г\, будет
*
216
Н. Хомский
решением уравнений (73). Его основание есть терминальный язык L(G)1 порождаемый грамматикой G.
В этом случае L(G) есть множество всех цепочек в алфавите Iа,Ь], н мы знаем, что существует эквивалентная грамматика G*, имеющая в качестве решения характеристический степенной ряд (т.е. коэффициенты которого равны 0 либо 1 — в данном случае все равны 1, за исключением коэффициента прн е) с основанием L(G). Примером может служить грамматика Q*, заданная уравнением
А=*а-\-Ь+аА+ЬА. (75)
Как было отмечено выше (разд. 1.2, теорема 1), для каждого конечного автомата существует соответствующий ему детерминированный автомат. Говоря в терминах этого раздела, каждый регулярный язык порождается грамматикой G, которой удовлетворяет некоторый характеристический формальный степенной ряд. Язык, порождаемый грамматикой из примера (72), регулярен; мы можем это видеть из того факта, что он порождается односторонней линейной грамматикой (75). Однако, как утверждает теорема 29 из разд. 4.5, существуют бесконтекстные языки, которые нельзя представить таким способом при помощи характеристического ряда; именно теорема 29 утверждает существование языка L, являющегося основанием ряда г, который удовлетворяет бесконтекстной грамматике, но не являющегося основанием никакого характеристического ряда, удовлетворяющего бесконтекстной грамматике.
В качестве еще одного примера для иллюстрации этих понятий рассмотрим следующие грамматики:
S-*a+bSS, - (76)
S а S b S. (77у
Интерпретируя Ь как знак импликации и а как переменную, мы видим, что грамматика (76) порождает множество правильно построенных формул имплнкативного исчисления с одной свободной переменной в бесскобочной записи Лукасевича н соответственно имеет характеристическое решение. Грамматика (77) порождает множество цепочек, получающихся нз формул этого исчисления в обычной записи опусканием скобок, н ее решением является степенной ряд, в котором коэффициент прн данной цепочке равен числу различных способов расстановки скобок, превращающих эту цепочку в правильно построенную формулу.
Введенное Шюценберже понятие представляющих множеств, перечисляемых порождающим процессом в терминах формальных степенных рядов, обусловлено потребностями изучения языка. Как подчеркивалось не раз, мы в конечном счете заинтересованы в
формальные свойства грамматик
217
изучении процессов, порождающих системы структурных описаний, больше, чем процессов, порождающих множества цепочек, т.е. в сильной, а не в слабой порождающей способности. Кратко описанный здесь подход является первым шагом в этом направлении, поскольку он учитывает число структурных описаний, приписываемых цепочке (хотя н не сами этн структурные описания). Он также дает нам вполне естественный подход к изучению недетерминированных преобразователен.
Напомним, что преобразователь, вообще говоря, может обладать двумя различными видами недетерминированности. Находясь в состоянии Si н считывая символ а, он может иметь право выбрать переход в то нли иное состояние. Выбрав переход в состояние Sj, он может, далее, иметь право напечатать ту или иную цепочку на выходной ленте. Мы скажем, что цепочка x=b1...bm (где Ь(—символ входного алфавита) переводит преобразователь T из состояния
S1 в состояние Sj с выходом X=X1...хп, если T имеет правила
Фк, Si4)-+(S,A+i, хк) для некоторых I1......in+1 Cf1 = I-; Imtl =/) и
для каждого k<^tn. Тогда цепочка х может переводить T из Si в 5/ со многими различными выходами, и оиа может переводить T из S1B Sj с выходом х многими различными путями (с различным разложением х).
Естественно поэтому попытаться представить результат действия входной цепочки X на преобразователь T при переводе его из S1 в Sj прн помощи полиномиального выражения к{х, і, j) =^] < ъ(х, i, j),
