Каков алгоритм генерации случайных детерминированных конечных автоматов?

Question

DFA должен иметь следующие четыре свойства:

• DFA имеет N узлов

• Каждый узел имеет 2 исходящих перехода.

• Каждый узел доступен из любого другого узла.

• DFA выбирается с абсолютно равномерной случайностью из всех возможностей

Это то, что у меня пока есть:

1. Начните с набора из N узлов.
2. Выберите узел, который еще не был выбран.
3. Подключите свой выход к 2 другим случайно выбранным узлам
4. Пометьте один переход 1 и другой переход 0.
5. Перейдите к 2, если не были выбраны все узлы.
6. Определитьесли есть узел без входящих соединений.
7. Если это так, украдите входящее соединение от узла с более чем одним входящим соединением.
8. Перейдите к 6, если нет узлов безвходящие соединения

Однако этот алгоритм неверен.Рассмотрим график, где узел 1 имеет два своих соединения, идущие к узлу 2 (и наоборот), в то время как узел 3 имеет два своих соединения, идущие к узлу 4 (и наоборот).Это что-то вроде:

1 <==> 2

3 <==> 4

Где под <==> я подразумеваю два исходящих соединения в обоих направлениях (итого 4 соединения).Кажется, это формирует 2 клика, что означает, что не каждое состояние достижимо из любого другого состояния.

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

Answer 1

Сильная связь - трудное ограничение. Давайте сгенерируем равномерные случайные сюръективные переходные функции, а затем протестируем их, например, с помощью Алгоритм Тарьяна с линейным временем SCC, пока мы не получим тот, который сильно связан. Этот процесс имеет правильное распределение, но не ясно, насколько он эффективен; Интуиция моего исследователя заключается в том, что предельная вероятность сильной связности меньше 1, но больше 0, что означает, что в ожидании необходимы только O (1) итерации.

Генерация сюръективных функций перехода сама по себе нетривиальна. К сожалению, без этого ограничения экспоненциально маловероятно, что каждое состояние имеет входящий переход. Используйте алгоритм, описанный в ответах на на этот вопрос , чтобы выбрать равномерное случайное разбиение {(1, a), (1, b), (2, a), (2, b),…, (N, a), (N, b)} с N частями. Перестановка узлов случайным образом и назначение их частям.

Например, пусть N = 3 и предположим, что случайное разбиение равно

{{(1, a), (2, a), (3, b)}, {(2, b)}, {(1, b), (3, a)}}.

Выбираем случайную перестановку 2, 3, 1 и выводим функцию перехода

(1, a) |-> 2
(1, b) |-> 1
(2, a) |-> 2
(2, b) |-> 3
(3, a) |-> 1
(3, b) |-> 2

Answer 2

Существует алгоритм ожидаемого времени выполнения O (n ^ {3/2}).

Если вы генерируете случайный орграф с равными m вершинами, так что каждая вершина имеет k, обозначенных как дуги (a k-out орграф), то с большой вероятностью самый большой SCC (сильно связанный компонент) в этом орграфе имеет размер около c_k m, где c_k - константа, зависящая от k.На самом деле, существует вероятность 1 / \ sqrt {m}, что размер этого SCC точно равен c_k m (округляется до целого числа).

Таким образом, вы можете сгенерировать равномерный случайный орграф с двумя выходами размером n / c_k и проверить размер наибольшего SCC.Если его размер не совсем n, попробуйте еще раз до успеха.Ожидаемое количество необходимых испытаний: \ sqrt {n}.И генерация каждого орграфа должна быть выполнена за O (n) время.Таким образом, в общей сложности алгоритм ожидал времени выполнения O (n ^ {3/2}).См. этот документ для получения более подробной информации.

Answer 3

В дальнейшем я буду использовать базовую терминологию теории графов .

Вы могли бы:

1. Начните с ориентированного графа с N вершинами и без дуг.
2. Создайте случайную перестановку из N вершин, чтобы получить случайный гамильтонов цикл, и добавьте его в граф.
3. Для каждой вершины добавьте одну исходящую дугу к случайно выбранной вершине.

Результат удовлетворит все три требования.

Answer 4

Следующие ссылки, по-видимому, актуальны для вашего вопроса:

F. Бассино, Дж. Дэвид и К. Ника, Перечисление и случайная генерация возможно неполных детерминированных автоматов, Чистая математика и приложения 19 (2-3) (2009) 1-16.

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

Answer 5

Мы можем начать со случайного числа состояний N1 между N и 2N.

Предположим, что начальное состояние является номером состояния 1. Для каждого состояния для каждого символа во входном алфавите мы генерируем случайное число.переход (между 1 и N1).

Мы берем автомат Connex, начиная с исходного состояния.Мы проверяем количество состояний, и после нескольких попыток получаем одно с N состояниями.

Если мы тоже хотим минимальный автомат, остается только присваивание конечных состояний, однако есть большие шансы, что случайное присваивание также получит минимальный автомат.

Answer 6

Самый простой способ, который я могу придумать, - это (равномерно) сгенерировать случайный DFA с N узлами и двумя исходящими ребрами на узел, игнорируя другие ограничения, а затем отбросить любые, которые не сильно связаны (что являетсялегко проверить с помощью алгоритма сильно связанных компонентов).Создание однородных DFA должно быть простым без ограничения достижимости.Единственное, что может вызвать проблемы с производительностью, это то, сколько DFA нужно будет пропустить, прежде чем вы найдете один со свойством достижимости.Вы должны сначала попробовать этот алгоритм и посмотреть, сколько времени у него уйдет на создание приемлемого DFA.

Answer 7

Просто продолжайте наращивать набор узлов, которые все достижимы. Как только они все достижимы, заполните пробелы.

Start with a set of N nodes called A.
Choose a node from A and put it in set B.
While there are nodes left in set A
    Choose a node x from set A
    Choose a node y from set B with less than two outgoing transitions.
    Choose a node z from set B
    Add a transition from y to x.
    Add a transition from x to z
    Move x to set B
For each node n in B
    While n has less than two outgoing transitions
         Choose a node m in B
         Add a transition from n to m
Choose a node to be the start node.
Choose some number of nodes to be accepting nodes.

Каждый узел в наборе B может достигать каждого узла в наборе B. Пока узел может быть достигнут из узла в наборе B, и этот узел может достигнуть узла в наборе B, он может быть добавлен в набор.