Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Следствие. Для того чтобы язык L был А-языком, необходимо и достаточно, чтобы существовала конгруэнция конечного индекса, относительно которой L был бы объединением классов.
14.3.6. Формулировка в терминах гомоморфизмов
Произвольная конгруэнция JR на полугруппе M определяет фактормножество M/JR и естественное отображение каждого Л є M на его класс A єМ/ЗЇ. _
Пусть Au A2 є Л и Bu B2 є В. Тогда
Ai = А2=фAiB2 = A2B2 (совместимость вправо);
Bi = B2 =#> AiBi = AiB2 (совместимость влево). 224
Часть III. Алгебраический подход
Отсюда
[J1 = A2 & B1 = B2] =# Л^б, = Аф2.
На множестве классов эквивалентности можно определить one рацию, индуцируемую операцией, определенной на М: AB есть класс всех AiBi, таких, что Ai єі, В В. Эта новая операция ассоциативна и превращает М/9Ї в полугруппу.
Естественное отображение M на М/ЗЇ (обозначим его через ?) таково, что
Ф(Л5) = Ф(Л)Ф(5);
следовательно, ф есть гомоморфизм.
Вообще, пусть 0 — гомоморфизм, отображающий полугруппу M на полугруппу M'. По определению гомоморфизма
[ А --> А' & В В'\ =ф AB --> А'В'.
Пусть отношение Ш определено следующим образом: А]ША2 тогда и только тогда, когда Aj и A2 имеют при отображении 0 один и тот же образ. Очевидно, что 9Ї — эквивалентность; поскольку 0 — гомоморфизм, SR совместимо влево и вправо с операцией полугруппы M и, следовательно, является конгруэнцией.
Таким образом, между M/SR и W существует изоморфизм; классу элементов, имеющих в качестве образа А', отвечает при этом изоморфизме само А'.
Прообразы. Пусть P' — подмножество множества M'. Обозначим через 0-1(Р') множество тех элементов М, образы которых принадлежат P'. В частности, 0-1 (А') при А' е M' есть класс элементов, образом которых является А'. Обозначив этот класс через А, получим
0~'(в (Л)) = А.
Рассмотрим теперь подмножество P множества M и попытаемся найти необходимое и достаточное условие для того, чтобы 0-1 (0(Р)) = Р.
Обозначим через Ш конгруэнцию, определяемую по гомоморфизму 0 так же, как и выше. Тогда имеем достаточное условие: P должно быть объединением классов эквивалентности по SR. Это условие является и необходимым, так как для всякого А' є 0 (P) множество G"1 (в(P)) содержит все прообразы А'. Тем самым имеет место
Теорема. Если 0 — гомоморфное отображение полугруппы M на полугруппу M', то 0~'(0(Р)) = P тогда и только тогда, когда P является объединением некоторых классов эквивалентности по конгруэнции Ш, связанной с 0. Гл. XIV. Дополнительные сведения об автоматных языках
225
Применение к А-я з ы к а м. Для того чтобы язык L в алфавите 51 был автоматным, необходимо и достаточно, чтобы имело место следующее утверждение:
1) На свободной полугруппе 91* существует конгруэнция СЇ, которая имеет конечный индекс и относительно которой L является объединением классов.
Если (1) верно, то факторполугруппа 91*/СЇ, являющаяся образом полугруппы 91* при естественном гомоморфизме ф, связанном с конгруэнцией СЇ, конечна и, кроме того,
Ф-1 (Ф (L)) = L.
Вообще, пусть 0 — гомоморфизм свободной полугруппы 91* на конечную полугруппу М. Тогда конгруэнция СЇ, ассоциированная с 0, определяет факторполугруппу 91*/СЇ, изоморфную М:
21*--2-- M
Так как ф— изоморфизм, из равенства 0_1(0(L)) =L следует, что ф_1(ф(/.)) = ф, и наоборот. Поэтому утверждение (1) равносильно утверждению (2).
2) Существуют конечная полугруппа M и гомоморфизм 0 свободной полугруппы 91* на М, такой, что
0-1 (0 (L)) = L.
Все сказанное выше можно сформулировать в виде следующей теоремы:
Теорема. Для того чтобы язык L сг 91* был автоматным, необходимо и достаточно, чтобы существовал гомоморфизм 0 свободной полугруппы 91* на конечную полугруппу М, такой, что
0-1 (Q(L)) = L.
14.3.7. А-языки и графы
Пусть X — алфавит, и пусть А, В сг X, Va X2.
Множество АХ* П Х*В П VX*) является стандартным
А-языком.
Напомним, что это множество состоит из тех цепочек множества X*, которые 226
Часть III. Алгебраический подход
— либо являются однобуквенными и принадлежат А Л B-,
— либо начинаются буквой из А, оканчиваются буквой из В и не содержат диграмм, имеющихся в V.
Напомним формальное определение графа.
Графом называется пара (G, R), где
1) G — множество элементов, называемых вершинами-,
2) R — подмножество декартова произведения G X G; элементы R называются дугами.
Пусть H и К — подмножества множества G. Назовем путем из H в К. любую последовательность вершин, которая:
а) либо состоит из одной вершины, принадлежащей H Л К\
б) либо имеет вид хи ..., Xi, ..., хп, где Х\ е Н, Xn (В К и
(V*e={l.....п -!})[(*„ *і+1)є=/?].
Нетрудно видеть, что если отождествить G с X, то множеств путей из H в К совпадет со стандартным А-языком
НХ'[]Х*К\Х*УХ\ где V = X2\R.
§ 14.4. преобразования
14.4.1. Односторонние преобразования
Рассмотрим с некоторой новой точки зрения понятие одностороннего преобразователя (с которым мы встречались ранее в § 10.6) и попытаемся обобщить его; будем говорить при этом не о «преобразователях», а о «преобразованиях».
