Математическая теория формальных языков

         

Гомоморфизмы


Определение 1.3.1. Пусть и - алфавиты. Если отображение

удовлетворяет условию

для всех слов

и , то отображение h называется гомоморфизмом

(морфизмом).

Замечание 1.3.2.

Можно доказать, что если - гомоморфизм, то .

Замечание 1.3.3. Пусть

и . Тогда отображение , заданное равенством , является гомоморфизмом.

Замечание 1.3.4.

Каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

Замечание 1.3.5. Если - гомоморфизм и , то через h(L) обозначается язык .

Пример 1.3.6. Пусть

и гомоморфизм

задан равенствами h(a) = abba и . Тогда

Определение 1.3.7. Если - гомоморфизм и , то через h-1(L) обозначается язык .

Пример 1.3.8. Рассмотрим алфавит . Пусть гомоморфизм

задан равенствами h(a) = ab и h(b) = abb. Тогда

Упражнение 1.3.9. Пусть . Существует ли такой гомоморфизм , что h(abc) = bac и h(da) = ba?

Упражнение 1.3.10. Существуют ли такой язык

и такой гомоморфизм , что

и ?

Упражнение 1.3.11. Пусть . Существует ли такой гомоморфизм , что

и ?

Упражнение 1.3.12. Существуют ли такой язык

и такой гомоморфизм , что

и ?

Упражнение 1.3.13. Пусть - гомоморфизм, заданный соотношениями h(a) = a, h(b) = ba, h(c) = bb. Существуют ли такие слова u и v, что |u|<|v| и |h(u)|>|h(v)|?



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