Теорема 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. языки L1 и L2 содержат только однобуквенные слова;
2. язык L3 содержит только двухбуквенные слова;
3. .
Лемма 4.2.4. Каждый локальный язык является автоматным.
Очевидно, что языки L1, L2 и L3 в определении 4.2.3 являются конечными. Остается применить замечание 2.1.19 и теоремы 3.1.1 и 3.2.1 (напомним, что разность языков выражается через пересечение и дополнение).
|
|
Теорема 4.2.5. Пусть L - язык над алфавитом и L не содержит пустого слова. Язык L является автоматным тогда и только тогда, когда существуют такие алфавит , локальный язык и побуквенный гомоморфизм , что L = h(L0).
Доказательство. Достаточность следует из леммы 4.2.4 и теоремы 4.1.1.
Для доказательства необходимости рассмотрим конечный автомат с однобуквенными переходами, задающий язык L. В качестве алфавита возьмем множество . Положим
и для каждого .
Пример 4.2.6. Пусть . Рассмотрим конечный автомат M2 из примера 3.1.3 и обозначим L = L(M2). Применим конструкцию из доказательства теоремы 4.2.5 к языку L. Для удобства заменим на d, на e и на f. Получим алфавит и локальный язык
Можно доказать, что
Побуквенный гомоморфизм h задается равенствами , и . Легко проверить, что действительно L = h(L0).