Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
185
этом мы будем помечать левую фигурную скобку, возникающую в г'-м уравнении (г = 1, 2, 3), цифрой г; этой же цифрой будут затем помечаться (левые) круглые скобки, «происходящие» от данной фигурной.
Итак, мы имеем:
[ S0=W, 210 = со, I 230 = со;
S1 = {coco} = со,
і
^=(CDClJa) = M,
2 2
51 = {da и Ь) = {6};
з з
22 = {{аШ} = {(а)(Щ
12 3 12 3
¦ %2 = {сос U а} = {а},
2 2
52 = ^WU 6} = {(<*(&)), ЬУ,
3 3 33 3
53 = UaH(W). b}} = {((a)(d(b))), ((a)(6))},
12333 11233 12 3
»3 = {{(a)(6)}cUa} = {(((a)(6))c), а}, 2 12 3 22123
S3 = {d{(d(b)), b}[)b} = {(d(d(b)), (d(b)), b);
S4 = {{(((a)(6))c), a}{(d(d(b))), (d{b)), b}} =
1 22 123 3333 33
= {((((a)(b))c)(d(d(b)))), ((a)(d(d(b)))),
11212 3 333 12 333
{ ((((a)(6))c)(d(6))), ((a)(rf(6))), ((((a)(b))c)b), ((a)(b))},
12123 33 12 33 12123 123
Si4=...
В результате мы одновременно получим скобочные представления структур цепочек языков, порожденных по правилам грамма- 186
Часть II. Некоторые замечательные классы языков
тики G из аксиом S, А и В. Сопоставим эти скобочные представления структур со структурами, которые приписывает данным цепочкам сама грамматика G.
На первом уровне мы имеем следующие выводы:
В
А в
((^нетерминальный
с а
(^нетерминальный, (а')
В
(?) нетерминальный, ф')
;(Ь)
3
На втором уровне деревья (а') и (?') подвешиваются к узлам А и В дерева нетерминального вывода (а):
Ha третьем уровне мы имеем для языка, порождаемого из аксиомы А, дерево, представляющее собой результат присоединения Гл. XI. Задание языков с помощью систем уравнений
187
дерева (т) к узлу S дерева (а):
А
((?> (V) j
г
Аналогичным образом получается (для языка, порождаемого из аксиомы В, на втором уровне) следующее дерево — результат присоединения терминального дерева (?') к узлу В нетерминального дерева (?):
В
то есть
(d (bj) З З 188
Часть II. Некоторые замечательные классы языков
На четвертом уровне для языка, порождаемого из аксиомы S, строятся все деревья, которые можно получить, присоединяя к узлам Л и S дерева (а) все терминальные деревья предыдущих уровней с вершинами Л и В:
S S
Мы видим, таким образом, что обе расстановки скобок совпадают. Это объясняется тем, что в ходе решения системы уравнений при каждой итерации снова появлялись простейшие схемы вывода, причем к нетерминальным узлам можно было присоединять терминальные деревья, построенные на предыдущих шагах. Структура цепочек остается той же самой, хотя в процессе решения системы уравнений деревья строятся «снизу вверх», а не «сверху вниз», как при непосредственном использовании правил грамматики.
11.1.9. Заключение
Итак, всякой КС-грамматике G можно поставить в соответствие систему уравнений, число которых равно числу ее нетерминальных символов.
Каждое из этих уравнений имеет вид
2==/(?, аз, є,
где / — многочлен.
Решением данной системы является набор языков, каждый из которых порождается в соответствии с правилами грамматики G из аксиомы, совпадающей с одним из ее нетерминальных символов.
Говорят, что этот набор языков удовлетворяет данной грамматике. Класс КС-языков совпадает с классом языков, задаваемых Гл. XI. Задание языков с помощью систем уравнений
189
системами уравнений рассматриваемого вида. В то же время мы видели, что определенная организация процесса решения системы уравнений позволяет обнаружить в цепочках языка некоторую структуру. Это побуждает нас отказаться от чисто теоретико-мно--жественной точки зрения, принятой нами вначале. Что это означает более конкретно, станет ясно в следующем параграфе.
§ 11.2. ЯЗЫКИ И ФОРМАЛЬНЫЕ СТЕПЕННЫЕ РЯДЫ
Стремление описывать последовательности языков L0, Li, L2,... ..., Ln, ... более «алгебраическим» способом и желание учитывать степень неоднозначности цепочек наводят на мысль рассмотреть многочлены, членами которых являлись бы цепочки упомянутых языков, а коэффициентами — целые положительные числа, причем коэффициент при цепочке должен быть равен числу приписываемых этой цепочке структур. Если язык-решение бесконечен, то такие многочлены на достаточно далеких шагах процесса будут иметь члены со сколь угодно высокими степенями.
Однако члены данной фиксированной степени, начиная с некоторого шага, перестают изменяться, что позволяет перейти к пределу и получить тем самым формальные степенные ряды.
Приступая к изучению языков с этой новой точки зрения, мы сформулируем как бы а priori ряд определений, опирающихся в действительности на приведенные выше эмпирические соображения. При этом для большей общности мы примем соглашение, что коэффициенты могут быть целыми числами любого знака; целесообразность этого обобщения станет очевидной ниже.
11.2.1. Степенные ряды
Пусть Vt = {fli I 1 ^ і ^ я} — терминальный словарь. Множество всех цепочек, которые можно составить из символов этого словаря, является счетным.
Сопоставим каждой цепочке хєКт некоторое целое число. Другими словами, зададим функцию, или отображение, (г) с областью определения Vt и множеством значений, содержащимся в множестве всех целых чисел Z:
