Definitions/proofs that allow "useless" cases?

Question

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?

Answer 1

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".

Answer 2

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).