Copyright	(c) João Saraiva 200120022003200420052017
License	LGPL
Maintainer	jas@di.uminho.pt
Stability	provisional
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Language.HaLex.Dfa

Contents

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
type TableDfa st = [(st, [st])]
ttAllSts :: TableDfa st -> [st]
ttAllDestSts :: Eq st => TableDfa st -> [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
complementDfa :: Eq st => Dfa st sy -> Dfa st sy
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
nodesAndEdgesDfa :: (Eq st, Ord st, Ord sy) => Dfa st sy -> (Int, Int)
nodesAndEdgesNoSyncDfa :: (Eq st, Ord st, Ord sy) => Dfa st sy -> (Int, Int)
dfadeadstates :: Ord st => Dfa st sy -> [st]
dfasyncstates :: Eq st => Dfa st sy -> [st]
cyclomaticDfa :: (Ord st, Ord sy) => Dfa st sy -> Int
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

data Dfa st sy Source #

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

Instances details

(Show st, Show sy, Ord st, Ord sy) => Fa Dfa st sy Source #	Instance of class `Fa` for a `Dfa`
Instance details Defined in Language.HaLex.FaClasses Methods accept :: Dfa st sy -> [sy] -> Bool Source # sizeFa :: Dfa st sy -> Int Source # equiv :: Dfa st sy -> Dfa st sy -> Bool Source # minimize :: Dfa st sy -> Dfa [[st]] sy Source # reverseFa :: Dfa st sy -> Ndfa st sy Source # deadstates :: Dfa st sy -> [st] Source # syncstates :: Dfa st sy -> [st] Source # cyclomatic :: Dfa st sy -> Int Source # sentences :: Dfa st sy -> [[sy]] Source # toHaskell' :: Dfa st sy -> String -> IO () Source # toGraph :: Dfa st sy -> String -> String Source # toGraphIO :: Dfa st sy -> String -> IO () Source # unionFa :: Dfa st sy -> Dfa st sy -> Ndfa st sy Source # concatFa :: Dfa st sy -> Dfa st sy -> Ndfa st sy Source # starFa :: Dfa st sy -> Ndfa st sy Source # plusFa :: Dfa st sy -> Ndfa st sy Source #
(Show st, Show sy) => Show (Dfa st sy) Source #	Print a `Dfa` as a Haskell function.
Instance details Defined in Language.HaLex.Dfa Methods showsPrec :: Int -> Dfa st sy -> ShowS # show :: Dfa st sy -> String # showList :: [Dfa st sy] -> ShowS #

Acceptance

dfaaccept Source #

Arguments

:: 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).

dfawalk Source #

Arguments

:: (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

type TableDfa st = [(st, [st])] Source #

Type of Table-based Deterministic Finite Automata. v1 , v2 , ... , vn vocabulary [ ( o1 , [ d , d , ... , d ]) , ( o2 , [ d , d , ... , d ]) ... ]

ttAllSts :: TableDfa st -> [st] Source #

Compute all states in a transtion table defining a Dfa

ttAllDestSts Source #

Arguments

:: Eq st
=> TableDfa st	Transition Table (maybe not totally defined)
-> [st]	set of states in the table

Compute all destinations states in a (transition) table It considers all states in the second element of the pair: the destion states. Usefull when the transition table is being constructed.

ttDfa2Dfa Source #

Arguments

:: (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.

dfa2tdfa Source #

Arguments

:: (Eq st, Ord sy)
=> Dfa st sy	Automaton
-> TableDfa st	Transition table

Dfa to a Transition Table-based Dfa

complementDfa Source #

Arguments

:: Eq st
=> Dfa st sy	Original `Dfa`
-> Dfa st sy	Resulting `Dfa`

Complement of a Dfa

Transitions

transitionsFromTo Source #

Arguments

:: 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

destinationsFrom Source #

Arguments

:: (st -> sy -> st)	Tansition Function
-> [sy]	Vocabulary
-> st	Origin
-> [st]	Destination States

Compute the destination states giving the origin state

transitionTableDfa Source #

Arguments

:: (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.

transitionTableDfa' Source #

Arguments

:: (Ord st, Ord sy)
=> Dfa st sy	Automaton
-> [(st, [st])]	Transition table

Produce the transition table of a given Dfa. Given a Dfa, it returns a list of triples of the form (Origin,[Destination]) defining all the transitions of the Dfa.

reachedStatesFrom Source #

Arguments

:: (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.

renameDfa Source #

Arguments

:: (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.

showDfaDelta :: (Show st, Show sy) => [st] -> [sy] -> (st -> sy -> st) -> [Char] -> [Char] Source #

Helper function to show the transition function of a Dfa.

beautifyDfaWithSyncSt Source #

Arguments

:: Eq st
=> Dfa [st] sy	Original Automaton
-> Dfa [Int] sy	Beautified Automaton (states as integers)

dfaIO Source #

Arguments

:: (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`

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.

nodesAndEdgesDfa Source #

Arguments

:: (Eq st, Ord st, Ord sy)
=> Dfa st sy	Automaton
-> (Int, Int)	(#States, #Transitions)

Compute the number of states and transtions of a Dfa

nodesAndEdgesNoSyncDfa Source #

Arguments

:: (Eq st, Ord st, Ord sy)
=> Dfa st sy	Automaton
-> (Int, Int)	(#States, #Transitions)

Compute the number of states and transtions of a Dfa It does not consider nodes (nor transitions to) dead states nor sync states.

dfadeadstates Source #

Arguments

:: Ord st
=> Dfa st sy	Automaton
-> [st]	Dead states

Compute the dead states of a Dfa

dfasyncstates Source #

Arguments

:: Eq st
=> Dfa st sy	Automaton
-> [st]	Dead states

Compute the sync states of a Dfa

cyclomaticDfa :: (Ord st, Ord sy) => Dfa st sy -> Int Source #

Compute the cyclomatic complexity of a Dfa The Cyclomatic Complexity (CC) is given by cc = N - E + 2 * P where N is the number of nodes E is the number of edges P is tne number of connected components

Properties of States

isStDead Source #

Arguments

:: 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)

isStSync Source #

Arguments

:: 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 ans it is not final/accepting state.

numberOutgoingArrows Source #

Arguments

:: (st -> sy -> st)	Transition Function
-> [sy]	Vocabulary
-> st	Origin
-> Int	Number of Arrows

Compute the number of outgoing arrows for a given state

numberIncomingArrows Source #

Arguments

:: 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

Data type

Instances

Acceptance

Transformation

Transitions

Printing

Properties of Dfa

Properties of States

Properties of `Dfa`