Какой хороший алгоритм для генерации случайных DFA?
https://cs.stackexchange.com/questions/12943
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я генерирую случайные DFA для проверки алгоритма снижения DFA.
Алгоритм, который я использую сейчас, заключается в следующем: для каждого состояния $ Q $, для каждого символа в алфавите $ C $ добавьте $ delta (Q, C) $ в какое -то случайное состояние. Каждое состояние имеет одинаковую вероятность стать окончательным состоянием.
Это хороший метод создания беспристрастных DFA? Кроме того, этот алгоритм не генерирует TRIM DFA (DFA без устаревших состояний), поэтому мне интересно, есть ли лучший способ генерирования случайных DFA, которые могут каким -то образом гарантировать, что он отделен?
Решение
Проверьте [1] и обсуждение в разделе 4, «Случайная генерация автоматов». Бумажные тесты различные алгоритмы минимизации DFA. Используется унифицированный случайный генератор, который создает канонические представления строкости полных DFA с государствами $ n $ и символами $ K $. Они также обсуждают другие методы.
Другие советы
Вы должны смотреть на Домашняя страница Кирила НикаАнкет В частности, следующие ссылки имеют отношение к вашему вопросу:
Ф. Бассино, Дж. Дэвид и С. Нико, перечисление и случайная генерация, возможно, неполные детерминированные автоматы, Чистая математика и приложения 19 (2-3) (2009) 1-16.
Ф. Бассино и С. Нико. Перечисление и случайная генерация доступных автоматов. Теор. Компонент В. 381 (2007) 86-104.
Существуют алгоритмы, чтобы случайным образом генерировать DFA до перестановки http://paranthoen.thomas.free.fr/papers/randdfatoappearintcs.ps.gz.
Но в приведенной выше статье также упоминается, что почти все DFA уже минимальны. Не минимальные DFA - это как основные цифры ... их лишь мало. И если вы используете этот алгоритм для проверки алгоритма минимизации, это будет похоже на то, что если вы тестируете алгоритм на первичном числе с помощью простого генератора случайных чисел. Чтобы иметь больше не минимальных DFA, вы можете изменить алгоритм, добавив состояние раковины и перенаправить важный процент переходов в это состояние раковины.
Но с моей точки зрения, если вы хотите проверить скорость вашей реализации, проверьте ее на то, что вы хотите использовать: с помощью случайных наборов слов или случайного режима, создайте NFA или DFA, а затем минимизируйте полученный DFA Анкет
Одной из природных стратегий состоит в том, чтобы рассматривать DFA как график, а затем есть много «естественных» и высоко изученных случайных распределений графиков, самое простое, вероятно, является, вероятно, Erdos-renyi. Анкет В этом случае вы рассматриваете все состояния DFA как узлы графика, и выбраны некоторые фиксированные проценты всех возможных ребра (переходы DFA). более сложные распределения, которые много изучаются в более позднюю эру маленький мир графики Для стратегии, которую вы упоминаете в своем вопросе, вы, очевидно, выбираете специальный случай $ p = 1/n $, где $ n $ - это количество узлов на графике. Однако ваша стратегия, а не Erdos-renyi, не гарантирует, что все штаты в DFA связаны [естественное ограничение для добавления].
