|
| Language.HaLex.Ndfa | | Portability | portable | | Stability | provisional | | Maintainer | jas@di.uminho.pt |
|
|
|
|
|
| Description |
Non-Deterministic Finite Automata in Haskell.
Code Included in the Lecture Notes on
Language Processing (with a functional flavour).
|
|
| Synopsis |
|
|
|
|
| Data type |
|
| data Ndfa st sy |
| Type of Non-Deterministic Finite Automata. Parameterized with
the type st of states and sy of symbols. | | Constructors | | Ndfa [sy] [st] [st] [st] (st -> Maybe sy -> [st]) | |
| | Instances | | (Show st, Show sy, Ord st, Ord sy) => Fa Ndfa st sy | | (Eq st, Show st, Show sy) => Show (Ndfa st sy) |
|
|
|
| Acceptance |
|
| ndfaaccept |
| :: Ord st | | | => Ndfa st sy | Automaton | | -> [sy] | Input symbols | | -> Bool | | | Test whether the given automaton accepts the given list of
input symbols. |
|
|
| ndfawalk |
| :: Ord st | | | => (st -> Maybe sy -> [st]) | Transition function | | -> [st] | Initial states | | -> [sy] | Input symbols | | -> [st] | Reached states | | Execute the transition function of a Ndfa on an initial state
and list of input symbol. Return the final state when all input
symbols have been consumed. |
|
|
| epsilon_closure |
| :: Ord st | | | => (st -> Maybe sy -> [st]) | Transition function | | -> [st] | Current states | | -> [st] | Reached states | | Compute the eplison closure of a Ndfa. |
|
|
| Transformation |
|
| ttNdfa2Ndfa |
| :: (Eq st, Eq sy) | | | => ([sy], [st], [st], [st], [(st, Maybe sy, st)]) | Tuple-based Ndfa | | -> Ndfa st sy | Automaton | | Reconstruct a Ndfa from a transition table.
Given a Ndfa expressed by a transition table
(ie a list of triples of the form
(Origin,Maybe Symbol,Destination)
it constructs a Ndfa. The other elements of the
input tuple are the vocabulary, a set of
states, and the sets of initial and final states
|
|
|
| Transitions |
|
| ndfaTransitionsFromTo :: Eq st => (st -> Maybe sy -> [st]) -> [sy] -> st -> st -> [Maybe sy] |
| Compute the labels with the same (giving) origin and destination |
|
| ndfadestinationsFrom |
| :: Ord st | | | => (st -> Maybe sy -> [st]) | Transition Function | | -> [sy] | Vocabulary | | -> st | Origin | | -> [st] | Destination States | | Compute the destination states giving the origin state |
|
|
| transitionTableNdfa |
| :: Ndfa st sy | Automaton | | -> [(st, Maybe sy, st)] | Transition table | Produce the transition table of a given Ndfa.
Given a Ndfa it returns a list of triples of the form
(Origin,Symbol,Destination)
defining all the transitions of the Ndfa.
|
|
|
| ndfareachedStatesFrom |
| :: Ord st | | | => (st -> Maybe 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 |
|
| toHaskell |
| :: Show fa | | | => fa | Automaton | | -> [Char] | Haskell module or file name | | -> IO () | | | Produce the transition table of a given finite automaton. |
|
|
| renameNdfa |
| :: Eq st | | | => Ndfa st sy | Automaton | | -> Int | Initial integer number | | -> Ndfa Int sy | Renamed Automaton | | Renames a Ndfa. |
|
|
| Properties of Ndfa |
|
| sizeNdfa |
| :: Ndfa st sy | Automaton | | -> Int | Size | | The size of an automaton is the number of its states. |
|
|
| ndfadeadstates |
| :: Ord st | | | => Ndfa st sy | Automaton | | -> [st] | Dead States | | Compute the dead states of a Ndfa
|
|
|
| Properties of States |
|
| ndfaIsStDead |
| :: Ord st | | | => (st -> Maybe sy -> [st]) | Transition Function | | -> [sy] | Vocabulary | | -> [st] | Set of Final States | | -> st | State | | -> Bool | | | Checks whether a Ndfa state is dead or not. |
|
|
| ndfanumberIncomingArrows |
| :: Eq st | | | => (st -> Maybe 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
|
|
|
| ndfanumberOutgoingArrows |
| :: Ord st | | | => (st -> Maybe sy -> [st]) | Transition Function | | -> [sy] | Vocabulary | | -> st | Origin | | -> Int | Number of Arrows | | Compute the number of outgoing arrows for a given state |
|
|
| Produced by Haddock version 0.6 |
