Closure properties of context free languages

I have the following problem:

Languages L1 = {a^n * b^n : n>=0} and L2 = {b^n * a^n : n>=0} are context free languages so they are closed under the L1L2 so L={a^n * b^2n A^n : n>=0} must be context free too because it is generated by a closure property.

I have to prove if this is true or not. So I checked the L language and I don’t think that it is context free then I also saw that L2 is just L1 reversed.

Do I have to check if L1, L2 are deterministic?

回答1:

L1={aⁿbⁿ : n>=0} and L2={bⁿaⁿ : n>=0} are both context free.

Since context-free languages are closed under concatenation, L3=L1L2 is also context-free.

However, L3 is not the same language as L4={aⁿb²ⁿaⁿ : n >= 0}. The string abbbaa is in L3, but not L4.

So is L4 context-free? If so, it must obey the pumping lemma for context-free languages.

Let p be the pumping length of L4. Choose s = a^pb^2pa^p. Then s is in L4, and |s| > p. Therefore, if L4 is context-free, we can write s as uvxyz, with |vxy| <= p, |vy| >= 1, and uvⁿxyⁿz is in L4 for any n >= 0.

Observe the following properties of any nonempty string in L4: The count of a's equals the count of b's. There is exactly one occurrence of the substring 'ab', and exactly one occurrence of the substring 'ba'. The length of the initial string of a's equals the length of the final string of a's.

We can use these observations to constrain the possible choices of v and y in our pumping argument for L4. Neither v nor y can contain the substring 'ab', because then, as v and y are pumped an arbitrary number of times, the output string would contain multiple occurrences of 'ab', and therefore cannot be an element of L4. The same argument applies to the substring 'ba'.

So v must be either empty, all a's, or all b's. The same applies to y.

Furthermore, if v is all a's, then y must consist of the same number of b's; otherwise, the pumped string would contain unequal numbers of a's and b's since v and y are pumped by the same n. Likewise, if v is all b's, then y must be the same number of a's.

But if v is all a's, and y is all b's, the final string of a's is unaffected by pumping v and y, therefore the leading string of a's will no longer match the trailing string of a's. Similarly, if v is all b's and y is all a's, the leading and trailing strings of a's will again have different lengths as v and y are pumped.

v and y cannot both be empty, since that would violate the condition |vy| >= 1 for the CFL pumping lemma. But since we have established that |v| = |y|, it follows that neither v nor y can be empty.

But if v cannot be empty, cannot be all a's, cannot be all b's, and cannot contain the substrings 'ab' or 'ba', then there is no possible choice of uvxyz for which the pumped version of s is still in L4. Therefore L4 is not context-free.

回答2:

I'm not sure that it is -- note that in each of the defintions of L1 and L2, n is scoped within that definition, i.e. they are two different variables. When you combine them you should rename one, and get instead: