Аннотация:
Изучается сложность реализации автоматов посредством кодирований его состояний. Рассматриваются всевозможные равномерные кодирования, т.е. кодирования состояний наборами одинаковой длины. На длину кода не накладывается ограничение сверху. Получена верхняя оценка сложности реализации автомата. Получена верхняя оценка длины кода, при котором достигается линейная реализуемость автомата.
Ключевые слова:теория автоматов, переходные системы, подстановка, кодирование, сложность.
Полный текст:
PDF файл (326 kB)