| Pumping Lemma For Regular Languages |
Article Index for Pumping |
Website Links For Pumping |
Information AboutPumping Lemma For Regular Languages |
| CATEGORIES ABOUT PUMPING LEMMA FOR REGULAR LANGUAGES | |
| formal languages | |
| lemmas | |
|
The pumping lemma was first articulated by Y. Bar-Hillel , M. Perles , E. Shamir in 1961 Y. Bar-Hillel , M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", ''Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung'' 14 (1961) pp. 143-172. FORMAL STATEMENT Let ''L'' be a regular language. Then there exists an integer ''p'' ≥ 1 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: | ||
| Over The Alphabet &Sigma | {''a'', ''b''} is not regular We will let ''w'', ''x'', ''y'', ''z'', ''p'', and ''i'' be as stated in the pumping lemma for regular languages Let ''w'' = ''a<sup>p</sup>b<sup>p</sup>'' It is obviously in ''L'', and the pumping lemma therefore yields a decomposition of ''w'' = ''xyz'' with ''xy'' &le ''p'', ''y'' &ge 1 and |
|
| ''xy<sup>i</sup>z'' In L For Every ''i'' &ge 0 If We Let ''xy'' | ''p'' and ''z''=''p'', then ''xy'' is the first half of ''w'', or all ''p'' of the ''a''s Because ''y'' &ge 1, it consists of a non-zero number of ''a''s, and ''xy<sup>2</sup>z'' has more ''a''s than ''b''s and is therefore not in ''L'' (note that any value of ''i'' &ne 1 will give us a contradiction) We have reached a contradiction because, in this case, the pumping lemma does not hold Therefore, the assumption that ''L'' is regular must be incorrect ''L'' is not regular |
|
|