Question

2. (10 points) Use the pumping lemma for context free grammars to show the following languages are not context-free.
(a) (5 points)
.
(b) (5 points)
L = {w ◦ Reverse(w) ◦ w | w ∈ {0,1}∗}.

I free grammar for this language L. lemma for context free grammars to show t 1. {OʻPOT<)} L = {w • Reverse(w) w we {0,1}*). DA+hattha follaurino lano

Answer 1

If L were context free, then the pumping lemma should hold. Let z = 0^n 1^{n+1} 0^{n+2}. Given this string and knowing that |z| >= n, we want to define z as uvwxy such that |vwx| <= n, |vx| >= 1. Because |vwx| <= n, there are five possible descriptions of uvwxy: 1. vwx is 0^p for some p<=n, p>=1 2. vwx is 0^p 1^q for some p+q<=n, p+q>=1 3. vwx is 1^p for some p<=n, p>=1 4. vwx is 1^p 0^q for some p+q<=n, p+q>=1 5. vwx is 1^q for some i<=n, i>=1 Note that because |vwx| <= n, vwx cannot contain "0"s. For all of these cases, u v^i w x^i y, i>=0, should be in the language. In case 1, if i=3 we will be adding an 00 to the string, making the number of "0"s n+2 and thus the string is not in the language since the number of 0's is more than the number of 1's, i.e., i > j. 

This means that our assumption was wrong and L is not context free.

NOTE: As per HOMEWORKLIB POLICY I am allowed to answer specific number of questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.