State Machine Tool in Silverlight
I have made a “SM Tool” during the last summer. It is a program, which allows you to work and play with Finite-state machines. It was my credit work on Advanced programming for .NET.
You can find it here SM Tool. You must have installed Silverlight plugin in your browser.
SM Tool is a program, which allows users to create and edit Finite State Machines. It’s goal is to help users better understand some parts of Automata theory, to become familiar with state machines and to try out some algorithms.
Properties of State Machines
It SM Tool, there are 2 types of state machines: Deterministic (D) and Nondeterministic (ND).
Each type has these standard properties
- name – a name of current machine
- alphabet – only ASCII characters can be in alphabet
- states – a list of states, each state has it’s related transition function
- final states – numbers of states, which should be final
Deterministic machine has
- initial state – a number of an initial states
- each state has one transition number for each character
ND machine has
- initial states – a list of numbers of states
- each state has a list of transitions for each character
In both D and ND, states can have 3 optional attributes, Name, x and y, which serve for drawing the machine.
The main storage for user’s state machines are XML files.
<machines> <dmachine name="My D machine"> ... </dmachine> <nmachine name="My ND machine"> ... </nmachine> </machines>
Example of D machine
<dmachine name="Language a+"> <alphabet>a b </alphabet> <begins>1</begins> <ends>2 </ends> <states> <state name="Start" x="107" y="151">2 3 </state> <state name="Found" x="256" y="98">2 3 </state> <state name="Cycle" x="259" y="263">3 3 </state> </states> </dmachine>
Example of ND machine
<nmachine name="Nedeterm."> <alphabet>a b </alphabet> <begins>1 2 </begins> <ends>1 3 </ends> <states> <state name="1" x="85" y="334">1,2 4 </state> <state name="2" x="344" y="169">4 3 </state> <state name="3" x="93" y="46">1 4 </state> <state name="4" x="162" y="183">1,4 4 </state> </states> </nmachine>
Each <dmachine> can be retyped into <ndmachine>, but ND machine has some extra properties, which D has not. In ND:
- <begins> can contain multiple numbers
- <state> can have for each character (separated by space) multiple transition states (separated by comma)
State parameters “name”, “x” and “y” are optional and don’t have to be listed.
The SM Tool user interface consists of 3 parts
- Stack of machines at left
- Command panel at the bottom
- Main panel
All state machines are lisdted in left panel. At the beginning, sample machines are loaded into program. Here you can:
- Delete machine by clicking on “X” button.
- Edit current machine
- Edit the graphic appearance of a machine
- Create a new machine
- Load other machines from XML
- Save all machines into XML
Editing a machine
After clicking on “Edit” button, editing window is opened. Here you can edit all the parameters of a machine. You can add new states, change initial / final states, change an alphabet etc.
After editing, you can try to save your machine as D or ND, or you can Cancel your changes.
Editing a graph
After clicking on “Graph” button, graphing window is opened. Here you can edit a visual appearance of a machine by setting positions of it’s states. You can change positions by dragging the states with a mouse.
Magic button can be used to automatically adjust the graph. It uses physics simulation (attraction / repulsion algorithm) to find the optimal positions for the states. Warning: it is not useful in all cases, so be careful when using it!When you have finished your editation, you can save it or cancel it.
There is a command panel at the bottom of SM Tool. Insert your command into “Intput” field, then click “Go!” button. Available commands:
- copy k – makes a copy of a machine
- reduce k – reduces a machine into it’s “minimal” reduced form
- determ k – converts ND machine into D machine
“k” is machine’s number in the machines list (on the left). Every newly created machine is added at the top of the list. Then you can view it, edit it or delete it.