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
[go: Go Back, main page]

INF2: Syntax and Semantics 2003

Lecture 4

Syntax and Semantics

Topics

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, 17 February 2003 at 10:15 in A4-106.

Reading Material

Exercises

Luca Aceto, Institute of Computer Science, Aalborg University.
Last modified: .