FSM-0.0.4.0: Basic concepts of finite state machines.
Safe HaskellNone
LanguageHaskell2010

FSM.Automata

Synopsis

Documentation

data Automata Source #

Instances

Instances details
Show Automata Source # 
Instance details

Defined in FSM.Automata

Creating functions

createAutomata :: Int -> String -> Int -> Matrix Int -> [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 c0

where:

  • s is the number of states of the automata.
  • i is the language 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.
  • c0 is the placeholder for the current state. If it's the first time defining this Automata, leave it as c0 = s0

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] 1

Accessing functions

getStates :: Automata -> Set Int Source #

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

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

This function returns the current initial state of the automata.

getInputs :: Automata -> String Source #

This function returns the string of inputs that the automata accepts.

getAssociations :: Automata -> Matrix Int Source #

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

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

getCurrentState :: Automata -> Int Source #

This function returns the current state in which the automata currently is.

getOutgoingStates :: Automata -> Int -> Set Int Source #

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

getIncomingStates :: Automata -> Int -> Set Int Source #

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

getHoles :: Automata -> Set Int Source #

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

getIsolated :: Automata -> Set Int Source #

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

Checking functions

validInput :: String -> Automata -> Bool Source #

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

Action functions

performAction :: Automata -> Char -> Automata Source #

This funcion perform the given transition from the current state and changes to a new current state.

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.

deleteState :: Automata -> Int -> Automata Source #

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

This function changes the initial state.

changeCurrentState :: Automata -> Int -> Automata Source #

This function changes the current state.

addAcceptingState :: Automata -> Int -> Automata Source #

This function adds one accepting state