Обсуждение:Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

Содержание

Алгоритм похож на правильный, но понять его очень сложно, текст не особо связный. Хочется пример для наглядности. И очень хочется список литературы.

Алгоритм сам по себе сложный. Текст попробую еще поменять, но из псевдокода и так все понятно. Могу добавить пример как с помощью сплиттера происходит деление блока. Список литературы добавлен.

Вот пример автомата количество состояний - 2, терминальных - 1 (вершина №0), мощность алфавита - 1. переходы: 0 [math]\to[/math] 0 1 [math]\to[/math] 1 Этот автомат ведь эквивалентен автомату только с вершиной 0, а алгоритм этого не скажет.

Алгоритм не правильный. Он даёт верный результат, но работает за [math]O(|\Sigma| * n ^ 2)[/math]. Кстати предложенный пример (0 [math]\to[/math] 0, 1 [math]\to[/math] 1) он отработает правильно, нужно только представлять автомат как автомат с "дьявольской вершиной". По второму источнику ("D. Gries. Describing an algorithm by Hopcroft.") можно составить представление как алгоритм за [math]O(|\Sigma| * n \log {n})[/math] должен работать. --Dmitriy D. 01:53, 29 октября 2012 (GST)

Оформление

Больше всего претензий. Понимания не только не добавляет, но и отнимает остатки. Пунктуация — аут полный, запятых практически нет. Ну ладно, это работа для гнома. Слово "сплиттер" пишется так, как его пишу я, а не как его пишешь ты. Разность множеств обозначается не тире, а backslash'ем. Зато вместо минусов надо ставить нормальное тире (пока Кирилл не видит, это его любимая мозоль). Там еще пара орфографических ошибок есть, но пока забьем.

Исправил "сплиттер", минусы и разность множеств. С письменным русским языком большие проблемы, так что надеюсь на гнома)

Влад, имхо, это стоит расписать подлиннее и поподробнее. Алёна.