Software Applications With Finite State Machines Computer Science Essay

Published:

Automata-based programming is a fundamental style of computer programming (which is a style of solving specific software engineering problems.), in which the program of its part is thought of as a model of a finite state machine (FSM) or any other (often more complicated) formal automata. Sometimes a potentially-infinite set of possible states is introduced, and such a set can have a complicated structure, not just an enumeration.

FSM-based programming is generally the same, but, formally speaking, doesn't cover all possible variants as FSM stands for finite state machine and automata-based programming doesn't necessarily employ FSMs in the strict sense.

The time period of the program's execution is clearly separated down to the steps of the automaton. Each of the steps is effectively an execution of a code section (same for all the steps), which possesses a single entry point. Such a section can be a function or other routine, or just a cycle body. The step section might be broken down to subsection to be executed depending on different states, although this is not necessary.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Any communication between the steps is only possible via the explicitly noted set of variables named the state. Between any two steps, the program (or its part created using the automata-based technique) can not have inexplicit components of its state, such as local (stack) variables' values, return addresses, the current instruction pointer etc. That is, the state of the whole program, taken at any two moments of entering the step of the automaton, can only differ in the values of the variables being considered as the state of the automaton.

The whole execution of the automata-based code is a (possibly explicit) cycle of the automaton's steps.

Another reason to use the notion of automata-based programming is that the programmer's style of thinking about the program in this technique is very similar to the style of thinking used to solve math-related tasks using Turing machine, Markov algorithmetc.

Example

Consider we need a program in C that reads a text from standard input stream, line by line, and prints the first word of each line. It is clear we need first to read and skip the leading spaces, if any, then read characters of the first word and print them until the word ends, and then read and skip all the remaining characters until the end-of-line character is encountered. Upon the end of line character (regardless of the stage) we restart the algorithm from the beginning, and in case the end of file condition (regardless of the stage) we terminate the program.

Traditional (imperative) program in C

The program which solves the example task in traditional (imperative) style can look something like this:

#include <stdio.h>

int main(void)

{

int c;

do {

c = getchar();

while(c == ' ')

c = getchar();

while(c != EOF && c != ' ' && c != '\n') {

putchar(c);

c = getchar();

}

putchar('\n');

while(c != EOF && c != '\n')

c = getchar();

} while(c != EOF);

return 0;

}

Automata-based style program

The same task can be solved thinking in terms of finite state machines. Please note that line parsing has three stages: skipping the leading spaces, printing the word and skipping the trailing characters. Let's call them states before, inside and after. The program may now look like this:

#include <stdio.h>

int main(void)

{

enum states {

before, inside, after

} state;

int c;

state = before;

while((c = getchar()) != EOF) {

switch(state) {

case before:

if(c == '\n') {

putchar('\n');

} else

if(c != ' ') {

putchar(c);

state = inside;

}

break;

case inside:

switch(c) {

case ' ': state = after; break;

case '\n':

putchar('\n');

state = before;

break;

default: putchar(c);

}

break;

case after:

if(c == '\n') {

putchar('\n');

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

state = before;

}

}

}

return 0;

}

Although the code now looks longer, it has at least one significant advantage: there's only one reading (that is, call to the getchar() function) instruction in the program. Besides that, there's only one loop instead of the four the former versions had.

In this program, the body of the while loop is the automaton step, and the loop itself is the cycle of the automaton's work.

The program implements (models) the work of a finite state machine shown on the picture. The N denotes the end of line character, the S denotes spaces, and the A stands for all the other characters. The automaton follows exactly one arrow on each step depending on the current state and the encountered character. Some state switches are accompanied with printing the character; such arrows are marked with asterisks.

It is not absolutely necessary to divide the code down to separate handlers for each unique state. Moreover, in some cases the very notion of the state can be composed of several variables' values, so that it could be impossible to handle each possible state explicitly. In the discussed program it is possible to reduce the code length noticing that the actions taken in response to the end of line character are the same for all the possible states. The following program is equal to the previous one but is a bit shorter:

#include <stdio.h>

int main(void)

{

enum states {

before, inside, after

} state;

int c;

state = before;

while((c = getchar()) != EOF) {

if(c == '\n') {

putchar('\n');

state = before;

} else

switch(state) {

case before:

if(c != ' ') {

putchar(c);

state = inside;

}

break;

case inside:

if(c == ' ') {

state = after;

} else {

putchar(c);

}

break;

case after:

break;

}

}

return 0;

}

A separate function for the automation step

The most important property of the previous program is that the automaton step code section is clearly localized. It is possible to exhibit this property even better if we provide a separate function for it:

