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

Теорема 4.1.1. Для любого гомоморфизма и автоматного языка язык h(L) является автоматным.

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

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

Теорема 4.1.2. Для любого гомоморфизма и автоматного языка язык h^-1(L) является автоматным.

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

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

4.2*. Локальные языки

Определение 4.2.1. Гомоморфизм называется побуквенным (length-preserving), если |h(a)| = 1 для каждого .

Замечание 4.2.2. Гомоморфизм является побуквенным тогда и только тогда, когда |h(w)| = |w| для каждого слова .

Определение 4.2.3. Язык называется локальным, если существуют такие языки , , , что

1. языки L₁ и L₂ содержат только однобуквенные слова;

2. язык L₃ содержит только двухбуквенные слова;

3. .

Лемма 4.2.4. Каждый локальный язык является автоматным.

Очевидно, что языки L₁, L₂ и L₃ в определении 4.2.3 являются конечными. Остается применить замечание 2.1.19 и теоремы 3.1.1 и 3.2.1 (напомним, что разность языков выражается через пересечение и дополнение).

Теорема 4.2.5. Пусть L - язык над алфавитом и L не содержит пустого слова. Язык L является автоматным тогда и только тогда, когда существуют такие алфавит , локальный язык и побуквенный гомоморфизм , что L = h(L₀).

Доказательство. Достаточность следует из леммы 4.2.4 и теоремы 4.1.1.

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

и для каждого .

Пример 4.2.6. Пусть . Рассмотрим конечный автомат M₂ из примера 3.1.3 и обозначим L = L(M₂). Применим конструкцию из доказательства теоремы 4.2.5 к языку L. Для удобства заменим на d, на e и на f. Получим алфавит и локальный язык