Структура данных для хранения узлов DFA

Мне нужна структура данных для хранения узлов конечного детерминированного автомата, чтобы найти узлы, которые удовлетворяют определенному условию, быстро (логарифмически).
Данное условие является следующим:

У меня есть узел pи я должен найти узел qтакой, что: (p ∈ F ≡ q ∈ F) & (∀ a : a ∈ Σ : δ(p,a) = δ(q,a)), То есть, p а также q либо оба являются окончательными, либо оба нет, и они имеют переходы к одним и тем же узлам.

Я не хочу проходить через все узлы, потому что это будет медленно. Очевидно, если набор букв алфавита, для которого q имеет переходы, отличается от множества, для которого p имеет переходы, q это не тот узел, который я ищу.

Кроме того, если p а также q иметь другое количество переходов, q опять не тот узел, который я хочу. Поэтому я думал о структуре данных, которая сортирует узлы в соответствии с их окончательностью и количеством переходов, поэтому мне не нужно просматривать все узлы, только те, которые имеют одинаковую конечность и одинаковое количество переходов. Но это все еще не логарифмический. Есть идеи.

Я использую с ++.

2

Решение

На узле есть два типа информации q:

  • Логическая информация (q ∈ F)
  • Список пар (a,n) такой, что δ (q, a) == n (то есть список пар символов / узлов-узлов, достижимых из q)

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

Это позволит хэшировать узлы по интересующему вас свойству. Поиск узлов-кандидатов q для данного узла p будет тогда около O (1).

(Для алгоритма минимизации, который вы упомянули в комментариях, это означает, что вам нужно будет перестраивать этот хэш после каждой итерации, потому что указатели узла назначения в парах будут меняться в результате действий, выполненных во время итерации.)

0

Другие решения

Я построил строку для каждого узла и поместил строки в дерево AVL. Он выполнялся быстрее, чем решение с хэш-функцией и неупорядоченной картой, и использовал гораздо меньше памяти.

Строка, представляющая узел, выглядит следующим образом: она начинается с 0 или же 1в зависимости от того, является ли узел конечным или нет, а затем пары (a,n) кодируются следующим образом: a является int в соответствии с положением символа a в алфавите и n Другой int, индекс узла, к которому он имеет переход с символом a,

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector