Return all reachable states in a DFA starting from the initial state

I'm trying to write a program in Haskell that returns a list of reachable states starting from the initial state, similar to a depth first search.

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

Note:

qs is the set of states
sigma is the alphabet
delta is a transition function that takes a state and a symbol and returns the next state
s is the initial state
inF is a function that returns true if the state is an accepting state, false otherwise

As the function is defined now:

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

returns all the states in the DFA (which is incorrect).

What I would like is to populate the list by starting at the initial state s and testing the delta function with each input.

For example:

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

The next step would be to repeat the process for each new state added to the list. This might add duplicates, but I can remove them later.

Then I tried:

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

I thought this might work, but it doesn't because it's creating the inner list and then using it to populate the outer list and then stopping.

I need to recursively build this list by exploring all the new states returned by the delta function.

Solution

You're attempting to compute the transitive closure of a relation here, where the relation is "x can get to y in one step". As such, I'd suggest using a generic transitive-closure solution, rather than a DFA-specific one, and then produce that relation from your DFA. Here's one fairly basic way to do it:

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'

The algorithm here is to have a list of reachable states, and at each step expand it by walking from each to all its nearest neighbors, and then nub the list to get rid of duplicates. Once that expansion step adds no new nodes, you're done.

Now, how to map your DFA problem onto this? It's not too hard: you just need to produce a nexts function using sigma and delta. Here we need to assume that your DFA delta function is total, ie that every node has a transition specified for every letter in sigma. This is easy enough by creating one additional "failure" node that all nodes can transition to if they don't like their input, so I'll just assume that's been done.

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

With that in place, your original problem reduces to:

closure (neighbors delta sigma) s