FSM-1.0.0: Basic concepts of finite state machines.

FSM.Automata

Synopsis

# Documentation

data Automata Source #

#### Instances

Instances details
 Source # Instance detailsDefined in FSM.Automata MethodsshowList :: [Automata] -> ShowS #

# Creating functions

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

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

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.

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.

This function returns the current initial state of the automata.

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

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.

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:

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

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

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

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.

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

# Checking functions

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 Source #

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.

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.

This function changes the initial state.

This function adds one accepting state