Welcome to MathOverflow

Question

2

That's very poor wording, so let me be more precise. Suppose L is an unambiguous regular language on an alphabet {a₁, ... 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?

flag	asked Oct 15 2009 at 4:44 Qiaochu Yuan 38.2k●5●116●301

Richard Dore · Accepted Answer · 2009-10-15 05:11:36Z UTC

3

Yes.

There's no reason to have two nonnegative integers, you can just use one integer x_i-y_i. 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.

edited Oct 15 2009 at 5:11

answered Oct 15 2009 at 5:05

Richard Dore
2,395●2●16●29

	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

Diego de Estrada · Answer 2 · 2009-10-22 16:22:31Z UTC

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.

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.