#include <stdio.h>

enum states { before, inside, after };

void step(enum states *state, int c)

{

if(c == '\n') {

putchar('\n');

*state = before;

} else

switch(*state) {

case before:

if(c != ' ') {

putchar(c);

*state = inside;

}

break;

case inside:

if(c == ' ') {

*state = after;

} else {

putchar(c);

}

break;

case after:

break;

}

}

int main(void)

{

int c;

enum states state = before;

while((c = getchar()) != EOF) {

step(&state, c);

}

return 0;

}

This example clearly demonstrates the basic properties of automata-based code:

time periods of automaton step executions may not overlap

the only information passed from the previous step to the next is the explicitly specified automaton state

Explicit state transition table

A finite automaton can be defined by an explicit state transition table. Generally speaking, an automata-based program code can naturally reflect this approach. In the program below there's an array named the_table, which defines the table. The rows of the table stand for three states, while columns reflect the input characters (first for spaces, second for the end of line character, and the last is for all the other characters).

For every possible combination, the table contains the new state number and the flag, which ascertains whether the automaton must print the symbol. In a real life task, this could be more complex; e.g., the table could contain pointers to functions to be called on every possible combination of conditions.

#include <stdio.h>

enum states { before = 0, inside = 1, after = 2 };

struct branch {

unsigned char new_state:2;

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

unsigned char should_putchar:1;

};

struct branch the_table[3][3] = {

/* ' ' '\n' others */

/* before */ { {before,0}, {before,1}, {inside,1} },

/* inside */ { {after, 0}, {before,1}, {inside,1} },

/* after */ { {after, 0}, {before,1}, {after, 0} }

};

void step(enum states *state, int c)

{

int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;

struct branch *b = & the_table[*state][idx2];

*state = (states)(b->new_state);

if(b->should_putchar) putchar(c);

}

int main(void)

{

int c;

enum states state = before;

while((c = getchar()) != EOF)

step(&state, c);

return 0;

}

Automation and Automata

Automata-based programming indeed closely matches the programming needs found in the field of automation.

A production cycle is commonly modelled as:

A sequence of stages stepping according to input data (from captors).

A set of actions performed depending on the current stage.

Various dedicated programming languages allow expressing such a model in more or less sophisticated ways.

Example Program

The example presented above could be expressed according to this view like in the following program. Here pseudo-code uses such conventions:

'set' and 'reset' respectively activate & inactivate a logic variable (here a stage)

':' is assignment, '=' is equality test

SPC : ' '

EOL : '\n'

states : (before, inside, after, end)

setState(c) {

if c=EOF then set end

if before and (c!=SPC and c!=EOL) then set inside

if inside and (c=SPC or c=EOL) then set after

if after and c=EOL then set before

}

doAction(c) {

if inside then write(c)

else if c=EOL then write(c)

}

cycle {

set before

loop {

c : readCharacter

setState(c)

doAction(c)

}

until end

}

The separation of routines expressing cycle progression on one side, and actual action on the other (matching input & output) allows clearer and simpler code.

Automation & Events

In the field of automation, stepping from step to step depends on input data coming from the machine itself. This is represented in the program by reading characters from a text. In reality, those data inform about position, speed, temperature, etc of critical elements of a machine.

Like in GUI programming, changes in the machine state can thus be considered as events causing the passage from a state to another, until the final one is reached. The combination of possible states can generate a wide variety of events, thus defining a more complex production cycle. As a consequence, cycles are usually far to be simple linear sequences. There are commonly parallel branches running together and alternatives selected according to different events, schematically represented below:

s:stage c:condition

s1

|

|-c2

|

s2

|

----------

| |

|-c31 |-c32

| |

s31 s32

| |

|-c41 |-c42

| |

----------

|

s4

Using object-oriented capabilities

If the implementation language supports object-oriented programming, it is reasonable to encapsulate the automaton into an object, thus hiding implementation details from the outer program. for example, the same program in C++ can look like this:

#include <stdio.h>

class StateMachine {

enum states { before = 0, inside = 1, after = 2 } state;

struct branch {

enum states new_state:2;

int should_putchar:1;

};

static struct branch the_table[3][3];

public:

StateMachine() : state(before) {}

void FeedChar(int c) {

int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;

struct branch *b = & the_table[state][idx2];

state = b->new_state;

if(b->should_putchar) putchar(c);

}

};

struct StateMachine::branch StateMachine::the_table[3][3] = {

/* ' ' '\n' others */

/* before */ { {before,0}, {before,1}, {inside,1} },

/* inside */ { {after, 0}, {before,1}, {inside,1} },

/* after */ { {after, 0}, {before,1}, {after, 0} }

};

