Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
s
b a bob
и имеет другую структуру: ((b)a((b)a(b))). Данный результат можно обобщить.
В самом деле, множество Sj, полученное путем аннулирования членов, не являющихся константами, соответствует выводу
(1)
Ь 182
Часть II. Некоторые замечательные классы языков
При получении S2 появляется «одночлен» ?а?; это позволяет присоединить к нетерминальному выводу
S
а
терминальные выводы вида (1), в результате чего мы получим
S
(2)
bab
При получении ?3 фигурирует тот же нетерминальный вывод, в котором к каждому из висячих 5 можно присоединить дерево вида (1) или (2).
Заключение. Мы начали изучение языков, задаваемых системами уравнений, встав на сугубо теоретико-множественную точку зрения. Однако тот факт, что мы встретились с проблемами представления структуры цепочек и с неоднозначностью, заставляет нас пересмотреть некоторые понятия и обозначения, а также ввести в рассмотрение формальные степенные ряды (см. § 11.2).
//./.7. Система уравнений, связанная с КС-грамматикой
Попытаемся обобщить представления и понятия, рассматривавшиеся до сих пор на материале частных случаев.
Пусть имеется КС-грамматика О, порождающая КС-язык L. Предположим для простоты, что ее вспомогательный словарь содержит только три символа: А, В и аксиому S. (Нетрудно будет убедиться, что это предположение не отражается на общности наших рассуждений.) Предположим, далее, что G не содержит ни правил вида С->Е, ни правил вида C->D (С, D є VA, E — пустая цепочка) и что любой ее нетерминальный символ может рано или поздно перейти в терминальный, т. е. что в G нет «непродуктивных» символов. Это предположение также не сказывается на общности рассуждений, поскольку мы уже знаем, что правила указанного Гл. XI. Задание языков с помощью систем уравнений
183
вида и непродуктивные символы можно устранить без изменения порождающей силы грамматики и даже без изменения (или с весьма незначительным изменением) структур, приписываемых грамматикой порождаемым цепочкам.
Имеется три группы правил грамматики G (в эти группы объединяются правила с одинаковыми левыми частями):
1) S-*<D„ S->(D2,..., S-*<DA;
2) Л—Wb A-+Wt;
3) B-* Qlt В-+ Q2, ..., В-+Qm;
здесь Ф, 1If и в — цепочки в словаре V = Va U Vt-
Сопоставим нетерминальным символам S, А и В «языковые» переменные 2, I и 8 соответственно. Заменим в цепочках Ф, xF и 0 каждое вхождение нетерминального символа вхождением соответствующей переменной, затем произведем объединение всех цепочек ф в формальное выражение f = Фі U • • • U Ф&')» всех цепочек 1F — в выражение g и цепочек 0 — в выражение А. Рассмотрим теперь систему уравнений
( 8 = / (8, Я, 23), (a) : a = g(8, Я, 23), I 23 = А(8, Я, 23). Примеры. 1) Для языка, порождаемого грамматикой VA = {S, А, В}, Vt = {а, Ь, с}, {S-+aSa, S-+bSb, S-+с},
мы получим уравнение, рассмотренное выше. 2) Для грамматики
S-+AB А-+Sc В-+dB А-+а В-+Ь
мы получим следующую систему уравнений:
( 8 = ??,
31 = 8с U а, I 23 = dS8U&.
') Здесь <Dj — выражение, полученное из Ф« заменой S, А, В на 5, © соответственно. — Прим. ред. 184
Часть II. Некоторые замечательные классы языков
Заметим, что аксиома участвует в этих уравнениях «на тех же правах», что и остальные вспомогательные символы. Переменные $ и 23 играют роль, аналогичную роли 8: они соответствуют языкам, порождаемым грамматиками, имеющими те же словари и правила, что и данная, но другие аксиомы: в одной грамматике аксиомой является А, в другой — В.
Неизвестным в нашей системе уравнений является тройка языков (Ls, La, Lb), грамматики которых имеют в качестве аксиом символы 5, А и В соответственно.
Решая эту систему, мы будем действовать точно так же, как в разобранном выше частном случае. Во всяком решении каждый из трех языков обязательно содержит цепочки, играющие роль «свободных членов» правой части соответствующего уравнения.
Исходя из начальной тройки
(80 = ю, 3tO = ю, 23o = o),
мы будем последовательно образовывать тройки, входящие в решение:
[2, = / (20, «о, 23о); Я, - ff (S0. «о, «о); », = А (80, S0)];
[8„ = /(8,,-1, »„_,); a„ = ff(2„_„ ...); »i = A(2„-i, ...)];
В качестве «индуктивного предела» мы получим [8,?,?], где 8 = 8i U е2 U ..., а = Иі U И2 U ..., 23 = »1 U 232 и ..., т. е. единственную тройку — наименьшее решение системы. Нетрудно показать, что его компоненты совпадут с языками, порождаемыми по правилам грамматики G из аксиом S, А и В соответственно 1J.
11.1,8. Пример решения системы уравнений
Решим в качестве примера систему уравнений, выписанную выше:
і 8-St»,
I Я-ScUa,
1 23 = ^231! b.
В промежуточных результатах наших выкладок мы будем сохранять расстановку скобок, индуцированную ходом решения. При
') Можно показать также, что (при условии отсутствия в исходной грамматике правил вида A-* E и A-* В) наименьшее решение является единственным. Доказательство аналогично приведенному в примечании ') на стр. 117 для частного случая. — Прим. ред. Гл. XI. Задание языков с помощью систем уравнений
