question about "merging" two context-free languages (CFL)
in [Theory]
|
Prev: P, NP, NP Complete, Intractable in layman terms?
Next: question about "merging" two context-free languages (CFL)
From: Dacong Yan on 12 Aug 2010 21:29 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 |