Набор тестов минимизации DFA?

Question

Я ищу тестовый набор детерминированных конечных автоматов, который будет использоваться для проверки правильности алгоритмов минимизации DFA.Не могли бы вы дать мне несколько советов?Или есть алгоритмы / реализации, которые будут генерировать такие автоматы?

Чтобы выиграть награду, вам необходимо предоставить тестовый набор из 400 или более неминимальных автоматов различных размеров и сложности, по крайней мере 20, содержащих более 2000 узлов.это не то место, где можно задать этот вопрос, пожалуйста, направьте меня в несколько лучших мест.Благодарю.

Answer 1

Чтобы проверить правильность, вы можете попробовать преобразовать ваши минимальные DFA в формат OpenFst и проверить эквивалентность свернутых акцепторов, используя операцию эквивалентность .

Answer 2

Проверка "всех" DFA до n состояний и m символов алфавита невозможна.Вы можете протестировать DFA с известными минимальными DFA;чтобы получить пары (DFA, минимальный DFA), вы можете сгенерировать случайные RE, получить NFA-лямбду, используя алгоритм из теоремы Клини, получить DFA с использованием конструкции подмножества, а затем свернуть с помощью известного правильного алгоритма минимизации DFA (я полагаю, выпризнайте, что канонический алгоритм корректен).

РЕДАКТИРОВАТЬ:

Чтобы расширить то, что я сказал, вот как я бы попытался сгенерировать набор тестов неминимальных конечных автоматов:

1. Создание регулярного выражения с использованием N операций (конкатенация, объединение, замыкание Клини).
2. Используйте алгоритм из теоремы Клини, чтобы получить NFA-лямбду с O (n) -состоянием в ней.
3. Используйте конструкцию подмножества / powerset, чтобы получить DFA с O (2 ^ n) состояниями в нем.
4. Повторяйте, пока не найдете достаточное количество достаточно сложных автоматов.

Создать регулярные выражения проще.Существует несколько правил:

1. a является RE, если a является символом алфавита
2. (rs) является RE, если r, s являются RE
3. (r + s) является RE, если r, s является RE
4. (r *) является RE, если r является RE
5. Ничто другое не является RE

Чтобы получить RE с n операциями, рекурсивный подход работает.

GetRE(ops)
 1. if ops = 0 then return RandomAlphabetSymbol()
 2. select(Rand() % 3)
 3. case 0 then
 4.  ops1 = Rand() % (ops - 1)
 5.  ops2 = (ops - 1) - ops1
 6.  return "(" + GetRE(ops1) + "+" + GetRE(ops2) + ")"
 7. case 1 then
 8.  ops1 = Rand() % (ops - 1)
 9.  ops2 = (ops - 1) - ops1
10.  return "(" + GetRE(ops1) + "." + GetRE(ops2) + ")"
11. case 2 then
12.  return "(" + GetRE(ops - 1) + "*)"

Вы можете найти нестроковое представление (т. Е. Иерархически связанную структуру, по сути, само дерево разбора), более удобный вариантза применение алгоритма Клини для получения NFA-лямбды.