FSA

Class Simulator

java.lang.Object

FSA.Simulator

Direct Known Subclasses:

FMASimulator, PFSASimulator

public class Simulator
extends java.lang.Object

This class simulates a running of a FSA for accepting/refuting a string in input

Author:

Davide Basile

Field Summary

Fields

Modifier and Type	Field and Description
protected FSA	automa
protected int	pointer_state
protected int	pointer_string

Constructor Summary

Constructors

Constructor and Description
Simulator(FSA automa) The constructor

Method Summary

Methods

Modifier and Type	Method and Description
protected Transition	backtracking(java.util.Vector<Continuation> continuation, java.util.Vector<Continuation> visited) Select a transition in the continuation that is not visited, save it in the visited continuation and restore the state of the continuation.
void	changeAutoma(FSA automa) Change the automaton to simulate
protected boolean	checkContinuation(Transition tr, int symbol) If a transition was selected in the continuation (tr not null), then perform the step by updating the state of the simulator
protected static int	contains(int n, int[] a) check if n is contained in a
protected static int	contains(int n, java.util.Vector v) Check if n is contained in the vector v
protected Continuation	createContinuation() Freeze the actual state of the simulator in a continuation
protected boolean	isValid(Transition tr, int symbol) Check if the transition can be performed
protected void	restoreStateContinuation(Continuation c) restore the state of the simulator freezed in the continuation c
boolean	run(int[] s) At every iteration: first check if the string is consumed, then if we are in a final state and the side conditions are verified then the string is accepted, else backtracking if possible, otherwise return false if the string is not consumed yet: if there is a continuation then performs the step stored else if there are possible steps then performs one and store the others in the continuation if no possible step are allowed, then performs backtracking or if the continuation is empty return false
protected boolean	sideConditions() A method to be extended in case of additional conditions of acceptance
protected boolean	step(int symbol, java.util.Vector<Continuation> continuation, java.util.Vector<Continuation> visited) Select all the possible transition that can be executed in this configuration, then perform the first transition and store all the other in the continuation.
protected void	updateState(Transition tr, int symbol) Update the state of the simulator by performing the transition tr

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

pointer_state

protected int pointer_state

pointer_string

protected int pointer_string

automa

protected FSA automa

Constructor Detail

Simulator

public Simulator(FSA automa)

The constructor

Parameters:

automa - The automaton to simulate

Method Detail

changeAutoma

public void changeAutoma(FSA automa)

Change the automaton to simulate

Parameters:

automa -

run

public boolean run(int[] s)

At every iteration:

• • first check if the string is consumed, then if we are in a final state and the side conditions are verified then the string is accepted,
  • else backtracking if possible, otherwise return false
• if the string is not consumed yet:
  • if there is a continuation then performs the step stored
  • else if there are possible steps then performs one and store the others in the continuation
  • if no possible step are allowed, then performs backtracking or if the continuation is empty return false

Parameters:

s - the string to be recognized

Returns:

true if s is recognized by the automata, false otherwise

checkContinuation

protected boolean checkContinuation(Transition tr,
                        int symbol)

If a transition was selected in the continuation (tr not null), then perform the step by updating the state of the simulator

Parameters:

tr - transition to perform

symbol - the symbol in input

Returns:

true if tr is not null, otherwise false

backtracking

protected Transition backtracking(java.util.Vector<Continuation> continuation,
                      java.util.Vector<Continuation> visited)

Select a transition in the continuation that is not visited, save it in the visited continuation and restore the state of the continuation. If no transitions are available then return null

Parameters:

continuation - vector of continuation to be visited

visited - vector of visited continuation

Returns:

the Transition to be performed or null if no transition are available

restoreStateContinuation

protected void restoreStateContinuation(Continuation c)

restore the state of the simulator freezed in the continuation c

Parameters:

c - the continuation to be restored

sideConditions

protected boolean sideConditions()

A method to be extended in case of additional conditions of acceptance

Returns:

true

updateState

protected void updateState(Transition tr,
               int symbol)

Update the state of the simulator by performing the transition tr

Parameters:

tr - the transition to be performed

symbol - the symbol in input

isValid

protected boolean isValid(Transition tr,
              int symbol)

Check if the transition can be performed

Parameters:

tr - transition to be performed

symbol - symbol in input

Returns:

true if the transition is valid

step

protected boolean step(int symbol,
           java.util.Vector<Continuation> continuation,
           java.util.Vector<Continuation> visited)

Select all the possible transition that can be executed in this configuration, then perform the first transition and store all the other in the continuation. Finally save the performed transition in the visited continuation.

Parameters:

symbol - the symbol in input

continuation - the vector of continuation to be performed

visited - the vector of visited continuation

Returns:

true if a step is performed, otherwise false

createContinuation

protected Continuation createContinuation()

Freeze the actual state of the simulator in a continuation

Returns:

a new Continuation with the actual state of the simulator freezed

contains

protected static int contains(int n,
           int[] a)

check if n is contained in a

Parameters:

n - integer to search

a - array of integer

Returns:

the index of the element of the array that contains n, -1 if the element is not contained

contains

protected static int contains(int n,
           java.util.Vector v)

Check if n is contained in the vector v

Parameters:

n - the integer to be searched

v - a vector of integer

Returns:

if n is found then return the index of n in v, otherwise -1