Let B be the language of all palindromes over {0,1} containing an equal number o

Question

Explanation / Answer

Ans. Assume B is context-free and let p be the pumping length. Consider a string s = 0p 1p 1p 0p ? B. Let s = uvxyz and the split satis?es all requirements of the pumping lemma. We have four cases to deal with: case 1: vxy contains only 0’s case 2: vxy contains only 1’s case 3: vxy is the form 0m 1n case 4: vxy is the form 1n 0m . For case 1, it contains two subcases. For the ?rst subcase that u = 0k1 , vxy = 0k2 and z = 0p-k1 -k2 1p 1p 0p . Choose any i > 1 and uv i xy i z ? B; for the second / subcase that u = 0p 1p 1p 0k1 , vxy = 0k2 and z = 0p-k1 -k2 , the proof is similar. For case 2, it must be the form u = 0p 1k1 , vxy = 1p-k1 1p-k2 and z = 1k2 0p . The case can be proved by similar argument as case 1. For case 3, let u = 0k , vxy = 0p-k 1l and z = 1p-l 0p . This case also contains two subcases. For the ?rst subcase, if v contains only 0’s, y contains only 1’s and one of them could be e. Under this subcase, let i = 2, uv 2 xy 2 z ? B whether / |v| = |y| or not; for the second subcase, it means that v or x straddles the boundary of 0’s and 1’s. If v = 0p-k 1t1 , and i = 2, s = uv 2 xy 2 z ? B; otherwise / y = 0t2 1l , s = uv 2 xy 2 z ? B. / For case 4, the proof is similar to that in case 3. One of these four cases must occur. Because all cases result in a contradic- tion, a contradiction is unavoidable. So the assumption that B is a CFL must be false. Thus we have proved that B is not a CFL.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.