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 Formal Languages and Computability
Keywords: The pumping lemma for regular languages and its
applications. Non-regular languages.
After having reviewed the algorithm for generating a regular
expression from a DFA, and its applications, 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.
Time and Location
Monday, 13 September 2004 at 14:30 in A4-106. Note! We
are going to have two lectures on Monday, 13 September 2004!
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.
[Optional, but
recommended] As I have told you several times during the
lecture, you cannot use the pumping lemma to show that a
language is regular. This exercise is meant to convince you that
there are indeed languages that have the property stated in the
pumping lemma, but are not regular.
To this end, consider the language
L = {cman bn | m >= 1, n >= 0 } U { am bn | m,n >= 0 } .
Argue that
L meets the condition of the pumping lemma. [Hint: Take its pumping length p to be 1.]
L is not regular. [Hint: Argue, first of all, that if L were regular, then so would the language
{cman bn | m >= 1, n >= 0 } .
Next show that this language is not regular using the pumping lemma.]