Where is my pudding? I was promised pudding.

[maradydd]

As I briefly mentioned in my last post, the students I'm grading for Computational Theory are learning about finite-state automata. You can think of an FSA as a sort of mathematical Choose Your Own Adventure book, where the choices you make correspond to the characters in a string:

You are standing on a road at the edge of a cliff.

• If the first character in the string is an A, you turn around and walk back down the road. Remove the first character and turn to page 23.
• If the first character in the string is a B, you step off the edge of the cliff. Remove the first character and turn to page 57.
• If the first character in the string is a C, it sure is relaxing and peaceful up here. Remove the first character and read this page again.

Each "page" is what we call a state, and just as there are a finite number of pages in a book, there are a finite number of states in a finite state automaton (or "machine", as they're also called). Just like in Choose Your Own Adventure books, there are good endings, which we call accept states. Every other state is a non-accepting state. This could correspond to a bad ending, which we call a "sink state", a non-accepting state that you can't get out of:

Page 57

You have fallen off the cliff and down a deep well.

• If the first character in the string is an A, you try to climb out of the well using only your hands, but you're not strong enough. Remove the first character and read this page again.
• If the first character in the string is a B, you shout for help but nobody hears you. Remove the first character and read this page again.
• If the first character in the string is a C, you lay there and do nothing. Remove the first character and read this page again.

Or it could also correspond to leaving off in the middle of the book -- you haven't found a good ending or a bad ending, you've simply run out of inputs and you're not in an accept state.

(Here is an excellent description of FSAs from the late, lamented Forum 3000, starring Barbie and the Powerpuff Girls.)

Anyway, it should be fairly obvious from the above explanation that any FSA can be run backward: with a little rewriting, you can read the book from end to beginning just as easily as you can from beginning to end. (You'd have to go through the entire book and replace all the "Go to page Y" instructions on page X with "Go to page X" instructions on page Y, but it's certainly do-able.) Since it's true that the reverse of any finite-state automaton is also a finite-state automaton, we say that FSAs are closed under reversal¹. This is a useful property to know about, as sometimes it can be used to make proofs a little bit easier.

So: on one of their assignments, my students had to prove that a certain language (where "language" just means "the set of strings, using a particular alphabet, that is described by a certain set of rules") could be described by an FSA. The textbook hinted that it would be easier to work with the reverse of the language, and just as you might expect, every student who attempted the problem managed to demonstrate succinctly that yes, it was pretty easy to design an FSA which recognized the reverse of the language.

Fewer than half of the students went on to point out "because the regular languages are closed under reversal, the existence of an FSA which describes the reversal of the original language means that it must also be possible to construct an FSA which describes the original language, thus the original language must be regular." Of those who did, approximately half resorted to Proof by Assignment to the Student: "Exercise 1.31 asks us to prove that the reverse of a regular language is also regular, therefore the language must be regular."

I'm giving the ones who committed Proof by Assignment full credit, albeit with a red-ink warning about the wisdom of such proof techniques -- one of these days they're going to run into a trick question and it's going to bite them in the ass. And I'm preparing for a deluge of angry demands for points back from the first half of the class. Even if the problem says you can assume the result of another exercise, that doesn't mean the proof is complete if you don't explain why that result is meaningful, dammit.

¹Actually, we say that the regular languages, which is the class of languages that can be described by an FSA, are closed under reversal. But I didn't want to scare anyone off by getting too technical.

Comments

[aelkiss.livejournal.com]

My friend Asad from Maryland is also teaching FSAs.

With giant vegetables. (http://www.cs.umd.edu/class/fall2005/cmsc330/lecture/s3.pdf)

I don't think he's getting enough sleep.

[maradydd.livejournal.com]

Looks like the actual slides are here (http://www.cs.umd.edu/class/fall2005/cmsc330/lectures/s3.pdf). Yeah, looks like there's more than a little sleep-dep humor in that.

[ernunnos.livejournal.com]

Do they still publish choose-your-own-adventure books? I mean, do students still get that example?

[maradydd.livejournal.com]

Dunno. I'm just the grader; the instructor is one of the department's automated-reasoning professors, so he probably just threw math at them. (Which, you know, usually shouldn't be a problem for grad students.) But I figured my audience would get it.

[grepmaster.livejournal.com]

Dunno about book form, but here's some recent ones =)

http://www.kuro5hin.org/story/2005/8/18/105551/619
http://www.kuro5hin.org/story/2005/9/6/34041/87727

[pturing.livejournal.com]

half resorted to Proof by Assignment to the Student
that cracks me up

[st3v3.livejournal.com]

You should write textbooks. I'd have read your book.

[maradydd.livejournal.com]

The idea of a pop-math book on computational theory amuses me enormously but I have no idea what anyone would do with it.

Of course, I keep on saying that someone needs to write a really good algorithms book for software developers who don't have much formal CS background. I suppose a computational theory book for developers with no formal CS background would be useful too, but a harder sell.

[st3v3.livejournal.com]

Joel Spolsky () is making good money at the minute selling a book on good writing on software (). Why not you? ;)

Most computer books, in fact most books on science, maths, etc tend to be stripped of all humanity in a pathological tribute to school science reports. The humanity and humour is important (because it helps people engage) and distinctive.

I hated much of my physics degree because of the quality (sic) of the writing in the textbooks I had to read. Bad books squeeze enthusiasm out of enthused students.

[q-pheevr.livejournal.com]

Heh. Actually, that sounds like a potentially fun exercise; I'm trying to imagine what sort of regular language would be easier to imagine backwards than forwards. And I've got xfst just sitting here on my computer, waiting to be played with again.... Do you think you could post (a pointer to) the question?

[maradydd.livejournal.com]

Gah, apologies for the late reply. It's from Michael Sipser's Introduction to the Theory of Computation, and has to do with binary addition. Each "character" of the input is a 3x1 matrix, e.g. [0 0 0]^T; the entire string must be valid columnar binary addition, i.e., the top two rows must sum to the third. You end up with one state for "valid transition when you have a carry bit", one for "valid transition when you don't have a carry bit", and a sink state for when an invalid transition has occurred.

The reason it's easier to do backward is because if you reverse it, you're doing little-endian binary addition, which is easier to do left-to-right than big-endian binary addition.

[q-pheevr.livejournal.com]

Ah, cool. Thanks.