Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Заметим, что умножение языков дистрибутивно относительно объединения:
L (L1 U L2) = LL1 U LL2; (L1 U L2) L = L1L U L2L.
Мы можем теперь ввести понятия переменной, формального выражения и функции.
11.1.1. Переменные и выражения
Рассмотрим семейство языков [LuLi, ...}; будем считать, что они определены над одним и тем же терминальным словарем Vr и что мы имеем вспомогательный словарь Va, который годится для описания грамматик всех этих языков.
Под языком мы будем понимать, как и раньше, всякое множество терминальных цепочек.
«Языковые» переменные. Нас будут интересовать переменные 8, ЯЯ, Sft, . .., значениями которых служат языки.
Пример. Пусть рассматривается класс КС-языков и введена переменная 8, пробегающая этот класс. Одним из «допустимых» значений переменной ? является язык Lm:
2 = Lm = {хсх I X е {а, Ь}*}.
Формальные выражения. Используя константы t, а, ... (фиксированные терминальные цепочки), переменные й,®1, Sd,... и символы операций, мы можем строить формальные выражения вроде
fg; t& (J a; SaM (J a&; .... 176
Часть II. Некоторые замечательные классы языков
Если значениями переменных, входящих в подобное выражение, являются те или иные языки, то и значением самого выражения будет некоторый язык.
Примеры. 1) Пусть имеется алфавит {а, и, к, л, о, п, р, т, ч, ь, я} и константа t = 'npo'\ рассмотрим выражение t2. Придадим переменной ? значение L, где
L = {кричать, лаять, к};
L — конечный язык, состоящий из трех терминальных цепочек.
Соответствующим значением выражения t? является
L' = {прокричать, пролаять, прок},
т. е. другой конечный язык, состоящий также из трех цепочек.
2) Придадим константе t значение ab и переменной ?—значение Lm, где
Lm = {хсх I X е {a, ft}*}.
Тогда выражение t? примет значение
{abc, abaca, abbcb, ababcba, ...}
— язык, который получается приписыванием цепочки ab слева ко всем цепочкам языка Lm.
Многочлены. Если формальное выражение образовано из терминальных констант и языковых переменных с помощью только двух операций — умножения и объединения, — мы будем называть его многочленом; порядок выполнения операций объединения («порядок членов») в многочлене безразличен.
Пример. Выражение аЬ8 U aSR U ШЬа8 есть многочлен от двух переменных ? и ЯК, состоящий из трех «членов».
11.1.2. Функции и уравнения
Ясно, что задание формального выражения равносильно заданию некоторой функции. Если каждой переменной в выражении отвечает некоторое семейство языков, то соответствующие значения этого выражения также образуют некоторое вполне определенное семейство языков. Таким образом может быть задано отображение множества допустимых наборов значений аргументов на множество допустимых значений выражения, т. е. функция, определенная на семействе наборов языков и в качестве значений принимающая языки.
Подчеркнем тот факт, что по крайней мере здесь, когда мы рассматриваем в качестве значения «языковой» переменной ? язык L, сам L рассматривается сугубо с теоретико-множественной точки зрения; в частности, цепочки языка L не снабжены никакими характеристиками (т. е. им не приписаны синтаксические структуры). Гл. XI. Задание языков с помощью систем уравнений
177
Пример. Рассмотрим в качестве области определения переменной класс линейных языков в алфавите {а, Ь, с}. Тогда выражение
ЬЖЬЦЖаШ
задает функцию, которая имеет эту область определения и значениями которой являются языки.
Уравнения. Для обозначения только что введенных функций мы будем использовать классические обозначения, а именно
0 = /(8, ®t, ...).
Если считать значения некоторых из переменных Й,2Я, ... известными, а других — неизвестными, мы получим уравнения, в которых неизвестные являются языками; возникает вопрос о методах решения таких уравнений.
Обратно, если дан некоторый язык, можно пытаться построить интересные уравнения, для которых данный язык будет решением.
Сначала мы изучим эти новые понятия на примере одного частного случая.
11.1.3. Уравнение, связанное с «зеркальным языком» Lm
Пусть имеется язык Lm в алфавите {а,Ь,с}, порождаемый следующей грамматикой:
S-+aSa S-+bSb . S —ус
Рассмотрим функцию, заданную выражением айа.
Если значением переменной й является Lm, то эта функция принимает значение Lm = aLma; язык Lm есть подъязык языка Lm, а именно — он содержит все те и только те цепочки языка Lm, которые начинаются и оканчиваются символом а.
Рассмотрим, далее, выражение a%a\J bQb. При й — Lm задаваемая им функция принимает в качестве значения язык, получаемый из Lm выбрасыванием цепочки с. Итак, Lm = aLma U bLmb U с.
Значит, язык Lm является одним из решений уравнения
2 = aia\Jb2b\Jc. (*)
11.1.4. Решение полученного уравнения
Можно задать вопрос, является ли язык Lm (в алфавите {о, Ь, с}) единственным решением только что выписанного уравнения. Запишем это уравнение в виде
2 = /(8)
и попытаемся решить его. 178
Часть II. Некоторые замечательные классы языков
Поскольку значение третьего члена правой части уравнения (*) известно, очевидно, что всякое решение L должно содержать одно-буквенную цепочку с, т. е. содержать язык L1 = {с}. Поэтому всякое решение обязательно содержит также и язык
