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

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


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

Предложение 6.1. Пусть 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) вляется автоматным.


Доказательство Пусть A=<?, Q, q0, F, ?> - ДКА, распознающий язык L. Построим по нему НКА M =<?, QM, q0M, FM, ?M>, распознающий язык
(L). Идея этого построения проста: нужно каждый переход из состояния q в q' по букве a
? в автомате A превратить в переход из q в q' по слову
(a) в автомате M.

Пусть ? = {a1, … , am}, Q= {q0, q1, …, qn} и
(ai)= d1id2i … d{ki}i, dli
? (1
l
ki) (если
(ai)
?). Для каждого ai зафиксируем простой НКА Mi, распознающий язык {d1id2i … d{ki}i}, имеющий (ki +1) состояние p0i, p1i, …, p{ki}i и команды p{l-1}dli
pl (1
l
ki). ( Если
(ai) = ?, то у Mi будут два состояния, соединенные ?-переходом). Теперь для каждой команды qj ai
qr поместим в M между qj и qr автомат Mi (цепочку состояний p0i, p1i, …, p{ki}i). Чтобы состояния различных цепочек не склеивались, придадим им верхний индекс j, т.е. у каждого qj будет своя копия каждого из автоматов Mi. Для этого положим QM = Q
{ plji | 0
j
n, 1
i
m, 0
l
ki }. Таким образом, pl{ji} - это l-ое состояние на пути из qj по "старой" букве ai. Программа ?M автомата M строится по программе A следующим образом. Для каждой команды вида qj ai
qr из ? поместим в ?M следующие команды:



Таким образом, из qj автомат M по пустому переходу попадает в начальное состояние p0ji j-ой копии автомата Mi, затем проходит по слову
(ai) и снова по пустому переходу попадает в qr.

Для завершения определения M положим q0M = q0 и FM = F.

Докажем теперь, что наше построение корректно, т.е., что
(L)=
( LA) = LM .



  1. (L)
    LM. Заметим вначале, что если ?
    L, то q0
    F и по определению q0
    FM, следовательно
    (?)=?
    LM.

    Пусть w=w1w2… wk
    L, ws
    ?. Тогда в диаграмме A имеется путь из q0 в некоторое заключительное состояние q'
    F, который несет слово w. Пусть это путь
    . Тогда для каждого 1
    x
    k в ? имеется команда
    . Но из определения ?M следует, что тогда в автомате M имеется путь из
    в
    , несущий слово
    (wx). Объединив все такие пути, получим путь из из q0 в q'
    FM, несущий слово
    (w). Следовательно,
    (w)
    LM.



  2. LM
    (L). Пусть слово u
    ?* принадлежит LM.


    Покажем, что тогда для некоторого w
    L u =
    (w). Рассмотрим для этого путь в диаграмме M из q0 в q'
    FM, несущий слово u . Выделим на этом пути все состояния из Q. Пусть это будут по порядку состояния q0=q{j0}, q{j1}, … q{jk}= q'. Тогда слово u разбивается на k подслов: u=u1u2 … uk таких, что ux переводит в M состояние
    в


    (1
    x
    k). Покажем, что для каждого такого ux существует символ wx
    ? такой, что ux =
    (wx) и в ? имеется команда
    . Действительно, любой путь из
    в M начинается ?-переходом в некоторое состояние вида
    . Пусть это будет состояние на пути, который несет ux в
    . Далее этот путь обязательно будет проходить по состояниям вида
    и завершится ?-переходом из
    в состояние
    . Тогда из определения M следует, что ux =
    (ai) и в ? имеется команда
    . Положив wx=ai, получим, что ux =
    (wx) и u=
    (w1)
    (w2) …
    (wk) =
    (w), для слова w=w1w2 … wk
    ?*. При этом каждый символ wx этого слова переводит в автомате A состояние
    в
    . Поэтому в A существует путь из q0 в q'
    F, несущий слово w и, следовательно w
    L .



Содержание раздела