Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Пусть X = {хі I 1 < і < m} — входной алфавит, Y = {у j \
— выходной алфавит и 2 = {Sh | I^ k р} — множество состояний. Пусть, далее, отображение (tr): 2 х X (tr) > 2 задает функцию переходов: паре (S, х) ставится в соответствие некоторое состояние, обозначаемое Sx. Наконец, пусть имеется отображение ті, сопоставляющее паре (S, х) цепочку ті (S, х) <= Y-.
2 X X-2+Y.
Под левым односторонним преобразованием, исходящим из состояния Sk, мы будем понимать отображение А'* в Y*, которое строится следующим образом. Пусть /еР — данная цепочка;
f = X{t ...Xiv
Первой букве Xil этой цепочки мы поставим в соответствие букву Tl (S^1, Xil) И состояние Sk2 = SklXll.
Второй букве Xi1 поставим в соответствие букву г] (-Sft2, хІ2) и состояние Skt = SkJCi1 и т. д. Гл. XIV. Дополнительные сведения об автоматных языках
227
Ясно, что таким образом всякой цепочке f є X* сопоставляется некоторая цепочка из Y*.
Для упрощения записи мы будем обозначать начальное состояние через 5 (без индекса), а образ цепочки f — через r\(S,f). Выражение t)(S, f) есть по определению образ цепочки / при преобразовании [X, Y, 2, (tr),T)], исходящем из состояния 5.
Пусть Гс:^*. Будем обозначать через t)(S, Г) множество (t)(SJ) I fe=n (образ языка Г).
Пусть, наконец, Ac Y* — язык в выходном алфавите; возможно, существуют такие цепочки из X*, что их образы принадлежат А.
Положим
t)-j(S, А) = {/еХ* I t)(S, /)є=Д}.
№: не требуется, чтобы все цепочки А были образами цепочек из X*!
14.4.2. Образ языка X *
Рассмотрим сначала язык t)(S, X*) — образ всего языка X*.
Всякой цепочке f є X* соответствует ее образ т) (S, f) и состояние Sf, в котором заканчивается ее преобразование.
Пусть g є Y*. Если ger](5, I*), то существуют цепочки f4.....fi, . . ¦ ^X*, для каждой из которых g является образом. Сопоставим цепочке g множество Og, состоящее из всех тех состояний Sfi, ..., Sf., ..., в которых автомат может писать последнюю букву цепочки g Если g^T)(S, X*), положим ag = 0. Будем писать g ~ g', если og = Og'.
1°. Отношение ~ есть отношение эквивалентности.
2°. t)(S, X*) представляет собой объединение классов по таких, что ag ф 0.
3°. Поскольку индекс отношения ~ не больше мощности множества всех подмножеств 2, он конечен.
4°. Отношение ~ совместимо вправо с конкатенацией.
В самом деле, предположим, что g ~ g', и сравним gh с g'h. Если g может быть получено из некоторого f так, что преобразование окончится в состоянии Sa, и если h может быть получено из некоторого и посредством преобразования, начинающегося в состоянии Sa, то существует такое f', что из f'u можно получить g'h. причем преобразование окончится в том же состоянии, что и при получении gh из fu.
В силу утверждений Г, 2° и 4° отношение эквивалентности по допустимым концам для t)(S, X*) является не более тонким, чем отношение ~ (по теореме п. 13 2.4). Отсюда и из 3° в силу теоремы п 14 3.3 следует, что множество г] (S, X*) является А-языком.
Итак, мы видем, что t)(S, Ar*) обладает некоторой структурой. Однако подмножество множества ц (S, X*) может и не иметь точного прообраза в X*, если оно не обладает естественной структурой. 228
Часть III. Алгебраический подход
14.4.3. Образ произвольного А-языка
Если язык X*— автоматный, то его образ также является А-языком.
Пусть Г с Л'* есть А-язык. Мы знаем, что отношение эквивалентности по допустимым концам относительно Г индуцирует разбиение множества X* на конечное число классов, причем язык Г оказывается объединением некоторых из них.
Пусть / є Г. Цепочка f принадлежит некоторому классу ее преобразование оканчивается в состоянии Sf. Пусть, далее, g є У*. Если ger)(S, Л'*), то множество {/ь ...,ft} ее прообразов не пусто; сопоставим в этом случае цепочке g множество пар {(Yf,< Sfі) І г'=1.....t}- Если поставим в соответст-
вие цепочке g пустое множество.
Если множество пар, сопоставленное указанным образом цепочке g, совпадает с множеством пар, сопоставленным таким же образом цепочке g', мы будем писать g ~ rg'«
Г. Отношение ~ г является эквивалентностью.
2°. Множество г] (5, Г) представляет собой объединение классов, отвечающих таким множествам {(vf,> ^f1).....•$<)}» для которых хотя бы один класс у* содержится в Г.
3°. Индекс отношения ~г конечен.
4°. Отношение ~г совместимо с конкатенацией вправо.
Для доказательства утверждения 4° достаточно вспомнить то, что говорилось при доказательстве аналогичного утверждения в предыдущем пункте, и добавить, что класс эквивалентности (по допустимым концам) цепочки fu совпадает с классом цепочки f'u, если только это верно для f и }'.
Из 1°—4° следует, что г](5, Г) есть А-язык. Нетрудно видеть, что классы эквивалентности, определяемые этим языком, содержатся в естественных классах эквивалентности, определяемых языком т](5, X*) (см. предыдущий пункт). Таким образом, если некоторый А-язык Ac F' определяет классы, не содержащиеся в «естественных» классах, то Д не может быть образом никакого А-языка Г czX*.
14.4.4. Прообраз А-языка
