| Safe Haskell | Safe |
|---|
DFA
Description
Definition, construction, computation and transformation of DFAs
Synopsis
- data DFA a = DFA {
- states :: Set a
- alphabet :: Set Char
- transition :: Map (a, Char) a
- startState :: a
- acceptStates :: Set a
- isValid :: (Ord a, Show a) => DFA a -> Bool
- dOddOnes :: DFA String
- compute :: Ord a => DFA a -> String -> [a]
- accepts :: Ord a => DFA a -> String -> Bool
- mapStates :: (Ord a, Ord b) => (a -> b) -> DFA a -> DFA b
- numberStates :: Ord a => DFA a -> DFA Int
Documentation
Deterministic finite automata
Constructors
| DFA | |
Fields
| |
isValid :: (Ord a, Show a) => DFA a -> Bool #
Checks if the given DFA (Q, Σ, δ, q0, F) is valid:
- δ is total on QxΣ, and δ(QxΣ) ⊆ Q;
- q0 ∈ Q;
- F ⊆ Q.
sample DFA recognising the language { w | every odd position of w is a 1 }
>>>dOddOnes `accepts` "10101"True
>>>dOddOnes `accepts` "000"False
>>>dOddOnes `accepts` ""True
compute :: Ord a => DFA a -> String -> [a] #
Compute the sequence of states when the DFA is computing on the string.
accepts :: Ord a => DFA a -> String -> Bool #
Simulate the DFA and return whether it accepts the string.
Formally, a DFA (Q, Σ, δ, q0, F) accepts a string w = w_1...w_n if a sequence of states r_0, r_1, ..., r_n in Q exists satisfying:
- r_0 = q0;
- δ(r_i, w_i+1) = r_i+1 for i = 0..n-1;
- r_n ∈ F.