Show that
L2 = {a^n b^m c^max(n,m) d^min(n,m)}
| m, n ≥ 0} ∈/ Context Free
To show that L2 is not a context-free language, we can use the pumping lemma for context-free languages. The pumping lemma states that if a language L is context-free, then there exists a constant p such that any string s in L with |s| ≥ p can be split into five parts, s = uvwxy, satisfying the following conditions:
1. |vwx| ≤ p,
2. |vx| ≥ 1, and
3. ∀i ≥ 0, uv^i wx^i y ∈ L.
Let's assume that L2 is context-free. We will then choose a string s ∈ L2 that satisfies the conditions of the pumping lemma and show that it leads to a contradiction.
Consider the string s = a^p b^p c^p d^p ∈ L2, where p is the pumping constant. According to the pumping lemma, we can split s into five parts, s = uvwxy, such that the conditions of the lemma hold.
Since |vwx| ≤ p, there are three possibilities for the placement of vwx:
1. vwx contains only 'a' or 'b' characters: In this case, pumping up or down would result in an imbalance of the number of 'a' or 'b' characters compared to the number of 'c' characters. Therefore, the resulting string would not belong to L2.
2. vwx contains both 'a' and 'b' characters: In this case, pumping up or down would result in an imbalance of the number of 'a' or 'b' characters compared to the number of 'c' characters. Again, the resulting string would not belong to L2.
3. vwx contains only 'c' or 'd' characters: In this case, pumping up or down would result in an imbalance of the number of 'c' or 'd' characters compared to the number of 'a' and 'b' characters. Once again, the resulting string would not belong to L2.
In all three cases, pumping the string violates the condition that uv^i wx^i y ∈ L2. Thus, our assumption that L2 is context-free is false.
Therefore, we have shown that L2 = {a^n b^m c^max(n,m) d^min(n,m) | m, n ≥ 0} is not a context-free language.