Intersection of automata, and why should you care

Regular readers of this blog (both of them…) know that I have a propensity to make actual use of basic theory, and this has served me really well, all these years, primarily because most others don’t. After all, you know the saying that, in theory, theory and practice do not differ but, in practice, they do. Well, the point is to know when they do and when they don’t. And I’ll stop being cryptic now and tell you that the theory concerning this post is automata theory.

I first used statemachines as an explicit programming abstraction around 2001, in a system that handled SMS dialogs with mobile subscribers (I say explicit, because, at some level, any system mutating state, transitions between states of an implicitly defined statemachine). Statemachines are a very concise way to model such things, as they have a memory of exactly unit length. You collapse all past history on this one thing, which is the current state. You gain an impoverished but surprisingly sufficient language (a regular grammar) to handle events.

And then, reality intervenes, and things become messy. There are Moore machines, and Mealy machines and statechart diagrams, the UML standard way to model statemachines for software, that encompass both. Because we don’t just care to recognize a series of events, what we want is to act on them, so we need a finite state transducer. I’ll use the Mealy viewpoint (actions linked to transitions) in the sequel. Let me relate some thoughts of mine about how to think about transition guards.

We start with a sample transition, as in the diagram.

Statemachine transition with guard

Statemachine transition with guard

You move from State 1 to State 2 when Event 1 arrives, but only when guard() is true. Supposedly, guard() is a boolean expression on the World. It can be either true or false, or else we wouldn’t bother asking, and, supposedly, the World sometimes makes it true and sometimes makes it false. I’ll come back to this in a moment. Suppose, now, that, the World being in a state of making guard() true, is represented as a real state, in another statemachine.

Two automata

Two automata

We now have two statemachines, and I’ve taken the liberty to make the World statemachine understand the Event 1 transition as well (not doing anything important with it). The reason I did that, was to pave the way to forming the intersection of the two statemachines.

Product of automata

Product of automata

What just happened, is that we got rid of the guard, at the cost of having to maintain a second statemachine, the World one. In a system where transitions in the World statemachine are also done from within the system itself, this amounts to optimizing the guard calculations to happen only when the World changes, and memoizing the result. The main statemachine should also understand (and similarly ignore) the events of the World one, so that the intersection statemachine is well-defined.

Don’t get all worked up about the complexity of all that, because you don’t have to physically form the intersection. All that “understanding” and “ignoring”, you should read it as happening implicitly. In plain words, you can just define transitions in the second machine in response to World-changing events, and transitions in the first machine in response to the main events, but the latter transitions will be defined on product-states, formed from one state from each statemachine.

I’ll be spending more time on statemachines in the immediate future, so you may expect more stuff coming from that direction. I can’t let you in on job-related things, but I’ll be happy to share basic knowledge.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s