# 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 $\{a_1, \dots, a_n\}$, and suppose to each letter of the alphabet we associate two non-negative integers $(x_i,y_i)$ 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 '09 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 '09 at 18:08
How's the unambiguity going? –  Ilya Nikokoshev Oct 22 '09 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 '09 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.

-