Example 6.2.4.Consider the language L4 = {apbqcrds | either s=0 or p=q=r}. In this language, the pumping lemma does not imply any contradictions for long strings of the form apbqcr (i.e., s= 0), there are three substrings in which pumping yields only strings in L4; also, for long strings of the form apbqcrds,s>0, there is one substring, ds, where pumping yields only strings in L4.
However, if L4 is context-free, then L4 _ a* b* c* d = {apbpcpd | p 0} is also context-free by Theorem 6.1.2. But this is an immediate contradiction to L1 of Example 6.2.1 (i.e., apply the homomorphism h(a) = a, h(b) = b, h(c) = c, h(d) = _ to L4 _ a* b* c* d to get L1).
Previous slide | Next slide | Back to first slide | View graphic version |