Pumping-Lemma
The pumping lemma and Pumplemma (also called loop set ) describes in theoretical computer science a property of certain classes of formal languages . In many cases it can be demonstrated on the basis of the lemma that a formal language is not regular or not context-free.
It has its name from the term inflate the lemma to pump to German. It derives from the fact that parts of words from languages of certain classes multiplied ( inflated ) may be such that the resulting words are also in the language.
First distinction is made between the pumping lemma for regular languages and that for context-free languages. In the literature, pumping lemmas are still to be found for extensions of context-free languages. However, more powerful language classes in the Chomsky hierarchy as the context-sensitive languages and the growing context-sensitive languages do not allow Pumpinglemma.
Alternatively, the lemma and its variants is also called uvw theorem uvwxy theorem, Schleifenlemma, Iterationslemma or Lemma of Bar - Hillel.
- 2.1 Pumping lemma for context-free languages
- 2.2 proof
- 2.3 Example
- 2.4 A non - context-free language that satisfies the pumping lemma
Regular Languages
Pumping lemma for regular languages
For every regular language there is a natural number, so that: Each word in with a minimum length has a decomposition with the following three properties:
In addition to the regular languages , there are also non- regular languages that meet this lemma. A necessary and sufficient condition for regular languages provide the Myhill - Nerode or Jaffe's pumping lemma.
The pumping lemma contains several changes between universal and existential quantification. This can be well understood from the following formal formulation of the lemma. It denotes the set of all regular languages .
Evidence
The validity of the lemma is based on that there is any regular language of a deterministic finite automaton that accepts the language. Over a finite alphabet contains a regular language with infinitely many words and those words that contain more characters than the machine has states. To accept such words, the machine must therefore contain a cycle, which can then be run through in any frequency. The letters, which is read during the passage through the cycle, so it can accordingly as often occur in words of the language.
The following proof is the minimum length from the lemma is equal to the number of states of the machine, and shows that due to the existence of a cycle of each word has the required separation with the minimum length.
Let be a regular language. Is finite, then there is a word with maximum length. Be, then, for all the wrong premise and the implication so true.
Is infinite, then be a deterministic finite automaton that accepts, and is the number of states of the automaton. Since is regular, such a machine exists always.
Now let any word of at least characters, ie. Denote by the state sequence, the beginning goes through when reading from the start state. In particular. As is, must be accepted by, that is, must be a final state. Since the machine has just states, a state repetition must occur at the latest after reading of characters. That means there are with. The machine goes through a cycle so on.
, The part of which is read as it passes through the cycle. Furthermore, the part of which is read as it passes through the front lying state sequence, and is the part of which is read as it passes through the underlying state sequence. With this choice applies.
With this choice of, and the information is valid from the pumping lemma:
Example
If the language is regular?
Suppose is a regular language. Then there according to pumping lemma is a number, so that all words can be decomposed as described.
Consider now specifically the word.
Under Condition 2 is not empty, consists, according to condition 1 and thus only of s ( as and ). By Condition 3, the word would have to be in. But this is obviously wrong, because this word has more s than s, since greater than 0 Because of these assumptions may not be regular.
A non - regular language that satisfies the pumping lemma
The language is not regular. However, satisfies the properties of the pumping lemma, since every word can be decomposed such that for all. This can simply be chosen as the first letter. This is either the number of leading s is arbitrary. Or is he or without leading but s is the number of leading s or arbitrarily.
Jaffe pumping lemma
Jeffrey Jaffe has developed a generalized pumping lemma, which is equivalent to the definition of the regular languages. So it is a necessary and sufficient condition to prove the regularity of a language.
The language is regular if and only if there exists a constant, so that there was a division there for all with, such that for all and suffixes:
Context-free languages
Pumping lemma for context-free languages
For each context-free language, there is a natural number, so that: Each word in with a minimum length has a decomposition with the following three properties:
In addition to the context-free languages are not context-free languages that meet this pumping lemma. The converse of the lemma therefore does not apply in general. A generalization of the pumping lemma for context-free languages is Ogden's Lemma.
Evidence
Given a context-free grammar G in Chomsky normal form with variables for which is that it just describes the desired language. Let now given a word of this language in which it applies.
Now consider a derivation tree T for h with height because our language was specified in CNF, T has the form of a binary tree. It follows for the height of T. There is thus a path T from the root to a leaf, for which applies that it has length. Thus, there are two nodes on that path, which represent the same variables for G.
Looking at the sub-tree, which is spanned by, so its leaves form the substring. The subtree, which is spanned by having, as a subtree of the tree. It is thus to divide the sheets into sheets of left and right leaves of and thus obtains a division of the sheets from the mold. Similarly, the sub-tree partitions the entire parse tree into three parts. Thus we obtain as sharing the substrings that are in the derivation tree the left or right of the of spanned subtree, the substrings, which are not however in the subtree, and finally the substring, which in lies. Here and represent the same variables of our grammar, it follows that the path can be repeated any number of times from to. By repeating the path we would generate words of the form, without leaving our language. What we have proved the pumping lemma for context-free languages.
Example
If the language is context-free?
We assume that is context-free. Be then the corresponding constant from the pumping lemma.
We consider the word. It then needs to be a separation, so that, for all. Since the word contains at most two different letters. Because, can not by all three letters have the same number. So can not be context-free.
A non - context-free language that satisfies the pumping lemma
The language is not context-free. However, satisfies the properties of the pumping lemma: If a word is not the case then this is also true for all words. If the letter is, however, included, there is a decomposition with ( denote the empty word ), and a suffix, so again all words are included.
Swell
- Theory of formal languages
- Compiler