Modelling Automata using Graphwiz API

An automata can be implemented in 2 ways.

1. Linked List representation

2. Matrix representation

I implemented a program in JAVA to model an automata(deterministic) in a Matrix structure and represent it graphically as shown to the left. The graphical representation was done by using the Graphviz JAVA api.

Eg. The Automata shown can be represented in matrix form as

	a	b
S0	S3	S1
S1	S2	S1
S2	S3	S1
S3	S0	S3

I have uploaded the code at github, you can download it here

STEPS TO RUN

1. First compile the source files

$ javac FiniteStateMachine.java

$ javac GraphViz.java

2. If both compile  successfully, run

$ java FiniteStateMachine –filename <input_file>

3. By default, if you have evince reader, the gif file should pop up instantly, else edit the code and remove the System command being executed.

4. For more help run

$ java FiniteStateMachine –help

A Transducer for Removing Comments in a file

Automata generated using Graphwiz API

The workflow of stripping comments from a C file from a file can be modelled using the following automata

• Set of States = {S0,S1,S2,S3,S4}
• Set of alphabets(A) = {set of all ascii characters }
• Start State = S0
• End State = S4

This can be converted to a transducer such that whenever the System reaches state 0 , the character is printed on console

I have developed a program for stripping coments based on this automata. The automate on the left was generated using GraphViz. See http://varrunr.wordpress.com/2009/12/10/modelling-automata-using-graphwiz-api/ for more.

You can download it here ( git repository)

Instructions

Run as

$ ./ strip_comment <input_file>

The Documentation was generated with Doxygen and is present in Doc folder

License : GPL

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/

Introduction to Automata

What is an automaton?

An automaton is a recognizer i.e given an input language, it recognizes if a string is a part of that language.

For Eg. English is a language comprising of alphabets ‘a-z’, “beethoven” word is a valid string of the language. At the same time “!a89rr” is an invalid string.

Terms involved in modeling a Finite State machine

Start State – The initial state of the system when no interaction has taken place yet

End/Accepting State – The state(s) that indicates the successful operation of a system (Eg. acceptance of a string)

Transition – An action which triggers the change of the system from one state to another

Mathematical Definition [ Wikipedia ]

A deterministic finite state machine or acceptor deterministic finite state machine is a quintuple (Σ,S,s₀,δ,F), where:

• Σ is the input alphabet (a finite, non-empty set of symbols).
• S is a finite, non-empty set of states.
• s₀ is an initial state, an element of S.
• δ is the state-transition function: (in a nondeterministic finite state machine it would be , ie., δ would return a set of states).
• F is the set of final states, a (possibly empty) subset of S.

Graphical Representation

An automata is represented graphically using a state diagram where each state is represented by a circle and transitions are represented by arrows labeled with the input alphabet causing the transition.

Finite State Machine

Eg. A Finite state Machine which recognizes if the input string has even  number of zeros

There are only 2 possible states for a string “Even number of zeroes” or “Odd number of zeroes”.The initial state, an empty string has even zeroes. Hence, the start state is the end/accepting state. This FSM can be represented by

Even -> 1  =  Even
Odd -> 0= Even
Even -> 0=Odd
Odd -> 1=Odd

Here, ” ->  ” represents a transition  and ” = ” represents the change to the next state. [ Assumed ]

The language accepted by the FSM is {00,100,1100,110000,10000, . . . } . The set of strings generated is infinite