12
$\begingroup$

I often see students confused/mystified by definitions (and proofs) that allow/consider "useless" cases. A case in point is the definition of a DFA (deterministic finite automaton), which allows states that aren't reachable at all from the starting state; also the proof that any NFA (nondeterministic finite automaton) can be "simulated" by a DFA whose states are subsets of the states of the NFA, again, the vast majority of those states are useless.

When defining DFAs I point out that such superfluous states are OK by the definition, but my students stumble over this anyway. They ask why the definition allows such nonsense. The obvious answer is that not forbidding them makes for a simpler definition, much easier to work with; but it grates their (engineering outlook) sense of parsimony the wrong way.

I'm sure other areas have similar phenomena. What do you do about this?

$\endgroup$
1
  • 3
    $\begingroup$ A car with a useless hood ornament and spinners is still a car. Why would a DFA with useless crap in it not be a DFA? $\endgroup$ Apr 11, 2014 at 6:08

2 Answers 2

17
+50
$\begingroup$

Think of a maze, like the ones you can find in kids' books that you trace through with a pencil. This may sound like a silly question, but what's the definition of a maze? If you ask your students this question, I suspect you'll get some puzzled reactions. I mean, you know a maze when you see one, right? But that very intuition supports the inclusion of "useless cases" in the definition: if you define a maze in such a way as to exclude those setups where not every corridor is reachable from the entrance, then you definitely don't know a maze when you see one—indeed, to verify maze-hood in any given case you'd have to manually check that no corridors are unreachable.

Once you make a good case for not excluding mazes with unreachable sections from the definition, it's not such a large leap to not excluding unreachable states from DFAs.

But now suppose you run a company that designs mazes for theme parks. In other words, these mazes are actually going to be built, and so it'd be pretty silly for some sections to be unreachable. What this demonstrates is: (1) when you're thinking about the abstract definition of a concept, including "useless" cases can make good sense, but (2) when you're thinking about implementation, "useless" cases are often absurd. You might have more luck selling this kind of analogy to a crowd with an "engineering outlook".

$\endgroup$
4
  • 5
    $\begingroup$ Nice analogy!${}$ $\endgroup$
    – dtldarek
    Apr 10, 2014 at 22:42
  • $\begingroup$ Thank you! One can think of a DFA like a maze, where the words read constitute instructions for which paths to choose. On this view the analogy comes naturally, and it happens to illustrate the utility of allowing "useless cases" quite intuitively, I think. $\endgroup$ Apr 11, 2014 at 16:13
  • 2
    $\begingroup$ And the only accepting state is the finish? This is pure bliss, I shall make it my ultimate DFA explanation $\ddot\smile$ It's only the Minotaur that we need now ^^, students of the world, beware! "Solve this maze or die, MUWHAHAHAhahahahaha.a.a.a.a......!" $\endgroup$
    – dtldarek
    Apr 11, 2014 at 17:17
  • 3
    $\begingroup$ Really, really good answer. To add on it: sometimes there is a definition: "x is a foobar when ...", and then a note: "We call x a simple foobar iff ..." or "We call 0 the trivial foobar". This approach could also be used. $\endgroup$
    – Ruben
    Apr 28, 2014 at 0:53
8
$\begingroup$

I think the most useful analogy is standard arithmetic.

I can express the number "4" in many ways. The most obvious is 4, but we also get 2+2, 8/2, 9/3 + 1, 3.99999... and that's not even scratching the surface of the (literally!) infinite ways I can express 4. I challenge the students to explain why arithmetic allows such useless ways to express 4. Why does basic arithmetic allow such nonsense? Why have so many equivalent ways to express such a simple concept as 4? Is it an oversight? Wouldn't it be easier if the only way to express 4 was to just write that one symbol?

I think overall the best parallel to "empty states" in DFAs is multiplication by 1 and addition of 0. 4*1*1*1*1*1... + 0 + 0 + 0 + 0... is probably one of the silliest statements imaginable, and yet it's allowed and a side effect of very useful properties of math. With DFAs it's the same, it can be a side effect of combining DFAs or converting NFAs that states become unreachable and useless. Culling them can be seen as the same thing they did in Algebra I when they simplified an equation for the first time and their teacher made them change 4x/2 + 3 - 4 into 2x - 1. The fact that you can, if you want, define completely superfluous unreachable states for giggles is merely a side effect, just like adding 0 to a number over and over. And just like adding 0 and multiplying by 1, sometimes it can have surprising benefits (see: multiplying by a/a and b/b so you can do the operation 1/a+1/b).

$\endgroup$
1
  • $\begingroup$ And when we have learned, that $4\cdot 1$, why do we even bother to write $4\cdot1$? We could just as well write $4$ in every instance of $4\cdot 1$ and forget about $4\cdot1$ altogether. It's superfluos. No, it's not. It's a different object with the same value. And this very fact is math, so we need to remember it and write it down. $\endgroup$
    – Toscho
    Apr 10, 2014 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.