Wednesday, August 01, 2018

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.


  1. Related to 2: Suppose that you have a regular expression of length n, and its language contains all words of length at most f(n). For which f(n) can you deduce that the regular expression is universal, that is, its language contains all words? (See Theorem 33 in
    Regular Expressions: New Results and Open Problem

    Another nice question is: what is the state complexity (number of states in the minimal DFA) of the hardest language consisting of binary words of length n? (See A maxmin problem on finite automata.)

  2. The links are pointing to the wrong place.

  3. Both of the links seem to lead to a paper of Alexander Soifer's on the chromatic number of the plane. If that was intentional, I don't see the connection...

    1. It was an accident- that link was in my machines temp memory and I messed up. Fixed now!

  4. Is the known proof of the four color theorem constructive? Do we know how to find a 4-coloring of a planar graph in polynomial time?

    1. The proof is constructive though of course quite long.
      One could take the proof and produce an algorithm in poly time.

  5. Dear Bill, I have a short proof that Planar 3-Colorability is in P, but the margins of this comment are too small to contain the proof..