Finite State Machines & Alternatives

Question

5.00/5 (1 vote)

See more:

I am working on making my own programmer for 8-bit micros and am wondering if their is anything more flexible than the default finite state machine.

I have used FSM's for 16x2 LCD menus and things that generally are set in stone as they are not the easiest to add too some times. I want to be able to easily add new programming algorithms and have full exception handling which I believe may be quite difficult to handle with a simple FSM.

Are their any alternative out there? I have used QM and such tools from [www.state-machine.com^] but they generate quite obscure code and I really don't learn anything when I go that route.

Posted 13-Jul-11 18:24pm

Trevor Johansen

Add a Solution

Comments

Sergey Alexandrovich Kryukov 14-Jul-11 0:27am

Do you need alternative to FSM (this answer cannot be answered without description of your application) or alternative implementation of FSM?
--SA

Trevor Johansen 14-Jul-11 0:40am

I'm open to different versions of FSM's or something completely different.

What I am implementing is a simple enough state chart but their is error checking and redundancy added to each state and if their are errors the system needs to branch into an alternate state set to discover and/or correct the problem.

I have done simple state machines such as user menus where everything is set in stone and their are no issues with things failing. Theirs not a whole lot of info on FSM's so most of what I know I learned from here: http://en.wikipedia.org/wiki/Automata-based_programming

3 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Answer 1 · 2011-07-13T18:33:00

Solution 1

Your arguments in favor if Finite-state machine sound very reasonable. If you don't like the tool you tried to use I would suggest you develop your own framework, perhaps much more compact, less general and closed to your application field. Also, you can exclude code generation and rely on manual coding, but still based on FSM which can add strictness to your design and maintainability to your code.

The concept of FSM is fairly simple to be translated into programming domain in more or less straightforward development process. See http://en.wikipedia.org/wiki/Finite-state_machine[^].

[EDIT] Look at my article Enumeration Types do not Enumerate! Working around .NET and Language Limitations[^]. In this article I provide implementation of Cartesian Square indexed by enumeration (enumeration type represents a set of states of FSM) and describe a FSM built over the Cartesian Square.

—SA

Posted 13-Jul-11 18:33pm

Sergey Alexandrovich Kryukov

Updated 18-Jul-11 18:06pm

v2

Comments

ThatsAlok 14-Jul-11 2:42am

nice link!

Sergey Alexandrovich Kryukov 15-Jul-11 4:31am

Thank you.
--SA

R. Erasmus 15-Jul-11 4:28am

good suggestion

Sergey Alexandrovich Kryukov 15-Jul-11 4:32am

Thank you, R.
--SA

Trevor Johansen 15-Jul-11 11:50am

I was hoping to find a framework to work from as the ones I have written on my own are not robust enough.

Sergey Alexandrovich Kryukov 19-Jul-11 0:04am

This is relatively compact topic, quite possible to create a robust framework. I did not even need to look for something else.
--SA

Sergey Alexandrovich Kryukov 19-Jul-11 0:10am

Please take a look at my article I referenced after [EDIT]. This is the very beginning of the FSM, but the most difficult part is implemented. Ask me questions if this is interesting. This is how I implemented my FSMs. They were universal, driven by meta-data, that's it, only one single implementation of FSM for all concrete machines. The FSMs instances were built on the fly based on meta-data and worked during runtime.
--SA

Trevor Johansen 21-Jul-11 22:53pm

Yea I am a bit confused by the C# syntax in your article. I was going to rework my code to allow adding states and events such as:

AddState ( Curr_State, New_State, Event );
AddEvent ( Event Key_UP );
AddEventFunction ( Event Key_UP, pFunc UP_Function);
AddStateFunction ( State, pFunc State_Function);

However I would store these variables into an array as I am already doing but in order to make it flexible I would need to use vectors to allow dynamic resizing. The vector library is not available on embedded devices. I could skirt around this by having a STATE_TABLE [#States][#Events][pFuncs] macro but that's not a very clean implimentation...

Current code is here: http://pastebin.com/sKkcF0Ui

Trevor Johansen 20-Jul-11 23:32pm

Well that was a great read! Unfortunately I do not use C#...

I quite like the enum as a class that C# has there. I have to maintain an 2d char array for debugging my enums in english in C/C++.

However I do not get quite a bit of the syntax as I have not dealt with templates yet and am unsure how to apply things to C++. I am working on a version of my code but have some kinks still. I will post it on pastebin tomorrow and I will ask my questions.

Thanks!

John R. Shaw · Answer 2 · 2011-07-14T16:27:00

Solution 2

It's on my to-do list. ;)

For educational research I would recommend looking at the lecture notes at Rice University. They are very good at explaining NFAs and DFAs.

You might look at The Boost Statechart Library [^] for ideas.

Posted 14-Jul-11 16:27pm

John R. Shaw

Comments

Trevor Johansen 15-Jul-11 11:51am

Thanks for the heads up on the Boost::FSM. It is open and has all the features I was looking for I believe.

Do they make a Java equivalent of the Boost library do you know?

John R. Shaw 15-Jul-11 12:42pm

Not exactly, but there are lots of java libraries out there - try search for "java statechart".

I found this http://sourceforge.net/projects/state4j/

Trevor Johansen 15-Jul-11 13:20pm

I found this awesome website: http://www.mywikinet.com/mpl/paper/html/example.html and it has a very clean FSM implementation. Should be applicable to C++ and Java, It is much more robust than my FSM and has a better interface.

John R. Shaw 15-Jul-11 13:32pm

Cool! Thanks for the link. It looks like you found what you were looking for.

mav@octaval · Answer 3 · 2011-07-14T21:49:00

Solution 3

I have worked with Qt's State Machine Framework. It is a well built framework and fairly easy to understand, but maybe it is just too much to depend on the full Qt framework for just the State Machine.

Posted 14-Jul-11 21:49pm

mav@octaval

Comments

Trevor Johansen 15-Jul-11 11:52am

I have used it to and its handy for things like quick user menus but I prefer not to rely on a closed source project.

mav@octaval 15-Jul-11 15:44pm

Qt is not closed source. Is open source, with LGPL license.

Finite State Machines & Alternatives

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Finite State Machines & Alternatives

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us