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

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

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

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

? (1

n), то

(w) =

(w1)

(w2) …

(wn).

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

определен на символах ? следующим образом:

(a) =00,

(b) =?,

Тогда

(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) вляется автоматным.

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