Есть простая и специфичная виртуалная машина (Для проверки регекспов). Она умеет только простые операции, безусловный переход и операцию деления процесса. И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода. Если один из процессов достигает любой точки выхода то все процессы заверщаются. Заранее известно что код может быть не оптимальным. Задача этот код оптимизировать. Очевидно что если некоторые команды никогда не выполняются их можно удалить. Но естъ ещё бесконечные циклы. Так-как они не видут к результату их тоже нужно оптимизировать.
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить.
Вот собственно ищю идею быстрого алгоритма.

kealon(Ruslan),

Я не вижу как алгоритм минимизации ДКА применим к изложенной задаче. Задачи то совершенно разные.

Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить.
Вот собственно ищю идею быстрого алгоритма.

Вот моя задача. Всё остальное - так немного лирики.

Но нам ничто не мешает взять граф и сказать что одна из вершин точка старта или начала пути и также задать набор вершин - точек завершения или конечных точек пути. Такая постановка задачи корекектна.

К такому доктору я бы не обращался. Это разные задачи.
Давайте на простом примере покажу.
Пусть граф задан таким образом:




Какой результат нам даст Алгоритм Бржозовско?

kealon(Ruslan),

Я рад что вы знаете методы оптимизации ДКА но я повторяю - это не моя задача.
во первых не это не ДКА, во вторых мне ненужно уменьшать количество состояний.

Рёбра - это действия виртуальной машины. Состояния - не материальны. Просто число.

В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения.

kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.

Для вас третий раз повторю:
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения.

Если вам что-то непонятно задавайте вопрос.
Подозреваю студент до вопроса не созрел но про вшей билет выучил.