Search code examples
haskellautomata

Check whether it accepts a finite determinant automaton at least one word of length k, if so - print it, else - print "No"

I wrote data structure and some functions for automata, but I stuck with find_way function that will accept automata object and k.

type FSM q = ([q], Alphabet, [Transition q], q, [q])
type Alphabet = [Char]
type Transition q = (q, Char, q)

states :: FSM q -> [q]
states (u, _, _, _, _) = u

alph :: FSM q -> Alphabet
alph (_, a, _, _, _) = a
trans :: FSM q -> [Transition q]
trans (_, _, t, _, _) = t
start :: FSM q -> q
start (_, _, _, s, _) = s
final :: FSM q -> [q]
final (_, _, _, _, f) = f

--return a or Nothing if no transition found
delta :: Eq a => FSM a -> a -> Char -> Maybe a
delta m st symbol = listToMaybe [q1 | (q0, x, q1) <- trans m, q0 == st, x == symbol]

--return "No" or first accepted word found
    
goal:: Eq a => FSM a -> Int -> String
goal m k = fromMaybe "No" $ asum [find_way m k x | x <- alph m]

find_way :: Eq a => FSM a -> Int -> Char -> Maybe String
Solution

  • I guess the "obvious" way to implement this is for find_way to use delta to take one step in the automata, then recursively call goal with a modified FSM with a different initial state. Don't forget to add a base case somewhere for when the user asks whether a length-0 string gets accepted.

    But that way is horribly inefficient. I recommend a different way:

    1. Make a new type, type Witness a = (String, a) or similar. The idea of this type is that the pair contains String and the state you would get to if you started from an FSM's initial state and used that String.
    2. Write a function successors :: Ord a => FSM a -> [Witness a] -> [Witness a] which, given a set of states, finds all the states that can be reached in just one transition from at least one of those states. There may be many ways to reach a given state, so make sure this de-duplicates its output, keeping just one Witness for each state (doesn't matter which one).
    3. Iterate that function k times, starting from the set that only has the FSM's initial state and the empty string, then check if there's any states both in the output and the FSM's final states.

    The first/obvious way is something like O(a^k), where a is the size of the alphabet and k is the length being queried. The proposed different way is more like O(k*n*(a+log(n))) where n is the total number of states (and a and k are as before).