Nyarly's Journal: ToC: Lesson 3 State Machines

(There I was thinking that no one was interested. Thanks for the emails. Next lesson begins immediately.)

Next step. We've got the idea of a language being a subset of all the possible strings given a specific alphabet. All right. And we can neatly describe a language as being all the strings accepted by a regular expression, which is a really nifty shorthand, but for real fun we need to move on to state machines.

There's two ways to explain state machines. One is geared for the mathematically inclined - a state machine is a 4-tuple that consists of a directed graph, a set of subsets of an alphabet that are associated with the edges in the graph, a single node from the graph, and a subset of nodes; the single node is the beginning state and the subset are the ending states. The other way is figurative, and I'm really thinking a diagram would be great right now. Here's a link: a state machine.

I'm not perfectly thrilled with this example because it's not using the notation that I like, and it implies that each edge can only be used for one symbol, but I'll deal. Just keep in mind that you'll sometimes see different ways of marking the begin and end states, and that you can use a comma seperated list of symbols on an edge (one of the arrows between circles) and it's okay.

Okay, great, that's a state machine. Here's what it's for. First stop: instead of nodes, or circles or arrows, a state machine consists of states (circles or nodes) and edges (arrows). Basically, any string "drives" a state machine. If the last symbol in a string leaves the machine in a end state, then it's accepted. If the string runs out when we're not in a end state, or includes a wrong symbol, then it's not accepted. Simple.

But what do I mean by "drives?" Basically, follow these steps:

1. Start in the beginning state. Put your finger on it if you want to.
2. Start at the beginning of the string. Put your other finger on it if you want.
3. Look at the current symbol in the string, and compare it to the symbols on the edges leading from your current state.
   • If the symbol is there, update your current state to the node on the other end of the edge.
   • If it's not there, stop. The string is notaccepted.
4. Move to the next symbol in the string. If there aren't any more, you're done. Now:
   • If the current state is an end state, the string is accepted.
   • If the current state isn't an end state, the string is not accepted.
5. Repeat from step 3.

What say you to an example? Try using the sample state machine (remember the link?) to check if the following strings are in it's language:

1. VXXXVS
2. TPTXX
3. VXXXVPXVGPS
4. TTXXXPS
5. TPPPPPTXXXXXVPS

Bonus question: how many strings does our sample machine accept?

The other thing to notice is that with not too much ingenuity, we can represent a regex with a state machine and vice versa. Just for fun, compare the sample machine to ((TP*T)|(V)(X*VP?)?)|(VV)S. Or try drawing a machine to accept 'abb*cow(end)?'. You can kind of see how regex and state machines are pretty equivalent, eh? Good.

Okay, state machines handled. Strictly speaking we could have a state machine with an infinite number of states, but there are many different reasons not to like the idea. Besides, they're cool enough with a finite number of states, which is where we get Finite State Machines, or FSM. By loosening the definitions or how an FSM works, we can describe all sorts of useful stuff, like networking stacks and burglar alarms.

If I were you, though, I wouldn't be satisfied with burglar alarms as justification for all this malarky about languages that aren't C# or Scheme anything useful. In fact, I'd probably be crying "What in the name of Alan Turing is all this garbage good for?"

Which is a very good question. See you next lesson.