|
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) | | 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)] | | 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.
| Constructors | Dfa [sy] [st] st [st] (st -> sy -> st) | |
| Instances | |
|
|
Acceptance
|
|
|
:: 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).
|
|
|
|
:: | | => 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
|
|
|
:: (Eq st, Eq sy) | | => ([sy], [st], st, [st], [(st, sy, st)]) | Tuple-based Automaton
| -> Dfa st sy | Automaton
| Reconstruct a Dfa from a transition table.
Given an automaton 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.
|
|
|
|
:: (Eq st, Ord sy) | | => Dfa st sy | Automaton
| -> TableDfa st | Transition table
| 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
|
|
|
|
:: (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.
|
|
|
|
:: (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
|
|
|
Beautify a Dfa by assigning (natural) numbers to states.
|
|
|
:: (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.
|
|
|
|
Helper function to show the transition function of a Dfa.
|
|
|
:: Eq st | | => Dfa [st] sy | Original Automaton
| -> Dfa [Int] sy | Beautified Automaton (states as integers)
|
|
|
|
:: (Show st, Show sy) | | => Dfa st sy | Automaton
| -> String | Haskell module name
| -> IO () | | Write a Dfa to a Haskell module in a file.
|
|
|
Properties of Dfa
|
|
|
Compute the size of a deterministic finite automaton.
The size of an automaton is the number of its states.
|
|
|
:: Ord st | | => Dfa st sy | Automaton
| -> [st] | Dead 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
|
|
|
|
:: Eq st | | => st -> sy -> st | Transition Function
| -> [sy] | Vocabulary
| -> [st] | Set of States
| -> st | Destination
| -> Int | Number of Arrows
| Compute the number of incoming arrows for a given state
|
|
|
Produced by Haddock version 2.3.0 |