MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted


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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.