Concepts, definitions (in italics):

• Complement of a language
• Set equality, subset
• Regular Operations (over languages)
• Regular Expressions (REs)
• Operator precedence for regular operations
• L(E), the language specified (described) by a regular expression E.

Reading/homework:

• (regular operations) read p.44 up to middle of p. 45 - same in old book
• (regular expressions) read sec. 1.3 up to middle of p. 66 - same in old book
• Start working on homework 1 (see link in "Homeworks" section of web site); we'll start next class with questions about the homework.

• Know and understand new definitions
• Given two sets, how to prove they are not equal?
• How is {e} different from Æ?
• Given an RE, describe the corresponding regular language (as a set, or in English).
• Given a string s and an RE E, determine whether s is in the language defined by E.
• What is L1 ° L2, if L1 = {e}? L1 = Æ? L2 = {e}? L1 = Æ?
• What is L*, if L = {e}? L = Æ?

• Regular expressions can be found in some programming languages (PERL) and in some utilities (VI, grep).  Here is a Wikipedia definition of regular expressions that discusses this.

Additional examples of regular expressions:

All decimals:

(0-9)(0-9)*('.' U e)(0-9)*

All strings over {0,1} where "0" is the third digit from the last:

(0 U 1)*0(0 U 1)(0 U 1)

All strings over {0,1} where "0" is the fourth digit from the last:

(0 U 1)*0(0 U 1)(0 U 1)(0 U 1)

All strings over {0,1} consisting of an even number of ones and zeros

(01 U 10 U 00 U 11)* or ((0 U 1)(0 U 1))*