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

Problem Detail: 

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

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

Asked By : Iancovici

Answered By : Hendrik Jan

Not all three languages are in fact non-context-free. Try to spot those that have a CF-grammar, and apply pumping to the remaining example(s). That is the difference you mean, I presume?

(added) The grammars you give in a comment seem correct to me. General hints for applying the pumping lemma are given in various answers at this site, see in particular How to prove that a language is not context-free?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10694

3.2K people like this

 Download Related Notes/Documents