How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ?

How are these Context-Free Pumping Lemma Approaches differ? Maybe this might help understand pumping lemma better

$(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{j}d^{i} \mid i, j \geq 0$}

I understand we use contradiction with these conditions

$|vwx| \leq p$
$|vx| \geq 1$
for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

Iancovici

Posted 2013-03-22T11:01:32.487

Reputation: 635

Welcome to [cs.SE]! Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have litte to work with. Let me direct you towards our reference questions which cover your problem in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Your question may then be reopened. Good luck!

– Raphael – 2013-03-22T14:00:22.133

So, what is your question? You've listed some languages, and you mention the context-free pumping lemma. You seem to be interested in applying that lemma to each language. So, have you tried to do it? What part of the proof gave you trouble? – Gilles 'SO- stop being evil' – 2013-03-22T19:46:35.453

Dear Moderators. It is clear that not each of the three languages here is non-context-free. After that hint the user has correctly identified these. For the pumping lemma I have directed user to a standard answer that deals with that topic. It seems that the question has been answered to the satisfraction of the user. – Hendrik Jan – 2013-03-22T22:20:26.983

1It seems like like only the second doesn't have a grammar, and the rest do. Is that right? a. $S \rightarrow aSd\mid A$ ; $A \rightarrow bSc \mid \epsilon$

and c. $S \rightarrow AB $ ; $A \rightarrow aAb \mid \epsilon$ ; $B \rightarrow cBd \mid \epsilon$ – Iancovici – 2013-03-22T11:37:45.833

@echadromani Your observation is correct (and so are the grammars you give) – Hendrik Jan – 2013-03-22T13:29:28.717

How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ?

Answers