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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! But is it also clear that L' is unambiguous? $\endgroup$
    – Qiaochu Yuan
    Commented 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$
    – Richard Dore
    Commented Oct 15, 2009 at 18:08
  • $\begingroup$ How's the unambiguity going? $\endgroup$
    – Ilya Nikokoshev
    Commented 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$
    – Richard Dore
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .