Введение в схемы, автоматы и алгоритмы



             

Замкнутость относительно гомоморфизмов и их обращений


Обратимся снова к свойствам замкнутости класса автоматных языков. Как мы уже установили с помощью конструкции произведения автоматов, этот класс замкнут относительно объединения, пересечения и разности (см. следствие 4.1.1). Из теоремы 5.1 непосредственно следует, что класс автоматных языков замкнут относительно операций конкатенации и итерации. Можно легко установить, что он также замкнут относительно дополнения.

Предложение 6.1. Пусть L - автоматный язык в алфавите ?. Тогда его дополнение - язык

\bar{L} =\{ w\ |\ w \in \Sigma^*\ \textit{ и }w \notin L\}
также является автоматным.

Действительно, достаточно заметить, что язык ?*, включающий все слова в алфавите ? является автоматным и что

\overline{L} = \Sigma^* \setminus L
.

Определенная ниже операция гомоморфизма формализует идею посимвольного перевода слов одного алфавита в слова другого.

Определение 6.1. Пусть ? и Delta - два алфавита. Отображение

: ?*
Delta* слов первого из них в слова второго называется гомоморфизмом, если

  1. (?) = ?;
  2. для любых двух слов w1 и w2 в алфавите ? имеет место равенство
    (w1w2) =
    (w1)
    (w2).

Из этого определения непосредственно следует, что гомоморфизм однозначно определяется своими значениями на символах алфавита ?. Если w=w1w2 … wn, wi

? (1
i
n), то
(w) =
(w1)
(w2) …
(wn).

Пример 6.1.Пусть ? ={a, b, c}, Delta ={ 0, 1}, а гомоморфизм

определен на символах ? следующим образом:
(a) =00,
(b) =?,
(c) =101.

Тогда

(aca) = 0010100,
(abcb) =00101,
(bbb) = ?.

Определение 6.2.

Пусть

: ?*
Delta* - произвольный гомоморфизм и L - язык в алфавите ?. Образом
(L) языка L при гомоморфизме
называется язык
(L)= {
(w) | w
L}, состоящий из образов всех слов языка L.

Пусть L - язык в алфавите ?. Прообразом этого языка при гомоморфизме

называется язык
-1(L)= { w
?* |
(w)
L}, состоящий из всех таких слов в алфавите ?, чьи образы при гомоморфизме
попадают в L.

Оказывается, что класс автоматных языков замкнут относительно операций гомоморфизма и обращения гомоморфизма (взятия прообраза)

Теорема 6.1. Пусть

: ?*
?* - произвольный гомоморфизм и L - автоматный язык в алфавите ?. Тогда и язык
(L) вляется автоматным.




Содержание    Вперед