For some , every sufficiently long in a context-free language has with , , and in the language for all .
This formal language is not a context-free language. For pumping length , use . A pumpable window of length at most cannot meet both outer blocks. If pumping adds copies of , then and . Preserving the product constraint would require , impossible both when and when it is positive. This contradicts the pumping lemma for context-free languages.
The language is not context-free. For a proposed pumping length, start with a larger prime . Pumping unequal numbers of zeros and ones breaks equality; if the positive changes are equal to , pumping with exponent gives the composite common block length .
The pumping lemma for context-free languages rules out a formal language when two pumpable pieces cannot preserve all three linked block counts. For example, let . If were a context-free language with pumping length , the word would have a decomposition with and .
The window cannot contain both an and a , because the intervening block alone has length . Pumping down to therefore leaves at least one outer block at length , while deleting at least one symbol from another block. The remaining block counts cannot all be equal, so , contrary to the pumping lemma for context-free languages. This argument uses a necessary condition for context-free languages; satisfying a pumping condition would not itself prove that a formal language is a context-free language.
Articles by others on the same topic
The Pumping Lemma for context-free languages is a property that all context-free languages (CFLs) must satisfy. It provides a way to prove that certain languages are not context-free by demonstrating that they do not conform to the lemma's conditions.