Safe Haskell	Safe

DFA_

Description

Operations on DFAs and conversion from NFAs

Synopsis

complement :: Ord a => DFA a -> DFA a
intersect :: (Ord a, Ord b) => DFA a -> DFA b -> DFA (a, b)
fromNFA :: Ord a => NFA a -> DFA (Set a)

Documentation

complement :: Ord a => DFA a -> DFA a #

Construct the complement the DFA.

Formally, given a DFA D recognising the language A, the complement D' recognises the language A^C = { w | w ∈ Σ*, w ∉ A }.

>>> (complement dOddOnes) `accepts` "101"
False

>>> (complement dOddOnes) `accepts` "0"
True

intersect :: (Ord a, Ord b) => DFA a -> DFA b -> DFA (a, b) #

Construct the intersection of the 2 DFAs.

Formally, given DFAs D1 and D2 recognising the languages A1 and A2, the interesction of D1 and D2 recognise the language A1 ∩ A2.

fromNFA :: Ord a => NFA a -> DFA (Set a) #

Construct a DFA that is equivalent to the NFA.

Idea: Given an NFA N = (Q, Σ, δ, q0, F), the set of states of the equivalent DFA D is the power set of Q; the start state is the set of states reachable from q0 following 0 or more ε arrows; the accept states are the sets which contain a member of F; the transition function keeps track of the set of states that the NFA would be in.