Минимизация NFA без determinization

Это известно, как каждый добирается от NFA для регулярного языка к минимальному DFA. Однако DFA мог бы иметь экспоненциально большее число состояний.

То, в чем я нуждаюсь, является способом уменьшить NFA, давая снова NFA, но с меньшим числом состояний. T.i. Мне не нужен результат, чтобы быть детерминированным, но я хотел бы, чтобы он был как можно меньше при сохранении распознанного языка (возможно, не абсолютно оптимальный, но чем меньший, тем лучше).

Каковы лучшие алгоритмы для этой проблемы? Или возможно не "лучшее", но по крайней мере "самое легкое для реализации с неплачевной эффективностью"? Или проблема имеет известное имя так, чтобы я мог найти хорошие источники информации сам?

12
задан jkff 31 July 2010 в 17:11
поделиться

1 ответ

Я считаю, что проблема также известна как минимизация NFA. Я считаю, что в целом это NP-сложно.

Одним из плодотворных подходов может быть минимизация бисимуляции [Paige, Tarjan 1987] и последующие производные.

В этой презентации есть некоторые заметки о разрешимости проблемы, а также ссылки на некоторые подходы с разъяснением их относительных достоинств.

9
ответ дан 2 December 2019 в 22:03
поделиться
Другие вопросы по тегам:

Похожие вопросы: