Множества двусторонних контекстов

Определение 6.3.1.

Пусть

и . Тогда множество контекстов (множество двусторонних контекстов) слова y относительно языка L определяется следующим образом:

Пример 6.3.2.

Пусть

и . Тогда

Лемма 6.3.3.

Если , то .

Доказательство. Из определений следует, что

Лемма 6.3.4.

Если , то

и .

Доказательство. Пусть

и . Тогда . Следовательно, . Далее, получаем, что ,

и . Второе равенство доказывается аналогично.

Лемма 6.3.5.

Если

и , то .

Определение 6.3.6.

Пусть . Тогда множество

называется синтаксическим моноидом (syntactic monoid) языка L.

Определение 6.3.7*.

Полугруппой (semigroup)

называется непустое множество M с ассоциативной бинарной операцией .

Определение 6.3.8*.

Пусть - полугруппа. Элемент

называется единицей (unit), если

для каждого .

Определение 6.3.9*.

Моноид - это полугруппа

с единицей .

Теорема 6.3.10*.

Определим бинарную операцию на Synt(L) следующим образом:

Тогда

является моноидом.

Теорема 6.3.11.

Синтаксический моноид Synt(L) конечен тогда и только тогда, когда язык L является автоматным.

Доказательство Пусть множество Synt(L) конечно. Согласно лемме 6.3.3 множество

тоже конечно. В силу леммы 6.1.6 язык L является автоматным.

Обратно, пусть язык L распознается некоторым конечным автоматом , не содержащим переходов с метками длины больше единицы. Поставим в соответствие каждому слову y множество , определенное следующим образом:

Легко проверить, что если , то . Следовательно, , где n = |Q|.

Пример 6.3.12.

Рассмотрим конечный автомат M из примера 2.1.14. Тогда

1. ;
2. если , то ;
3. если , то ;
4. если , то ;
5. если , то ;
6. ;
7. .

Лемма 6.3.13.

Пусть ,

и для каждого слова

длины n найдется такое слово , что

и . Тогда

Доказательство. Индукцией по

можно доказать, что для каждого слова

длины k найдется такое слово , что

и . В шаге индукции используется лемма 6.3.5.

Упражнение 6.3.14. Сколько элементов в синтаксическом моноиде языка a+b над алфавитом {a,b}?

Упражнение 6.3.15. Сколько элементов в синтаксическом моноиде языка b+a+ над алфавитом {a,b}?

Упражнение 6.3.16. Сколько элементов в синтаксическом моноиде языка (aa+b)* над алфавитом {a,b}?

Упражнение 6.3.17. Сколько элементов в синтаксическом моноиде языка (ab)*(ba)*+a* над алфавитом {a,b}?

Упражнение 6.3.18. Сколько элементов в синтаксическом моноиде языка a(b+c)*a(a+b+c)*+b(a+c)*b(a+b+c)*+c(a+b)*c(a+b+c)* над алфавитом {a,b,c}?

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

---

---