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 belongsto {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 6'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 cannot be used, you should also briefly and clearly explain why it cannot be used. If you answer that s can be used, complete the proof. (a) s = a^p b^p c^p d^p. Can this s be used? yes/no. (b) s = a^p c^p b^p d^p. Can this s be used? yes/no. (c) s = d^p c^p b^p a^p. Can this s be used? yes/no. (d) s = a^p bp. Can this s be used? yes/no.

Explanation / Answer

If a language L is context-free, then there exists some integer p > 0 (called a "pumping length"[1]) such that every string s in L that has a length of p or more symbols can be written as

s = uvwxy

with substrings u, v, w, x and y, such that

1. |vwx| p,
2. |vx| 1, and
3. uvnwxny is in L for all n 0.

a.
For s = apbpcpdp
let p be 2, therefore s= aabbccdd
let
u = aa
v = b
w = NIL
x = b
y = ccdd
Therefore we can easily prove that uvnwxny is not in L

*We cannot better fit v,w,x since we have a constrain |vwx| p

So a is not Context-free

Same applies for b and c

d. this cannot be used

For s = apbp
let p be 2, therefore s= aabb
let
u = a
v = a
w = NIL
x = b
y = b
Therefore we clearly say that uvnwxny is in L

Therefore apbp might be context free.

I hope you like the explanation provided by me. I left b and c for you, since they are very similar to problem explained in a and I hope that you can solve them yourself with ease. If incase you think I should answer them, please let me know in the comment section, I shall update them at the earliest. Or even you face any problem understanding the logic, please feel free to comment below. I shall be glad to help you with the same.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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