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

Определение 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).

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

Упражнение 4.2.8. Является ли локальным язык

над алфавитом ?

Упражнение 4.2.9. Является ли локальным язык

над алфавитом ?

Упражнение 4.2.10. Является ли локальным язык

над алфавитом ?

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

---

---