Re: question about "merging" two context-free languages (CFL)

On Aug 12, 9:26 pm, Tony <tonywinslow1...@gmail.com> wrote:
> Suppose we have two context-free languages L1 and L2, and they have
> disjoint alphabet set A1 and A2 (A1 \intersection A2 = \emptyset). Is
> it possible to "merge" L1 and L2 into a new context-free language L
> such that
> 1) the alphabet set A of L is A1 \union A2
> 2) a sequence of letters W (subset of A*) is a valid word in L if
> and only if the longest subsequences W1 and W2 of W satisfy the
> following conditions:
> a) W1 (subset of A1*) is a valid word in L1
> b) W2 (subset of A2*) is a valid word in L2
>
> Example. A1={a, b}, A2={c, d}, L1=a L1 b | \epsilon; L2=c L2 d |
> \epsilon. For the sequence "acbdca", W1 would be "abc", and W2 would
> be "cdc". The sequence "acbd" would be a valid word in the new
> language L since the subsequences W1="ab" and W2="cd" are valid in L1
> and L2, respectively.


I would call this interleaving rather than merging. This looks like a
straightforward application of the pumping lemma for CFLs, which shows
the interleaved language is not, in general, context free. That is,
selected pairs of languages will have context free interleavings, but
many won't.


The Wikipedia article on this subject is fine.
http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages


We can use the PL to show the example you gave is not context free.
With p as given, consider the string a^p c^p b^p d^p .


I'll let you work through the rest in case this is homework. It's
quite similar to the proof in the article.


Cheers.

Return to the comp.compilers page.
Search the comp.compilers archives again.