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



             

Дополнительные свойства автоматных языков


Эта лекция содержит дополнительные результаты, не используемые в дальнейшем изложении. В начале лекции доказывается замкнутость класса всех автоматных языков относительно взятия гомоморфного образа и относительно взятия полного гомоморфного прообраза.

В разделе 4.2* определяются понятия побуквенного гомоморфизма и локального языка и доказывается еще один критерий автоматности: среди языков, не содержащих пустого слова, автоматными являются в точности образы локальных языков при побуквенных гомоморфизмах.

В последнем разделе этой лекции устанавливается числовой критерий автоматности для языков над однобуквенным алфавитом (в терминах арифметических прогрессий) и доказывается связанное с длинами слов необходимое условие автоматности (для произвольного алфавита).




Содержание    Вперед