|
Language.HaLex.Dfa | Portability | portable | Stability | provisional | Maintainer | jas@di.uminho.pt |
|
|
|
|
|
Description |
Deterministic Finite Automata in Haskell.
Code Included in the Lecture Notes on
Language Processing (with a functional flavour).
|
|
Synopsis |
|
data Dfa st sy = Dfa [sy] [st] st [st] (st -> sy -> st) | | dfawalk :: (st -> sy -> st) -> st -> [sy] -> st | | transitionsFromTo :: Eq st => (st -> sy -> st) -> [sy] -> st -> st -> [sy] | | transitionTableDfa :: (Ord st, Ord sy) => Dfa st sy -> [(st, sy, st)] | | ttDfa2Dfa :: (Eq st, Eq sy) => ([sy], [st], st, [st], [(st, sy, st)]) -> Dfa st sy | | beautifyDfa :: (Ord st, Ord sy) => Dfa st sy -> Dfa Int sy | | renameDfa :: (Ord st, Ord sy) => Dfa st sy -> Int -> Dfa Int sy | | beautifyDfaWithSyncSt :: Eq st => Dfa [st] sy -> Dfa [Int] sy | | dfaIO :: (Show st, Show sy) => Dfa st sy -> String -> IO () | | dfaaccept :: Eq st => Dfa st sy -> [sy] -> Bool | | sizeDfa :: Dfa st sy -> Int | | dfa2tdfa :: (Eq st, Ord sy) => Dfa st sy -> TableDfa st | | showDfaDelta :: (Show st, Show sy) => [st] -> [sy] -> (st -> sy -> st) -> [Char] -> [Char] |
|
|
|
Data type |
|
data Dfa st sy |
The type of Deterministic Finite Automata. Paramterized with
the type st of states and sy of symbols. | Constructors | Dfa [sy] [st] st [st] (st -> sy -> st) | |
| Instances | (Show st, Show sy) => Show (Dfa st sy) | (Show st, Show sy, Ord st, Ord sy) => Fa Dfa st sy |
|
|
|
dfawalk |
:: (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. |
|
|
transitionsFromTo :: Eq st => (st -> sy -> st) -> [sy] -> st -> st -> [sy] |
Compute the labels with the same (giving) origin and destination |
|
transitionTableDfa |
:: (Ord st, Ord sy) | | => Dfa st sy | Automaton | -> [(st, sy, st)] | Transition table | Produce the transition table of a given Dfa.
Given a Dfa, it returns a list of triples of the form
(Origin,Symbol,Destination)
defining all the transitions of the Dfa.
|
|
|
ttDfa2Dfa :: (Eq st, Eq sy) => ([sy], [st], st, [st], [(st, sy, st)]) -> Dfa st sy |
Reconstruct a Dfa from a transition table.
Given a DFA expressed by a transition table
(ie a list of triples of the form
(Origin,Symbol,Destination)
it constructs a DFA. The other elements of the
input tuple are the vocabulary, a set of
states, an initial state, and a set of
final states. |
|
beautifyDfa :: (Ord st, Ord sy) => Dfa st sy -> Dfa Int sy |
|
renameDfa |
:: (Ord st, Ord sy) | | => Dfa st sy | Automaton | -> Int | Initial state ID | -> Dfa Int sy | Renamed automaton | 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.
|
|
|
beautifyDfaWithSyncSt :: Eq st => Dfa [st] sy -> Dfa [Int] sy |
|
dfaIO |
:: (Show st, Show sy) | | => Dfa st sy | Automaton | -> String | Haskell module name | -> IO () | | Write a Dfa to a Haskell module or file on file. |
|
|
dfaaccept |
:: Eq st | | => Dfa st sy | Automaton | -> [sy] | Input symbols | -> Bool | | Test whether the given automaton accepts the given list of
input symbols (expressed as a fold). |
|
|
sizeDfa :: Dfa st sy -> Int |
Compute the size of a deterministic finite automaton
The size of an automaton is the number of its states. |
|
dfa2tdfa :: (Eq st, Ord sy) => Dfa st sy -> TableDfa st |
|
showDfaDelta :: (Show st, Show sy) => [st] -> [sy] -> (st -> sy -> st) -> [Char] -> [Char] |
Helper function to show the transition function of a Dfa. |
|
Produced by Haddock version 0.6 |