Formal Statement
Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:
- |y| ≥ 1;
- |xy| ≤ p
- for all i ≥ 0, xyiz ∈ L
y is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in L). (1) means the loop y to be pumped must be of length at least one; (2) means the loop must occur within the first p characters. |x| must be smaller than p (conclusion of (1) and (2)), apart from that there is no restriction on x and z.
In simple words, for any regular language L, any sufficiently long word w (in L) can be split into 3 parts. i.e. w = xyz, such that all the strings xykz for k≥0 are also in L.
Below is a formal expression of the Pumping Lemma.
Read more about this topic: Pumping Lemma For Regular Languages
Famous quotes containing the words formal and/or statement:
“The spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (1869–1950)
“Eloquence must be grounded on the plainest narrative. Afterwards, it may warm itself until it exhales symbols of every kind and color, speaks only through the most poetic forms; but first and last, it must still be at bottom a biblical statement of fact.”
—Ralph Waldo Emerson (1803–1882)