Use the pumping lemma (PL) to prove that the language L = {a^3n#b^5n#c^7n, n gre

Question

Use the pumping lemma (PL) to prove that the language L = {a^3n#b^5n#c^7n, n greaterthanorequalto 0} is not a Context Free (CF). I will consider that, as usual, you are assuming that L is a CF Language (CFL) and thus you are looking for a contradiction based on the conditions of the PL for CFLs. For this, you will consider that m is the pumping length. Then your first step will be to define string s Element L and its constraint. Next, you will consider only the following THREE cases: (i) Can Discuss what can happen if v or y include #. (ii) v is only a's (iii) y is only c's Using all this information you must describe why we reach a contradiction. (Notice that the lengths ratios are |a|:|b|:|c| = ???). Do not to do all the algebra, just give a complete explanation, that should suffice.

Explanation / Answer

while proving by pumping lemma for the string s = uvxyz having condition (|vxy|<=p and |vy|>=1}
|uvnxynz|=|s|+(n1)|vy|=k+(n1)|vy|

So if consider n=k+1, then k+k|vy|=k(1+|vy|)k+k|vy|=k(1+|vy|) is not prime and not belongs to language(L). Now similarly in our case assume that |vy|= k<=p then new strings are ap+k bp-k/2, and the second is bk/2 apcp which clearly seems that these new strings doesn't belong to given language L. So given language is not context-free

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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