Monday, October 16, 2017

Reductions between formal languages

Let EQ = {w : number of a's = number of b's }

Let EQO = { anbn : n ∈  N} (so its Equal and in Order)

Typically we do the following:

Prove EQO is not regular by the pumping lemma.

Then to show EQ is not regular you say: If EQ was regular than EQ INTERSECT a*b*= EQO is regular, hence EQ is not regular (I know you can also show EQ with the Pumping Lemma but thats not important now.)

One can view this as a reduction:

A  ≤  B

If one can take B, apply a finite sequence of closure operations (e.g., intersect with a regular lang,
complement, replace all a with aba, replace all a with e (empty string), ) and get A.

If A is not regular and A≤ B then B is not regular.

Note that


Since EQO is not regular (by pumping ) we get EQ and \overline{EQ} are not regular.

Hence we could view the theory of showing things not-reg like the theory of NP completeness
with reductions and such. However, I have never seen a chain of more than length 2.

BUT- consider the following! Instead of using Pumping Lemma we use Comm. Comp. I have
been able to show (and this was well known) that

EQ is not regular by using Comm. Comp:

EQH = { (x,y) : |x|=|y| and number of a's in xy = number of b's in xy }

Comm Complexity of EQH is known to be log n  + \Theta(1). Important- NOT O(1).

If EQ is regular then Alice and Bob have an O(1) protocol: Alice runs x through the DFA and
transmits to Bob the state, then Bob runs y from that state to the end and transmits 1 if ended up in an accept state, 0 if not.

But I was not able to show EQO is not regular using Comm Complexity. SO imagine a bizzaro world where I taught my students the Comm Comp approach but not the Pumping Lemma. Could they prove that EQO is not regular. For one thing, could they prove

EQO ≤ EQ  ?

Or show that this CANNOT be done.

Anyone know?

One could also study the structure of the degrees induced by the equiv classes.
If this has already been done, let me know in the comments.


  1. I think that you can still get an O(1) protocol for EQH with a putative EQO DFA. Let M be such a DFA. Alice counts the number of a's in x. Let this count be m. Now Alice transmits m to Bob using O(1) bits as follows. Alice feeds a^m to her EQO DFA and records the state q that is reached. Alice sends M and q to Bob. Bob starts feeding b's to M starting from state q until M accepts. Bob counts the number of b's it took, which must equal m.

    You can play the same game with Kolmogorov complexity. Li and Vitanyi do this in their book (Jeffrey Shallit also has this approach in his book as well).

  2. Why not just Myhill Nerode directly to show EQ is not regular? It is so direct: the suffix set corresponding to prefix a^i is distinct for each integer i. (For example it contains b^j iff i=j)

  3. It seems that the issue for EQ0 is one of uniformity. CC is a non-uniform model of computation. The natural relationship of CC to DFAs for a language L is for the family of languages
    L intersect Sigma^n. In this case what we get are oblivious read-once BPs (i.e. OBDDs) with the fixed input order. Obviously also one cannot do this with a constant # of states, but another natural non-uniform analogue with the # of states is the width. This is what CC bounds and of course, EQ0 is computable by constant width OBDDs.

    On the other hand, the pumping lemma is a lousy tool that doesn't always work. Why not use the easy direction of the Myhll-Nerode theorem which is both completely intuitive and always works?

  4. Narad- thanks for Comm Comp Proof!

    David and Paul- I've been hearing comments like `Puming lemma is lousy, Myhill or Kolm is much better' for a while now and I am
    trying to put such statements on a rigorous basis by looking at
    all ways to prove things not regular and also include reductions.
    My goal is to get a language that you CAN prove not reg by
    Myhll Nerode or Kolm but CANNOT prove rig by pumping AND closure.
    Pumping is ambigous since there have been many pumping lemmas.
    ANYWAY, I'll be postong on that at a later point.

  5. We can show that EQ0 is not regular using only communication complexity tools in this way: if EQ0 is regular, then we can obtain on O(1) comm protocol for EQ (which is false)

    - Suppose that w = xy; Alice knows x and Bob knows y
    - Suppose that EQ0 is regular so, there is a DFA D that recognizes a^n b^n.
    - We give D to both Alice and Bob.
    - Then Alice calculates n = 2^#a * 3^#b where #a, #b are the number of a and b in her x
    - Alice runs D on a^n and communicates the final state q_i to Bob (in constant time)
    - Now Bob can simulate the behaviour of D starting from state q_i and inputs b,bb,bbb,bbbb,... until he founds b^k that is accepted by D
    - By hypothesis D recognizes EQ0 so k is exactly the n constructed by Alice
    - By the prime number theorem he can recover #a and #b from n
    - Then he can count the #a' #b' that occur in his string y and check that #a + #a' = #b + #b' and can answer correctly to the EQ problem.
    - Clearly the communication between Alice and Bob is costant (it only depends on the fixed D)
    - So we proved that EQ has constant comm complexity which is a contradiction

    A slightly variant is the following: Alice computes n = |#a - #b| and transmits to Bob the state q_i of D after parsing a^n, plus a flag bit which is 1 if #a >= #b. As above, Bob can reconstruct n and check that ( #a >= #b and #b'- #a' = n ) or ( #a < #b and #a' - #b' = n).