Об $\omega$-языках специальных биллиардов

В статье рассматриваются недетерминированные инициальные конечные автоматы без финальных состояний и $\omega$-языки, определяемые такими автоматами. Для таких $\omega$-языков рассматриваются так называемые языки обструкций. Определяются и подробно рассматриваются биллиардные $\omega$-языки, задаваемые специальным образом для каждого $n\ge3$ над алфавитом из $n$ букв. Каждое $\omega$-слово такого $\omega$-языка может быть получено с помощью бесконечного числа правильных отражений точки от стенок биллиарда, имеющего форму правильного $n$-угольника. Для таких $\omega$-языков рассматриваются языки обструкций и показывается, что ни при каком $n$ такой язык обструкций не является регулярным.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 99–01–00907 и 00–15–99253.