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]

Syntax and Semantics

Lecture 4

Syntax and Semantics

Topics

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.

Time and Location

Monday, 29 November 2004 at 9:00 in room 303.

Reading Material

Exercises

Luca Aceto, Institute of Computer Science, Aalborg University.
Last modified: Monday, 22-Nov-2004 17:20:19 CET.