Three trick questions in Formal Lang Theory

There are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, the other I was surprised by 1) If w is a string then SUBSEQ(w) is all strings you can form by replacing some symbols in w with empty string. SUBSEQ(L) is defined in the obv way. I ask the following in class (not on an exam). TRUE or FALSE and WHY and we'll discuss If L is regular then SUBSEQ(L) is regular If L is context free then SUBSEQ(L) is context free If L is decidable then SUBSEQ(L) is decidable If L is c.e. (used to be called r.e.) then SUBSEQ(L) is c.e. The students pretty much get and prove that 1,2, and 4 are TRUE. They all think 3 is false. But is true. For a strange reason If L is ANY lang whatsoever then SUBSEQ(L) is regular. Comes from wqo theory. For more on this see a blog post I did when I was a guest blogger (it shows- the typeface is terrible) here 2) How many states does and NFA  need for { a^n : n \ne 1000} (or similar large numbers). ALL of the students think it takes about 1000 states. They are wrong: here The two above I know people get wrong. The third one surprised me, yet every year the good students get it wrong 3) BILL: We showed that a) 2-colorablility is in P, hence of course planar 2-colorability is in P b) 3-colorability is NP-complete c) 4-colorabilty of Planar graphs is in P SO what about 3-colorability of planar graphs? My very best student said the following last spring: Planar 2-col is in P Planar 4-col is in P so I would guess that Planar 3-col is in P. In prior years others made the same mistake.  My opinion of these students is NOT lowered, but I am surprised they make that guess. Of course, once you KNOW something you have a hard time recovering the state of mind of NOT knowing it, so my being surprised says more about my having drunk the Kool aid then their thought patterns.