| Safe Haskell | Safe |
|---|
NFA
Description
Definition, construction, computation and transformation of NFAs
Synopsis
- type Transition a = Map (a, Char) (Set a)
- emptyStr :: Char
- data NFA a = NFA {
- states :: Set a
- alphabet :: Set Char
- transition :: Transition a
- startState :: a
- acceptStates :: Set a
- isValid :: (Ord a, Show a) => NFA a -> Bool
- fillTransition :: Ord a => Set a -> Set Char -> Transition a -> Transition a
- nOddOnes :: NFA String
- statesReachableAlongεArrowsFrom :: Ord a => NFA a -> Set a -> Set a
- compute :: Ord a => NFA a -> String -> [Set a]
- accepts :: Ord a => NFA a -> String -> Bool
- mapStates :: (Ord a, Ord b) => (a -> b) -> NFA a -> NFA b
- numberStates :: Ord a => NFA a -> NFA Int
Documentation
type Transition a = Map (a, Char) (Set a) #
Nondetermisnitic finite automata
Constructors
| NFA | |
Fields
| |
isValid :: (Ord a, Show a) => NFA a -> Bool #
Checks if the given NFA (Q, Σ, δ, q0, F) is valid:
- δ(Q x Σ_ε) ⊆ P(Q);
- q0 ∈ Q;
- F ⊆ Q.
fillTransition :: Ord a => Set a -> Set Char -> Transition a -> Transition a #
Fill the transition function by assigning ∅ to the missing keys of Q x Σ_ε.
For example, the total transition function for the NFA recognising the empty
set, with the alphabet being {a, b} (\949 is emptyStr):
>>>fillTransition (S.fromList [0]) (S.fromList ['a', 'b']) M.emptyfromList [((0,'a'),fromList []),((0,'b'),fromList []),((0,'\949'),fromList [])]
sample NFA recognising the language { w | every odd position of w is a 1 }
>>>nOddOnes `accepts` "10101"True
>>>nOddOnes `accepts` "000"False
>>>nOddOnes `accepts` ""True
statesReachableAlongεArrowsFrom :: Ord a => NFA a -> Set a -> Set a #
Compute the set of states reachable from the given set by following 0 or more ε arrows.
compute :: Ord a => NFA a -> String -> [Set a] #
Compute the sequence of states when the NFA is computing on the string.
accepts :: Ord a => NFA a -> String -> Bool #
Simulate the NFA and return whether it accepts the string.
Formally, an NFA (Q, Σ, δ, q0, F) accepts a string w if w can be written as w = y_1...y_n where each y_i ∈ Σ_ε and a sequence of states r_0, r_1, ..., r_m in Q exists satisfying:
- r_0 = q0;
- δ(r_i, y_i+1) ∈ r_i+1 for i = 0..m-1;
- r_m ∈ F.