int main(void)

{

int c;

StateMachine machine;

while((c = getchar()) != EOF)

machine.FeedChar(c);

return 0;

}

Note: To minimize changes not directly related to the subject of the article, the input/output functions from the standard library of C are being used.

Applications

Automata-based programming is widely used in lexical and syntactic analyses.

Besides that, thinking in terms of automata (that is, breaking the execution process down to automaton steps and passing information from step to step through the explicit state) is necessary for event-driven programming as the only alternative to using parallel processes or threads.

The notions of states and state machines are often used in the field of formal specification. For instance, UML-based software architecture development uses state diagrams to specify the behaviour of the program. Also various communication protocols are often specified using the explicit notion of state.

Thinking in terms of automata (steps and states) can also be used to describe semantics of some programming languages. For example, the execution of a program written in the Refallanguage is described as a sequence of steps of a so-called abstract Refal machine; the state of the machine is a view (an arbitrary Refal expression without variables).

Continuations in the Scheme language require thinking in terms of steps and states, although Scheme itself is in no way automata-related (it is recursive). To make it possible the call/ccfeature to work, implementation needs to be able to catch a whole state of the executing program, which is only possible when there's no implicit part in the state. Such a caught state is the very thing called continuation, and it can be considered as the state of a (relatively complicated) automaton. The step of the automaton is deducing the next continuation from the previous one, and the execution process is the cycle of such steps.

Alexander Ollongren in his book[3] explains the so-called Vienna method of programming languages semantics description which is fully based on formal automata.

The STAT system [1] is a good example of using the automata-based approach; this system, besides other features, includes an embedded language called STATL which is purely automata-oriented.

History

Automata-based techniques were used widely in the domains where there are algorithms based on automata theory, such as formal language analyses.

One of the early papers on this is by Johnson et al., 1968.

One of the earliest mentions of automata-based programming as a general technique is found in the paper by Peter Naur, 1963.[5] The author calls the technique Turing machine approach, however no real Turing machine is given in the paper; instead, the technique based on states and steps is described.

Compared against imperative and procedural programming

The notion of state is not exclusive property of automata-based programming.[6] Generally speaking, state (or program state) appears during execution of any computer program, as a combination of all information that can change during the execution. For instance, a state of a traditional imperative program consists of

values of all variables and the information stored within dynamic memory

values stored in registers

