096. Функция разметки состояний и базисные слова для конечных автоматов

Представление конечных автоматов в виде базисных слов с использованием функции разметки и базисного автомата [2] позволяет в ряде случаев оценивать сложность языка, представить его произведения как количество состояний базисного автомата при процедуре детерминизации. Конечные автоматы, как детерминированные так и недетерминированные, нашли широкое применение в информатике, компьютерных науках.

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