Аннотация:
Если в диаграмме Мура автомата без выходов убрать информацию о входных буквах, то получится ориентированный граф. Обратная операция, когда эта информация восстанавливается, называется разметкой графа автомата. В этой статье приводятся оценки числа разметок графов, приводящих к групповым автоматам.
Ключевые слова:групповой автомат, граф переходов, диаграмма Мура, перманент матрицы, факторизация.
Полный текст:
PDF файл (499 kB)