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

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

Обратимся снова к свойствам замкнутости класса автоматных языков. Как мы уже установили с помощью конструкции произведения автоматов, этот класс замкнут относительно объединения, пересечения и разности (см. следствие 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 .

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

---