Teaching NFAs after DFAs

Question

Michael0x2a's recent question reminded me of a problem I've had teaching about Nondeterministic Finite Automata in the past.

I can get my students quite comfortable following and creating DFAs, but when I show them NFAs, they learn to follow without learning to create. They rarely become comfortable enough with the toolset to make any significant use of it, and when given the chance on any problem, they virtually always restrict themselves to the DFA tools.

How can I make $\epsilon$ transitions and multiple transitions from a single state on the same input character simple and clear enough that students will use the tools with the same fluency and freedom that they can with DFAs?

Answer 1

I don't know how you frame the motivation for NFAs, but something I've found helpful is to put this up front, before introducing them. Something like the following:

• DFAs are the answer to the question "what does computing mean if we only have control and no memory of any kind?" They are essentially flowcharts, an intuition every student understands.

• NFAs are the answer to the "next" question, namely "What can we do if we can execute flowcharts in parallel? Not just a little parallel, but unlimited? Let's give them even more usefulness and suppose that we can extract the right answer if it appears on any thread, instantly. Does this give us any advantage over just one flowchart?"

I've found my students are able to do quite well with this intuition, because they're willing to suspend disbelief regarding the conceptual hurdle that "magic" -- the primary mechanism that defines NFA execution -- cannot be implemented in a real machine.

Then, when they learn that the "magic" of an NFA gives nothing new over a DFA, many of them become quite excited. As they should :-)

---

[EDIT]

To expand on my comment, I've found that I can carry this story throughout the semester, as motivation for every one of the theoretical devices. Philosophically, I think of the automata theory course (at least the first, undergrad version) as centered around the question "what do we mean by the idea of computing?" This in turn divides into two, interlocking questions: what power do we get by adding certain capabilities (in memory, memory access, and concurrency), and what price do we pay for adding them?

I gave what I see as the answers to these questions for finite state automata above.

The next one in the story is the idea of adding memory, without worrying about how much, but with only limited access abilities. Following Sipser and most every other automata textbook, this means memory with only stack access and no limit on concurrency: i.e. NPDAs.

• ASIDE: I first learned this stuff out of Floyd & Beigel's magnificent text, "The Language of Machines"", and they insert an intermediate study between FSAs and NPDAs, namely the capability of memory that can do nothing but count up and down (what they call "counters"). These are strictly more powerful than FSAs (they can solve the balanced parentheses problem), and strictly less powerful than PDAs, either deterministic or not. It's kind of a cool thing to add if you can, because it gives an easier to read yet fully formed notion of the idea of simulation as a mechanism for studying expressiveness. There's also at least one, very practical application that I know of, from language implementation: checking whether a break statement is correctly placed within a loop. About half of my compilers students try to do this with the same technique they use for checking nested comments in the lexer: incrementing a counter when a loop is entered, decrementing it when a loop is exited, and checking that the counter is positive when a break is encountered. If your language supports nested procedure definitions, this won't work, and the nonequivalence of counter and stack machines explains why. This side topic takes time, though, and I've only ever seen it in the Floyd & Beigel text, which is, sadly, long out of print.

Anyway, memory with only end access and unbounded concurrency gives you the class of CFGs, of course. By the time we get through that and the CFG pumping lemmas, I've found my students enjoy the overarching story enough that they appreciate the detour into DPDAs enough to revisit the question "with end access memory, does concurrency give us any advantage?" I've never found time to really study deterministic PDAs (which is okay for me, since I also teach our compilers course :-) ), but students do seem to enjoy learning that the answer to the concurrency question for stacks is that is does make a difference. I even managed once to show how the existence of an inherently ambiguous context free language gives an an alternative proof of the nonequivalence in expressiveness.

Finally, there are Turing machines, of course, which represent the answer to the question of what we get when we combine control flow with unbounded memory and no limit on access. The fact that concurrency once again becomes irrelevant to expressibility is mind blowing to me, and it seems to be to those students that aren't exhausted by the semester, since we're always near the end at this point. If one needs a good story to explain this, it's in the fact that concurrency can always be implemented by threads and sufficiently powerful thread scheduling (which is, essentially, what the proof of simulation of NTA by DTA is).

At this point, I try to include the Universality Theorem, at least a mention of it. More than any other result, I find that this one ties Turing machines to real programming languages in a very effective way, because it guarantees that every "real" programming language can be implemented with the minimum tool set of deterministic control flow and random access memory.

Including the Universality Theorem also has the nice advantage of making the non-computability results more concrete. It's not just that Turing machines can't answer such questions: no real programming language can, and the combination of the Halting Problem and Universality explains why!

Answer 2

This isn't a particularly in-depth answer, but the course I'm currently TA-ing ultimately requires our students to build a regular expression engine (basically, a simplified grep clone).

Basically, they need to:

1. Write a grammar to parse regular expression strings (so, they practice writing CFGs). We of course give them a parser/don't require them to write that part.
2. Convert the resulting tree into NFAs.
3. Minimize the NFAs into DFAs.
4. Execute/match the input by traversing the DFAs.

At that point, the students will (a) realize it's much easier to combine together arbitrary automata if we can liberally spam epsilons all over the place (and that combining DFAs is non-trivial) and so (b) realize they had better understand how NFAs work if they want to get their engine working. (Do or die, yeah?)

A more lightweight lesson idea might be to have students build automata that are very obviously combinations of other automata -- you could have them build each individual subcomponent and ask them to combine them or something to emphasize the usefulness of epsilons. The hope is that they'll start using NFAs more frequently once you emphasize the advantages they have over DFAs.

Other things that seem to help are:

1. Walking through NFA transitions very slowly and carefully on a whiteboard, perhaps using magnets or sticky notes to show which state(s) we're currently "located" on.
2. Showing students how to combine NFAs into DFAs/asking them walk through that algorithm on exercises.

Answer 3

i tend to use "simpler" examples of NFA(like recognice words that contain the sequence "xyz") which can be generated with an easy to see NFA than a DFA so they can see that sometimes NFA can be visually more easy to read...