Language.HaLex.Dfa

Deterministic Finite Automata in Haskell.

Code Included in the Lecture Notes on Language Processing (with a functional flavour).

Data type

data Dfa st sy

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

(Show st, Show sy, Ord st, Ord sy) => Fa Dfa st sy

Instance of class Fa for a Dfa

Methods

accept :: Dfa st sy -> [sy] -> Bool

sizeFa :: Dfa st sy -> Int

equiv :: Dfa st sy -> Dfa st sy -> Bool

minimize :: Dfa st sy -> Dfa [[st]] sy

reverseFa :: Dfa st sy -> Ndfa st sy

deadstates :: Dfa st sy -> [st]

sentences :: Dfa st sy -> [[sy]]

toHaskell' :: Dfa st sy -> String -> IO ()

toGraph :: Dfa st sy -> String -> String

toGraphIO :: Dfa st sy -> String -> IO ()

unionFa :: Dfa st sy -> Dfa st sy -> Ndfa st sy

concatFa :: Dfa st sy -> Dfa st sy -> Ndfa st sy

starFa :: Dfa st sy -> Ndfa st sy

plusFa :: Dfa st sy -> Ndfa st sy

(Show st, Show sy) => Show (Dfa st sy)

Print a Dfa as a Haskell function.

Methods

showsPrec :: Int -> Dfa st sy -> ShowS

show :: Dfa st sy -> String

showList :: [Dfa st sy] -> ShowS

Acceptance

dfaaccept

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

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

ttDfa2Dfa

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

Arguments

:: (Eq st, Ord sy)

=> Dfa st sy

Automaton

-> TableDfa st

Transition table

Dfa to a Table-based Dfa

Transitions

transitionsFromTo

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

Arguments

:: (st -> sy -> st)

Tansition Function

-> [sy]

Vocabulary

-> st

Origin

-> [st]

Destination States

Compute the destination states giving the origin state

transitionTableDfa

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'

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

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

Beautify a Dfa by assigning (natural) numbers to states.

renameDfa

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]

Helper function to show the transition function of a Dfa.

beautifyDfaWithSyncSt

Arguments

:: Eq st

=> Dfa [st] sy

Original Automaton

-> Dfa [Int] sy

Beautified Automaton (states as integers)

dfaIO

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

Compute the size of a deterministic finite automaton. The size of an automaton is the number of its states.

dfadeadstates

Arguments

:: Ord st

=> Dfa st sy

Automaton

-> [st]

Dead states

Compute the dead states of a Dfa

Properties of States

isStDead

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

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

numberOutgoingArrows

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

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