## Is the “diagonal” of a regular language always context-free?

That's very poor wording, so let me be more precise. Suppose L is an unambiguous regular language on an alphabet {a1, ... an}, and suppose to each letter of the alphabet we associate two non-negative integers (xi, yi) which are not both zero. Associate to a word w the sum of the pairs of integers associated to each of its letters; call this M(w) = (x, y).

Let L' be the language consisting of all words such that M(w) = (x, x) for some x. Is L' an unambiguous context-free language?

-

Yes.

There's no reason to have two nonnegative integers, you can just use one integer xi-yi. Then you care about whether the sum is zero. The language K of things which sum to zero is recognized by a push down automata -- the stack is always just a bunch of +1 tokens or -1 tokens corresponding to the current sum. Since K is recognized by a push down automata, it is context free.

The language you are interested in is L intersect K. The intersection of a regular language and a context free language is always context free.

-
 Thanks! But is it also clear that L' is unambiguous? – Qiaochu Yuan Oct 15 2009 at 5:56 Sorry, I missed the unambiguous part. (Which makes it a more interesting problem.) I think I can prove the answer is still yes, but I need to check some details. If it works out I will post it later today. – Richard Dore Oct 15 2009 at 18:08 How's the unambiguity going? – Ilya Nikokoshev Oct 22 2009 at 17:57 I was trying to unwind the DPDA somehow to get an unambiguous language. But it gets messy. I'm glad to see from Diego's comment this can just be done more generally. – Richard Dore Oct 22 2009 at 21:30

It's unnecessary to assume that L is unambiguous: a regular language always is, because there exists a DFA that accepts it.

Following Richard's notation, it is easy to construct a DPDA for K, so it is a DCF language (a subset of the unambiguous CFLs). Looking at the construction that proves that the intersection of a CFL and a regular language is CF, we can see that the same property is also preserved for DCFLs, because no step in the construction would produce non-determinism if it isn't already.

So we can conclude that L'=K∩L is a DCFL, and in particular unambiguous.

-