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

Gene <>
Sat, 14 Aug 2010 11:30:57 -0700 (PDT)

          From comp.compilers

Related articles
question about "merging" two context-free languages (CFL) (Tony) (2010-08-12)
Re: question about "merging" two context-free languages (CFL) (Gene) (2010-08-14)
| List of all articles for this month |

From: Gene <>
Newsgroups: comp.compilers,comp.theory
Date: Sat, 14 Aug 2010 11:30:57 -0700 (PDT)
Organization: Compilers Central
References: 10-08-007
Keywords: parse
Posted-Date: 14 Aug 2010 23:04:00 EDT

On Aug 12, 9:26 pm, Tony <> 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.

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.


Post a followup to this message

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