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

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

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


- (?) = ?;
- для любых двух слов w1 и w2 в алфавите ? имеет место равенство (w1w2) =(w1)(w2).
Из этого определения непосредственно следует, что гомоморфизм однозначно определяется своими значениями на символах алфавита ?. Если w=w1w2 … wn, wi







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




Тогда



Определение 6.2.
Пусть







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






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



Доказательство Пусть A=<?, Q, q0, F, ?> - ДКА, распознающий язык L. Построим по нему НКА M =<?, QM, q0M, FM, ?M>, распознающий язык



Пусть ? = {a1, … , am}, Q= {q0, q1, …, qn} и




















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

Для завершения определения M положим q0M = q0 и FM = F.
Докажем теперь, что наше построение корректно, т.е., что


(L)LM. Заметим вначале, что если ?L, то q0F и по определению q0FM, следовательно(?)=?LM.
Пусть w=w1w2… wkL, ws?. Тогда в диаграмме A имеется путь из q0 в некоторое заключительное состояние q'F, который несет слово w. Пусть это путь. Тогда для каждого 1xk в ? имеется команда. Но из определения ?M следует, что тогда в автомате M имеется путь изв, несущий слово(wx). Объединив все такие пути, получим путь из из q0 в q'FM, несущий слово(w). Следовательно,(w)LM.
LM(L). Пусть слово u?* принадлежит LM.
Покажем, что тогда для некоторого wL u =(w). Рассмотрим для этого путь в диаграмме M из q0 в q'FM, несущий слово u . Выделим на этом пути все состояния из Q. Пусть это будут по порядку состояния q0=q{j0}, q{j1}, … q{jk}= q'. Тогда слово u разбивается на k подслов: u=u1u2 … uk таких, что ux переводит в M состояниев
(1xk). Покажем, что для каждого такого 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 и, следовательно wL .