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.
A pumping length is a threshold beyond which every word in the language has a decomposition satisfying the conclusion of the relevant pumping lemma.
The language is not context-free. Pump a word with both block lengths . Unequal changes to the blocks destroy equality; an equal positive change makes both lengths , which lies strictly between consecutive squares and .

Ancestors (5)

  1. Formal language theory
  2. Foundations of mathematics
  3. Area of mathematics
  4. Mathematics
  5. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

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.