stack contents (including local variables' values and return addresses)

current value of the instruction pointer

These can be divided to the explicit part (such as values stored in variables) and the implicit part (return addresses and the instruction pointer).

Having said this, an automata-based program can be considered as a special case of an imperative program, in which implicit part of the state is minimized. The state of the whole program taken at the two distinct moments of entering the step code section can differ in the automaton state only. This simplifies the analysis of the program.

Object-oriented programming relationship

In the theory of object-oriented programming an object is said to have an internal state and is capable of receiving messages, responding to them, sending messages to other objects and changing the internal state during message handling. In more practical terminology, to call an object's method is considered the same as to send a message to the object.

Thus, on the one hand, objects from object-oriented programming can be considered as automata (or models of automata) whose state is the combination of internal fields, and one or more methods are considered to be the step. Such methods must not call each other nor themselves, neither directly nor indirectly, otherwise the object can not be considered to be implemented in an automata-based manner.

On the other hand, it is obvious that object is good for implementing a model of an automaton. When the automata-based approach is used within an object-oriented language, an automaton model is usually implemented by a class, the state is represented with internal (private) fields of the class, and the step is implemented as a method; such a method is usually the only non-constant public method of the class (besides constructors and destructors). Other public methods could query the state but don't change it. All the secondary methods (such as particular state handlers) are usually hidden within the private part of the class.

Event-driven finite state machine

In computation, a finite-state machine (FSM) is event driven if the creator of the FSM intends to think of the machine as consuming events or messages. This is in contrast to the parsing-theory origins of the term finite-state machine where the machine is described as consuming characters or tokens.

Often these machines are implemented as threads or processes communicating with one another as part of a larger application. For example, an individual car in a traffic simulation might be implemented as an event-driven finite-state machine.

This is a common and useful idiom, though not as precisely defined and theoretically grounded as the application of finite state machines to parsing. By abuse of terminology, programmers may refer to code created while thinking of this idiom as a finite state machine even if the space required for the state grows with the size of the input.

Example in C

This code describes the state machine for a British traffic light, which follows the pattern; red -> red+yellow -> green -> yellow -> red.

/********************************************************************/

#include <stdio.h>

/********************************************************************/

typedef enum {

STATE_INIT,

STATE_RED, STATE_RED_AND_YELLOW, STATE_GREEN, STATE_YELLOW,

STATE_FINISHED

} STATES;

#define OPERATION_DONE 1

void state_machine( int *, int );

void state_init( int * );

void state_red( int * );

void state_red_and_yellow( int * );

void state_green( int * );

void state_yellow( int * );

/********************************************************************/

int main(void)

{

int

state = STATE_INIT,

operation;

while( state != STATE_FINISHED )

{

switch( state )

{

case STATE_INIT:

state_init( &operation );

printf("i");

break;

case STATE_RED:

state_red( &operation );

printf("r");

break;

case STATE_RED_AND_YELLOW:

state_red_and_yellow( &operation );

printf("o");

break;

case STATE_GREEN:

state_green( &operation );

printf("g");

break;

case STATE_YELLOW:

state_yellow( &operation );

printf("y");

break;

}

state_machine( &state, operation );

}

}

/********************************************************************/

void state_machine( int *state, int operation )

{

switch( *state )

{

case STATE_INIT:

switch( operation )

{

case OPERATION_DONE:

*state = STATE_RED;

break;

}

break;

case STATE_RED:

switch( operation )

{

case OPERATION_DONE:

*state = STATE_RED_AND_YELLOW;

break;

}

break;

case STATE_RED_AND_YELLOW:

switch( operation )

{

case OPERATION_DONE:

*state = STATE_GREEN;

break;

}

break;

case STATE_GREEN:

switch( operation )

{

case OPERATION_DONE:

*state = STATE_YELLOW;

break;

}

break;

case STATE_YELLOW:

switch( operation )

{

case OPERATION_DONE:

*state = STATE_RED;

break;

}

break;

}

}

/********************************************************************/

void state_init( int *operation )

{

// Power on

*operation = OPERATION_DONE;

}

/********************************************************************/

void state_red( int *operation )

{

// change traffic light to red only

// wait for 30 seconds to let other traffic through

*operation = OPERATION_DONE;

}

/********************************************************************/

void state_red_and_yellow( int *operation )

{

// change traffic light to red and yellow

// wait for 5 seconds to let people get ready

*operation = OPERATION_DONE;

}

/********************************************************************/

void state_green( int *operation )

{

// change traffic light to green only

// then wait for 30 seconds to let some traffic through

*operation = OPERATION_DONE;

}

/********************************************************************/

void state_yellow( int *operation )

{

// change traffic light to yellow only

// then wait for 5 seconds to let traffic know we're going to go red

*operation = OPERATION_DONE;

}

Virtual finite state machine

A virtual finite state machine is a finite-state machine (FSM) defined in a virtual environment. The VFSM concept provides a software specification method to describe the behavior of a control system using assigned names of input control properties and of output actions.

The VFSM method introduces an execution model and facilitates the idea of an executable specification. This technology is mainly used in complex machine control, instrumentation and telecommunication applications.

Control Properties

A variable in the VFSM environment may have one or more values which are relevant for the control - in such a case it is an input variable. Those values are the control properties of this variable. Control properties are not necessarily specific data values but are rather certain states of the variable. For instance, a digital variable could provide three control properties: TRUE, FALSE and UNKNOWN according to its possible boolean values. A numerical (analog) input variable has control properties such as: LOW, HIGH, OK, BAD, UNKNOWN according to its range of desired values. A timer can have its OVER state (time-out occurred) as its most significant control value; other values could be STOPPED, RUNNING etc...

Actions

A variable in the VFSM environment may be activated by actions - in such a case it is an output variable. For instance, a digital output has two actions: True and False. A numerical (analog) output variable has an action: Set. A timer which is both: an input and output variable can be triggered by actions like: Start, Stop or Reset.

Virtual Environment

The virtual environment characterises the environment in which a VFSM operates. It is defined by three sets of names:

input names, represented by the control properties of all available variables

output names, represented by all the available actions on the variables

state names, as defined for each of the states of the FSM.

The input names build virtual conditions to perform state transitions or input actions. The virtual conditions are built using the positive logic algebra. The output names trigger actions (entry actions, exit actions, input actions or transition actions).

Positive Logic Algebra

To build a virtual condition using input names the boolean operations AND and OR are allowed. The NOT operator is not possible because the input names can not be negated, even when they apparently describe boolean values. They simply exist or not.

VFSM Execution Model

A subset of all defined input names, which can exist only in a certain situation, is called virtual input (VI). For instance temperature can be either "too low", "good" or "too high". Although there are three input names defined, only one of them can exist in a real situation. This one builds the VI.

A subset of all defined output names, which can exist only in a certain situation is called virtual output (VO). VO is built by the current action(s) of the VFSM.

The behavior specification is built by a state table which describes all details of a single state of the VFSM.

The VFSM executor is triggered by VI and the current state of the VFSM. In consideration of the behavior specification of the current state, the VO is set.

Figure 2 shows one possible implementation of a VFSM executor. Based on this implementation a typical behavior characteristics must be considered.

State Table

A state table defines all details of the behavior of a state of a VFSM. It consists of three columns: in the first column state names are used, in the second the virtual conditions built out of input names using the positive logic algebra are placed and in the third column the output names appear:

State Name

Condition(s)

Actions(s)

Current state

Entry action

Output name(s)

Exit action

Output name(s)

Virtual condition

Output name(s)

...

...

Next state name

Virtual condition

Output name(s)

Next state name

Virtual condition

Output name(s)

...

...

...

Read the table as following: the first two lines define the entry and exit actions of the current state. The following lines which do not provide the next state represent the input actions. Finally the lines providing the next state represent the state transition conditions and transition actions. All fields are optional. A pure combinatorial VFSM is possible in case only where input actions are used, but no state transitions are defined. The transition action can be replaced by the proper use of other actions.

Automata-Based approach to programming.

Now we are going to look at some of very basic programs made with automata-based approach.

Warm up example: Clock

Clock: implementation

class CLOCK

feature

time: TIME

tick is

begin

time.minute_forth

end

h is

begin

time.set_hour ((time.hour + 1 \\ 24)

end

m is

begin

time.set_minute ((time.minute + 1) \\ 60)

end

end

Alarm Clock

Alarm clock: implementation

class ALARM_CLOCK

…

is_alarm_on: BOOLEAN //FLAGS!

is_in_alarm_time_mode: BOOLEAN //FLAGS!

a is

begin

if is_alarm_on then

if is_in_alarm_time_mode then

is_in_alarm_time_mode := False

else

bell.turn_off

is_alarm_on := False

end

else

is_alarm_on := True

is_in_alarm_time_mode := True

end

end

end

Automata-Based Approach

Theory

What the AP (automata-based programming) is not about

How to use finite automata in specific problems

lexers and parers (push-down automata)

finding substrings

…

How to implement finite automata-Based

multi-choice (switch, inspect, …)

dynamic tables

O-O patterns

Objects with complex behavior

Applicability of AP

Use automata-Based approach to model, design and implement objects with complex behavior

There are plenty of them in control systems and reactive systems...

… and also in applications: network protocols, characters in computer games, dialogs in GUI, etc

Use automata-Based approach only for objects with complex behavior

The Model

Abstract Datatype (ADT) is a model of object with simple behavior

We should come up with a model that will

Capture the notion of complex behavior

Be a special case of ADT

Control vs. Computational states

Control States

Computational States

They are few

They are infinitely (or immensely) many

Each of them has a certain meaning and qualitatively differs from all others

They differ from each other only quantitatively

They define actions that the object performs

They directly define only the result of an action

The hard part

When modelling an object with complex behavior the main object is to

extract the control states

define the level of abstraction of control object

What the AP used to be

Started with logical control (Anatoly Shalyto, 1991), then adopted for software

Non object-oriented

Automata decompositions:

head automaton

other automata can be nested or called

commands and queries of control objects were implemented as standalone functions (usually in C)

What the O-O AP is

The first step is object decompositions

Classes that represent objects with complex behavior are implemented as automated classes

For each automated class a set of control states is devised, then the transitions are introduced with appropriate conditions and actions

Each automated class is represented with state-transition diagram

(Optionally some features can be added to an automated class)

If there is no tool support, automata are implemented using any known pattern

TOOLS

Tool support for AP

Early Tools:

Visio2Switch - generating C code from transition diagrams in Microsoft Visio

MetaAuto - Multi-language code generation

O-O tools:

uniMod ("classes for automata" approach)

under construction...

Ongoing research topics

Verification of automata-Based programs

good for model-checking

combination of model-checking (of the automaton) and proof (of the object checking)

Automatic regeneration of automata-Based

genetic programming

Automatic Generation

For a object with complex behavior

a control object is defined manually

a fitness function is defined on computational states

controller is optimized, so that after k steps fitness function has the highest value

with the naïve approach a size of automaton representation grows exponentially with number input variables

Solutions:

reduced transition tables

decision trees

By ooking at all the above data gathered, it is pretty clear that automata theory can be implemented in software engineering in a number of ways, some of which are shown in this report, but still, that leaves a lot of possibilities to be explored by the student of automata theory...