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 (0)

There are currently no matching articles.