Pumppausmenetelmän

Pumppausmenetelmä, often translated as the "pumping method" or "pumping lemma," is a technique used in theoretical computer science to prove that certain languages are not regular. It is a fundamental result in the study of formal languages and automata theory. The core idea behind the pumppausmenetelmä is that if a language is regular, then any sufficiently long string in that language can be "pumped" – meaning a certain substring within it can be repeated zero or more times, and the resulting strings will still be in the language.

The method involves assuming a language is regular and then deriving a contradiction based on this assumption. If a language is regular, there exists a finite automaton that accepts it. The pumppausmenetelmä leverages the pigeonhole principle: if you have more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon. In the context of automata, if a string is longer than the number of states in the automaton, the automaton must revisit at least one state while processing the string. This repeated state signifies a substring that can be "pumped."

The proof proceeds by choosing a specific string of a certain length from the language. The pumppausmenetelmä then states that this string can be decomposed into three parts, where a middle part can be repeated. If, after pumping this middle part (either by repeating it or omitting it), the resulting string is no longer in the language, it contradicts the initial assumption that the language is regular. Therefore, the language cannot be regular. This lemma is a powerful tool for demonstrating the non-regularity of many common languages, such as {a^n b^n | n >= 0}.