Pumpamisfunktsiooni

Pumpamisfunktsiooni, also known as the pumping lemma for context-free languages, is a fundamental theorem in the theory of computation. It provides a way to prove that a given language is not context-free. The lemma states that for any context-free language L, there exists a constant p (the pumping length) such that any string s in L with length at least p can be divided into five substrings, s = uvwxy, satisfying specific conditions. These conditions ensure that parts of the string can be "pumped" or repeated, resulting in new strings that must also be in L.

The crucial conditions are: 1. The substring vw must not be empty. 2. The substring vx must not be empty. 3. For any integer n greater than or equal to 0, the string uv^nwx^ny must also belong to L. The core idea is that if a language is context-free, its strings must have a certain recursive structure that allows for this repetition.

To use the pumping lemma to show a language is not context-free, one assumes it is context-free and derives a contradiction. This typically involves choosing a string s in the language that is sufficiently long, and then showing that no matter how s is decomposed into uvwxy according to the lemma's rules, there is always an n (usually n=0 or n=2) for which uv^nwx^ny is not in the language. This contradiction proves the initial assumption was false, and the language is therefore not context-free. It's a powerful tool for distinguishing between context-free and non-context-free languages.