Возвращение всех достижимых состояний в DFA, начиная с начального состояния

Question

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

states_reachable :: Eq st => DFA st -> [st] 
states_reachable (qs, sigma, delta, s, inF) = 
    [delta q a | q <- qs, a <- sigma] 

Примечание:

• QS это множество состояний
• сигма является алфавита
• дельта является функцией перехода, которая принимает состояние и символ и возвращает следующее состояние
• с начальным состояние
• Inf это функция, которая возвращает истину, если состояние является принимающим состоянием, иначе ложь

В качестве функции определяется в настоящее время:

[delta q a | q <- qs, a <- sigma] 

возвращается все состояния в DFA (что неверно).

Я хотел бы заполнить список, начав с начального состояния s и проверив функцию дельта с каждым входом.

Например:

// returns the states reachable from the initial state for all symbols in sigma 
[delta s a | a <- sigma] 

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

Тогда я попробовал:

[delta q a | q <- [delta s a | a <- sigma], a <- sigma] 

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

Мне нужно рекурсивно построить этот список, исследуя все новые состояния, возвращаемые функцией дельта.

Answer 1

Вы пытаетесь вычислить транзитивное замыкание отношения здесь, где отношение «x может перейти в y за один шаг». Таким образом, я бы предложил использовать общее решение для транзитивного закрытия, а не для DFA-специфического, а затем произвести это отношение из вашего DFA. Вот один довольно простой способ сделать это:

module Closure (closure) where             
import Data.List (nub) 

closure :: Eq a => (a -> [a]) -> a -> [a] 
closure nexts init = go [init] 
    where go xs = let xs' = nub $ xs ++ (xs >>= nexts)        
       in if xs == xs'             
        then xs              
        else go xs'             

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

Теперь, как нанести на карту проблему с DFA? Это не так сложно: вам просто нужно создать функцию nexts, используя sigma и delta.Здесь нам нужно предположить, что ваша функция DFA delta является общей, т. Е. Каждый узел имеет переход, указанный для каждой буквы в sigma. Это достаточно просто, создав один дополнительный узел «сбоя», который все узлы могут перейти, если им не нравится их вход, поэтому я просто предполагаю, что это было сделано.

neighbors :: (node -> letter -> node) -> [letter] -> node -> [node]    
neighbors delta sigma n = map (delta n) sigma         

С, что на месте, исходная задача сводится к:

closure (neighbors delta sigma) s