Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Бабин Д.Н., Ищенко Р.А.
О восстановлении диаграммы автомата по его графу
Аннотация:
Если в диаграмме переходов автомата убрать информацию о входных буквах, то получится ориентированный граф. C точностью до переименования букв входного алфавита мы решаем обратную задачу восстановления диаграммы автомата по орграфу. Как правило число решений оказывается большим, но иногда это можно сделать однозначно. Возникает задача найти алгоритм для проверки существования решения, а также оценить число решений в худшем случае в зависимости от типа переходов автомата.
