# Language to describe Finite State Machine

I'm doing a lot of code analysis using lexer and finite state machine. For time being I'm using table to describe FSM:

``````| token | current state | target state |
+-------+---------------+--------------+
| .     | start         | dot          |
| trace | dot           | method       |
| (     | method        | detected     |
``````

Using this table and implicit `start` state FSM is created:

Lexer is used to generate a stream of tokens and token used as trigger for state transition. In case transition from current state is impossible - FSM is set to `start` state.

Using table to describe FSM is alright for fairly small number of states, but it gets complicated fairly quickly. Google search suggested very few interesting results:

So the question is there standard or de facto language to describe finite state machines?

• using state-transition tables is the regular way of doing it. However, if I remember correctly, then Type-3-Grammatics are recognized by finite state machines, so I think you could use those as description language (en.wikipedia.org/wiki/Regular_grammar) Commented Aug 26, 2016 at 10:17
• Why don't you use a parser generator? Commented Aug 26, 2016 at 16:33
• Thats a good question, I'll look into parser generator as well. Commented Aug 30, 2016 at 8:57
• So you are building this FSM in order to parse code and analyze it, correct? So you are building the in memory representation of the FSM, right? If I've got that right, are you handling the parsing the table? Commented Aug 30, 2016 at 16:18
• One of the simplest languages which can encode the information set of a state-transition table, along with parseable predicates for labelled (or not) transitions, is probably those good old S-expressions: en.wikipedia.org/wiki/S-expression Commented Aug 31, 2016 at 5:41

Since finite state machines are a basically subset of (labelled) directed graphs, what about something like DOT. It was just the first thing that popped up on a Google "directed graph language". I've never used it.

• DOT and graphviz is for making diagrams, it's not useful for code analysis. Commented Aug 26, 2016 at 16:38
• @whatsisname My understanding is that the question is about how to describe the finite state machine. DOT does that. Are you saying that the DOT representation can only be used to for making diagrams? If so, that seems to be obviously not true. Commented Aug 26, 2016 at 16:46
• I interpreted his question as he needs to do some analysis on code, but not necessarily report his findings to someone else. Graphviz might be useful for reporting the findings, but not the actual analysis. We often use "describe" as a synonym for "characterize" in this context. Commented Aug 26, 2016 at 19:15
• Additionally, if he is going to use DOT for whatever he's doing, now he has two problems. Commented Aug 26, 2016 at 19:15
• @whatsisname If you look at around the middle of the page from my link, there are 10 different tools listed that can supposedly use this format. All I see in the question is a request for a different way to format the FMS as text. The question is unclear so maybe you are right and it's not helpful. I'd need clarification on the question to be sure. Commented Aug 29, 2016 at 13:26

Most of what has been standardised goes beyond simple finite state machines.

If you like XML, there's State Chart XML and UML's XMI for UML state charts, both of which are a superset of finite state machine.

There's also Matlab's stateflow, but I'm not sure if there's a text based language behind them or a proprietary format.

Trawling my links from a few years back, Microsoft's Abstract state machine language has an implementation XASM ( I've not used it ) and a paper 'SML-a high level language for the design and verification of finite state machines'. If you want something more of domain language within a programming languages, there's this question Is there a programming language with built-in state machine construct?