Математическая теория формальных языков

         

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


Определение 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}, что язык

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



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