Обратимся снова к свойствам замкнутости класса автоматных языков. Как мы уже установили с помощью конструкции произведения автоматов, этот класс замкнут относительно объединения, пересечения и разности (см. следствие 4.1.1). Из теоремы 5.1 непосредственно следует, что класс автоматных языков замкнут относительно операций конкатенации и итерации. Можно легко установить, что он также замкнут относительно дополнения.
Предложение 6.1. Пусть L - автоматный язык в алфавите ?. Тогда его дополнение - язык
Действительно, достаточно заметить, что язык ?*, включающий все слова в алфавите ? является автоматным и что
Определенная ниже операция гомоморфизма формализует идею посимвольного перевода слов одного алфавита в слова другого.
Определение 6.1. Пусть ? и Delta - два алфавита. Отображение
Из этого определения непосредственно следует, что гомоморфизм однозначно определяется своими значениями на символах алфавита ?. Если w=w1w2 … wn, wi
Пример 6.1.Пусть ? ={a, b, c}, Delta ={ 0, 1}, а гомоморфизм
Тогда
Определение 6.2.
Пусть
Пусть L - язык в алфавите ?. Прообразом этого языка при гомоморфизме
Оказывается, что класс автоматных языков замкнут относительно операций гомоморфизма и обращения гомоморфизма (взятия прообраза)
Теорема 6.1. Пусть