Гомоморфизмы и автоматные языки

Теорема 4.1.1.

Для любого гомоморфизма

и автоматного языка

язык h(L) является автоматным.

Доказательство. Пусть исходный язык L задан конечным автоматом . Положим

Тогда язык h(L) распознается конечным автоматом .

Теорема 4.1.2. Для любого гомоморфизма

и автоматного языка

язык h-1(L) является автоматным.

Доказательство. Без ограничения общности можно предположить, что исходный язык L задан конечным автоматом , где

не содержит переходов с метками длины больше единицы. Положим

Язык h-1(L) распознается конечным автоматом .

Упражнение 4.1.3. Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?}

Упражнение 4.1.4. Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?}

Упражнение 4.1.5. Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?