3
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks! But is it also clear that L' is unambiguous? $\endgroup$ Oct 15, 2009 at 5:56
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2009 at 18:08
  • $\begingroup$ How's the unambiguity going? $\endgroup$ Oct 22, 2009 at 17:57
  • $\begingroup$ 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. $\endgroup$ Oct 22, 2009 at 21:30
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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