Early on in LaValle’s “Planning Algorithms” (2006), there is a formulation of finite state machines when the state space X is finite. I’ve been drawing circles with arrows since the beginning with this word counting algorithm in K&R C, and I could never figure out the systematic approach to their solution:

...
if (blank)
state = OUT
else if (OUT)
state = IN
word++
...

Then I was inspired by this book to describe the word-counting as in the explanation in Chapter 2: the state space X is {IN, OUT} and the actions U = {<letter>, <blank>}. So given some input of a letter or blank (newline, tab, or space), we have a function

f(u,x) = u && x = x'

The table of the transition states is then shown to be

f(letter, IN) = IN
f(letter, OUT) = IN
f(blank, IN) = OUT
f(blank, OUT) = OUT

The first conditional is then if (u = blank), which is described by the two latter state transitions: a blank character means we’re out of a word regardless of whether we’re in or out of a word.

The next conditional is distinguishing whether we are transitioning into the first letter of a word from a blank, or if we are transitioning within a word, letter to letter. It is self-evident that, between the first and second transition functions, the conditional “if (state == OUT)” is the only one to let us count words without counting letters within the word.

This is the best explanation I have for the word-counting algorithm. I like it very much.

### Like this:

Like Loading...

*Related*