Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Syntax and Semantics
Keywords: The pumping lemma for regular languages and its
applications. Non-regular languages.
This lecture deals with the following question:
How do we show that a language is not
regular?
The mere fact that we might be unable to construct a DFA that
recognizes a language L does not constitute a proof of the
non-regularity of that language. One way to argue that L is
not regular is to isolate a characteristic property enjoyed by all the
regular languages, but not by L. The so-called pumping
lemma gives one such property. Using the property described in
the statement of the pumping lemma, we can now formally show that many
languages are not regular.
Supplementary Reading for the Keenest: Sections 2 and
3 of Guo-Qiang Zhang and E. Rodney Canfield. The end of pumping?
Theoretical Computer Science, 174(1-2):275-279, 15 March
1997. (Available for photocopying from the course folder.)
Exercises
Exercises 1.17(a,b)(*) and 1.18(*) on page 86 of Sipser's book.
Problems 1.23(*) (page 88), 1.39 (page 90) and 1.41 (page 90) in Sipser's book.