pumping lemma (context-free languages)
Let be a context-free language (a.k.a. type 2 language). Then there exist
two integers and such that, if the length of a word is greater
than , then where are subwords such that
-
1.
The length of the subword is less than .
-
2.
is not be empty.
-
3.
For all integers , it is the case that belongs to , where exponentiation denotes repetition of a subword times.
An important use of this lemma is that it allows one to show that a language
is not context-free. (Remember, just because a language happens to be described
in terms of a context-sensitive grammar does not automatically preclude the
possibility of describing the same language also by a
context-free language.) The idea is to assume that the language is
context-free, then arrive at a contradiction via this lemma.
As an illustrative example, consider the following language, which consists of
but one terminal symbol, ‘x’ and which consists of all strings of ‘x’ ’s whose
length is a perfect square. Were this a context-free language, there would
exist integers and as above. Choose an integer such that .
Then the word belongs to our language and the lemma tells us that
it can be written as so as to satisfy the conditions enumerated above.
Write , , , , for suitable nonnegative integers . Then we have ;
by condition , and, by condition , would
have to be a perfect square because would be a word of the
language. This, however, leads to a contradiction:
could not possibly be a perfect square for all unless .
As an exercise, the reader may consider constructing a context-sensitive
grammar for this language and posting it as an attachment to this entry
(at which time this sentence will come down).
Title | pumping lemma |
---|---|
Canonical name | PumpingLemmacontextfreeLanguages |
Date of creation | 2013-03-22 16:21:10 |
Last modified on | 2013-03-22 16:21:10 |
Owner | rspuzio (6075) |
Last modified by | rspuzio (6075) |
Numerical id | 8 |
Author | rspuzio (6075) |
Entry type | Theorem |
Classification | msc 68Q42 |
Synonym | pumping lemma |
Related topic | PumpingLemmaRegularLanguages |