FSM.Automata

Documentation

data Automata

Instances

Show Automata

Defined in FSM.Automata

Methods

showsPrec :: Int -> Automata -> ShowS

show :: Automata -> String

showList :: [Automata] -> ShowS

Creating functions

createAutomata :: Int -> String -> Int -> Matrix Int -> [Int] -> Automata

This is the main function for creating the Automata abstract data type. By default, the inital state and the current state of the automata are the same.

Please pay attention to how the object is built. E.g.,

createAutomata s i s0 m a

where:

• s is the number of states of the automata.
• i is the alphabet the automata accepts.
• s0 is the initial state of the automata.
• m is the matrix of associations of the automata. (Details here: getAssociations)
• a is the list of accepting states of the automata.

More specifically you could

import qualified Data.Matrix as M
mat = M.fromLists [[2,0,0,0],[2,1,4,0],[1,4,0,0],[0,0,0,3]]
tom = createAutomata 4 ['a', 'b', 'c', 'd'] 1 mat [4]

Accessing functions

getStates :: Automata -> Set Int

This function returns the set of states of the automata. It is really of not much use since the generation of the automata only needs the number of states and not the whole set of them, but just in case you want to check which states does the current automata have.

getAcceptingStates :: Automata -> [Int]

This function returns the list of accepting states of the automata. It is a list and not a set for coherence purpouses. When you build the automata you have to give a list of accepting states so I though it made sense to also return a list of accepting states as the accessing function.

getInitialState :: Automata -> Int

This function returns the current initial state of the automata.

getInputs :: Automata -> String

This function returns the string of inputs (alphabet) that the automata accepts.

getAssociations :: Automata -> Matrix Int

This function returns the associations matrix of the automata. This matrix is built according to the following rules:

1. The columns of the matrix represent the inputs of the alphabet that the automata accepts in lexicographical order.
2. The rows of the matrix represent the states of the automata in ascending order.
3. The element \(a_{ij} = k \) means that the state \(i\) is connected to the state \(k\) thanks to the input that the column \(j\) of the matrix represents.

More info can be found here: Wikipedia: State-transition table

Continuing with the previous example, the following matrix correspongs to the automata in the figure.

mat = M.fromLists [[2,0,0,0],[2,1,4,0],[1,4,0,0],[0,0,0,3]]
tom = createAutomata 4 ['a', 'b', 'c', 'd'] 1 mat [4] 1

The code above represent this matrix:

    'a' 'b' 'c' 'd'         <= inputs
  ------------------
1 |  2   0   0   0 
2 |  2   1   4   0  
3 |  1   4   0   0 
4 |  0   0   0   3  

^
|
states

And the matrix above represents the transitions in the following automata:

getTransitions :: Automata -> Int -> Set Char

This function returns the inputs that a state accepts for transitioning into another state.

getOutgoingStates :: Automata -> Int -> Set Int

This function returns the states you can possibly reach from a given state.

getIncomingStates :: Automata -> Int -> Set Int

This function returns the states that can possibly reach a given state.

getDeadlocks :: Automata -> Set Int

This function returns those states of the automata that do not have any input to any other state (except for itself), i.e., once that a deadlock state is reached, none of the rest of state can be reached anymore for the current execution.

getIsolated :: Automata -> Set Int

This function returns the states of the given automata that cannot be reached.

Checking functions

validInput :: String -> Automata -> Bool

This function test if a string is valid, i.e., if when the automata receives the string, ends in one of the accepting states.

Editing functions

addState :: Automata -> [Int] -> Automata

Function for adding a state to an Automata with the list of associations to the other states. If you would want to add a non-connected state, simply enter the list [0,..,0], with as many zeros as possible inputs.

deleteState :: Automata -> Int -> Automata

This function deletes a state and all the connections it has with any other state. Please note that this function automatically reassigns new numbers for the remaining states, so the states and the associations matrix change accordingly. E.g. if you delete in the previous automata the 3rd state, then since the new automata has just 3 states, the old 4th state becomes the new 3rd state.

changeInitialState :: Automata -> Int -> Automata

This function changes the initial state.

addAcceptingState :: Automata -> Int -> Automata

This function adds one accepting state