This question is about the pumping lemma for context-free languages. Let A = [w

Question

This question is about the pumping lemma for context-free languages. Let A = [w element {a, b, c, d}* | n_a(w) = n_b(w) and n_c(w) = n_d(w)}. (i.e. w has the same number of a's as b's and w has the same number of c's as d's). Suppose you are trying to prove that A is not context-free using the pumping lemma for context-free languages. Your proof starts (correctly) like this: Suppose for a contradiction that A is context-free. Let p be the pumping length given by the pumping lemma for context-free languages. Now you have to choose string s. For each choice of s below, state whether or not this choice of s can be used to finish the proof that A is not context-free. If you answer that s can not be used, you should also briefly and clearly explain why it can not be used. If you answer that s can be used, complete the proof. s = a^p h^p c^p d^p. Can this s be used yes/no. s = a^p c^p b^p d^p. Can this s be used yes/no. s = d^p c^p b^p a^p. Can this s be used yes/no. s = a^p b^P. Can this s be used yes/no.

Explanation / Answer

Answer:

The language L = { w| n ³ 0 }is not a CFL. Suppose L is a CFL, and consider z = apbpcpdp where p is the constant of the pumping lemma for CFL's. Clearly, z is in L. Let z = uvwxy, where u,v,w,x and y are some substrings of z which satisfy conditions (i) - (iii) above. Since |vwx| £ p, substrings v and x together contain at most two different symbols (see the illustration below). Since |vx| £ 1, v and x together have at least one symbol. It follows that z' = uv2wx2y does not have the same number of a's, b's ,c's and d’s. Hence, z' is not in L. This contradicts the lemma. Thus language L is not a CFL.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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