Let ?={1,2,3,4} and C={w E Sigma in w, the number of 1s equals the number of 2s,

Question

Let ?={1,2,3,4} and C={w E Sigma in w, the number of 1s equals the number of 2s, and the number of 3s equals the number of 4s}. show that C is not context free

Explanation / Answer

For a contradiction assume that C is context free. Therefore, C has a pumping length p. Take s = 1p3p2p4p 2 C with jsj > p. Therefore, there exists uvxyz such that (1) uvixyiz 2 C for all i 0, (2) jvyj > 0 and (3) jvxyj p. We will now proceed by cases to show that no matter the values of uvxyz we choose, we will reach a contradiction. Case 1: vxy contains a 1. Then uv2xy2z =2 C, since it will no longer have the same number of 1s and 2s. This is because from (3), vxy cannot contain any 2s. Case 2: vxy contains a 2. Then uv2xy2z =2 C, since it will no longer have the same number of 1s and 2s. This is because from (3), vxy cannot contain any 1s. Case 1: vxy contains a 3. Then uv2xy2z =2 C, since it will no longer have the same number of 3s and 4s. This is because from (3), vxy cannot contain any 4s. Case 1: vxy contains a 4. Then uv2xy2z =2 C, since it will no longer have the same number of 3s and 4s. This is because from (3), vxy cannot contain any 3s. From (2) we see that these are all the cases. In each one we contradict (1). Therefore, C is not context free.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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