Что такое хороший алгоритм для генерации случайных DFA?

9

Я генерирую случайные DFA для проверки алгоритма сокращения DFA на них.

Алгоритм, который я сейчас использую, таков: для каждого состояния , для каждого символа в алфавите добавьте к некоторому случайному состоянию. Каждое состояние имеет одинаковую вероятность стать конечным состоянием. $q$ $c$ $\delta (q, c)$

Это хороший метод создания объективных DFA? Кроме того, этот алгоритм не генерирует обрезанный DFA (DFA без устаревших состояний), поэтому мне интересно, есть ли лучший способ генерации случайных DFA, который каким-то образом может гарантировать, что это обрезка?

algorithms finite-automata randomness pseudo-random-generators random-graphs Дункан
источник

2

Там нет естественного распределения случайных DFA, так что решать вам. Чего ты хочешь достичь?

Ювал Фильмус

Я генерирую случайные DFA для проверки алгоритма сокращения DFA на них.

Дункан

Возможно, вы хотите начать с небольшого набора минимальных DFA и взорвать их? Таким образом, вы знаете, что минимизация действительно приводит к правильному результату.

adrianN

Интересно, вы тестируете неоптимальный алгоритм сокращения или он находит уникальный минимальный оптимальный DFA?

vzn

2

Если вы генерируете структуры данных для тестирования, объективность не важна. Важно иметь хороший шанс вызвать интересное поведение. Чтобы провести аналогию, когда вы тестируете геометрический алгоритм, вы должны убедиться, что в некоторых ваших тестах будут выровнены три точки, а другие вещи никогда не встречаются при случайном распределении.

Жиль "ТАК - перестань быть злым"

6

Проверьте [1] и обсуждение в Разделе 4, Генерация случайных автоматов. В статье рассматриваются различные алгоритмы минимизации DFA. Используется равномерный генератор случайных чисел, который создает канонические строковые представления полных DFA с состояниями и символами. Они также обсуждают другие методы. $n$ $k$

[1] Алмейда М., Морейра Н. и Рейс Р. (2007). О производительности алгоритмов минимизации автоматов. Логика и теория алгоритмов, 3.

Юхо
источник

Что означает «канонические строковые представления»?

Дункан

Σ

$\Sigma$

4

Вы должны взглянуть на домашнюю страницу Сирила Ника . В частности, следующие вопросы имеют отношение к вашему вопросу:

F. Bassino, J. David и C. Nicaud, Перечисление и случайная генерация возможно неполных детерминированных автоматов, Чистая математика и приложения 19 (2-3) (2009) 1-16.

Ф. Бассино и С. Никао. Перечисление и случайная генерация доступных автоматов. Теор. Комп. Совет Безопасности ООН , 381 (2007) 86-104.

J.-E. Штырь
источник

3

Существуют алгоритмы для случайной генерации DFA с точностью до перестановки http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz .

Но в вышеупомянутой статье также упоминается, что почти все DFA уже минимальны. Неминимальные DFA - это простые числа ... их всего несколько. И если вы используете этот алгоритм для тестирования алгоритма минимизации, это будет похоже на тестирование алгоритма на простом числе с помощью простого генератора случайных чисел. Чтобы иметь больше неминимальных DFA, вы можете изменить алгоритм, добавив состояние приемника, и перенаправить значительный процент переходов в это состояние приемника.

Но, с моей точки зрения, если вы хотите проверить скорость своей реализации, сравните ее с тем, для чего вы хотите ее использовать: со случайными наборами слов или случайным REGEX, создайте NFA или DFA, а затем минимизируйте получающийся DFA ,

Томас
источник

2

$p=1/n$ $n$ это количество узлов в графе. однако ваша стратегия, как и Erdos-Renyi, не гарантирует, что все государства в DFA связаны между собой [естественное ограничение для добавления].

ВЗН
источник

1

К вашему сведению: cs.stackexchange.com/review/suggested-edits/6609

Жиль "

(v_{1}, b, v_{2})

$(v_1,b,v_2)$

v_{1}

$v_1$

v_{2}

$v_2$

b

$b$

Что такое хороший алгоритм для генерации случайных DFA?

Ответы: