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

Hi,


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.


Thanks,
Tony

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