Длины слов в автоматных языках

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

Пусть ,

и . Множество

называется заключительно периодическим (ultimately periodic) с периодом m, если выполнено условие

Лемма 4.3.2.

Пусть . Тогда равносильны следующие утверждения:

1. множество

   является заключительно периодическим;

2. найдутся такие положительное целое число m и конечные множества

   и , что

3. множество

   является объединением конечного семейства арифметических прогрессий.

Теорема 4.3.3.

Язык L над однобуквенным алфавитом {a} является автоматным тогда и только тогда, когда множество

является заключительно периодическим.

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

Теорема 4.3.4.

Если язык L является автоматным, то множество

является заключительно периодическим.

Доказательство. Рассмотрим конечный автомат, распознающий язык L. Заменим все символы в метках переходов на символ a. Осталось применить теорему 4.3.3 к полученному автоматному языку над однобуквенным алфавитом {a}.

Упражнение 4.3.5.

Существует ли такой автоматный язык L над алфавитом {a}, что язык

не является автоматным?

Упражнение 4.3.6.

Существует ли такой автоматный язык L над алфавитом {a}, что язык

не является автоматным?

Упражнение 4.3.7.

Существует ли такой автоматный язык L1

над алфавитом , что язык

не является автоматным?

Упражнение 4.3.8.

Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?

Упражнение 4.3.9.

Существует ли такой автоматный язык L над алфавитом {a,b}, что язык

не является автоматным?

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

---

---