Copyright | (c) Joãoo Saraiva 20012002200320042005 |
---|---|
License | LGPL |
Maintainer | jas@di.uminho.pt |
Stability | provisional |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell98 |
Deterministic Finite Automata in Haskell.
Code Included in the Lecture Notes on Language Processing (with a functional flavour).
- data Dfa st sy = Dfa [sy] [st] st [st] (st -> sy -> st)
- dfaaccept :: Eq st => Dfa st sy -> [sy] -> Bool
- dfawalk :: (st -> sy -> st) -> st -> [sy] -> st
- ttDfa2Dfa :: (Eq st, Eq sy) => ([sy], [st], st, [st], [(st, sy, st)]) -> Dfa st sy
- dfa2tdfa :: (Eq st, Ord sy) => Dfa st sy -> TableDfa st
- transitionsFromTo :: Eq st => (st -> sy -> st) -> [sy] -> st -> st -> [sy]
- destinationsFrom :: (st -> sy -> st) -> [sy] -> st -> [st]
- transitionTableDfa :: (Ord st, Ord sy) => Dfa st sy -> [(st, sy, st)]
- transitionTableDfa' :: (Ord st, Ord sy) => Dfa st sy -> [(st, [st])]
- reachedStatesFrom :: (Eq [st], Ord st) => (st -> sy -> st) -> [sy] -> st -> [st]
- beautifyDfa :: (Ord st, Ord sy) => Dfa st sy -> Dfa Int sy
- renameDfa :: (Ord st, Ord sy) => Dfa st sy -> Int -> Dfa Int sy
- showDfaDelta :: (Show st, Show sy) => [st] -> [sy] -> (st -> sy -> st) -> [Char] -> [Char]
- beautifyDfaWithSyncSt :: Eq st => Dfa [st] sy -> Dfa [Int] sy
- dfaIO :: (Show st, Show sy) => Dfa st sy -> String -> IO ()
- sizeDfa :: Dfa st sy -> Int
- dfadeadstates :: Ord st => Dfa st sy -> [st]
- isStDead :: Ord st => (st -> sy -> st) -> [sy] -> [st] -> st -> Bool
- isStSync :: Eq st => (st -> sy -> st) -> [sy] -> [st] -> st -> Bool
- numberOutgoingArrows :: (st -> sy -> st) -> [sy] -> st -> Int
- numberIncomingArrows :: Eq st => (st -> sy -> st) -> [sy] -> [st] -> st -> Int
Data type
The type of Deterministic Finite Automata parameterized with
the type st
of states and sy
of symbols.
Dfa [sy] [st] st [st] (st -> sy -> st) |
Acceptance
Test whether the given automaton accepts the given list of input symbols (expressed as a fold).
:: (st -> sy -> st) | Transition function |
-> st | Initial state |
-> [sy] | Input symbols |
-> st | Final state |
Execute the transition function of a Dfa
on an initial state
and list of input symbol. Return the final state when all input
symbols have been consumed.
Transformation
Dfa to a Table-based Dfa
Transitions
:: Eq st | |
=> (st -> sy -> st) | Transition function |
-> [sy] | Vocabulary |
-> st | Origin |
-> st | Destination |
-> [sy] | Labels |
Compute the labels with the same (giving) origin and destination states
:: (st -> sy -> st) | Tansition Function |
-> [sy] | Vocabulary |
-> st | Origin |
-> [st] | Destination States |
Compute the destination states giving the origin state
:: (Eq [st], Ord st) | |
=> (st -> sy -> st) | Transition function |
-> [sy] | Vocabulary |
-> st | Origin |
-> [st] | Reached states |
Compute the states that can be reached from a state according to a given transition function and vocabulary
Printing
beautifyDfa :: (Ord st, Ord sy) => Dfa st sy -> Dfa Int sy Source #
Beautify a Dfa
by assigning (natural) numbers to states.
Renames a Dfa
.
It renames a DFA in such a way that the renaming of two isomorphic DFA
returns the same DFA.
It is the basis for the equivalence test for minimized DFA.
showDfaDelta :: (Show st, Show sy) => [st] -> [sy] -> (st -> sy -> st) -> [Char] -> [Char] Source #
Helper function to show the transition function of a Dfa
.
Write a Dfa
to a Haskell module in a file.
Properties of Dfa
sizeDfa :: Dfa st sy -> Int Source #
Compute the size of a deterministic finite automaton. The size of an automaton is the number of its states.
Compute the dead states of a Dfa
Properties of States
:: Ord st | |
=> (st -> sy -> st) | Transition Function |
-> [sy] | Vocabulary |
-> [st] | Set of Final States |
-> st | State |
-> Bool |
Checks whether a state is dead or not.
One state is dead when it is not possible to reach a final state from it. (probably we should consider that it has to be reachable from the initial state, as well)
:: Eq st | |
=> (st -> sy -> st) | Transition Function |
-> [sy] | Vocabulary |
-> [st] | Set of Final States |
-> st | State |
-> Bool |
Checks whether a state is a sync state or not
A sync state is a state that has transitions to itself for all symbols of the vocabulary
:: (st -> sy -> st) | Transition Function |
-> [sy] | Vocabulary |
-> st | Origin |
-> Int | Number of Arrows |
Compute the number of outgoing arrows for a given state