**Lecture 2
(Regular Expressions), 8/30/17**

**Concepts, definitions (in italics):**

- Definitions are the basis for
proofs. Together with “givens”, they are the “inputs” for the proofs.
- Example: proofs that S
INTERSECT empty-set = empty-set, S U empty-set = S
*Language operations*:*concatenation*L1 o L2,*star**L*^{*}*Regular operations*(over languages): *, o, U*Regular Expressions*(REs) specify languages (each regular expression evaluates to some language)- 3 types of simple REs (base cases)
- 3 types of complex REs (recursively defined)
- Other examples of a
recursive definition: Fibonacci numbers, arithmetic expressions
- Language
*specified*by an RE - Also a recursive definition
*Expression trees*for REs- Analogous to expression trees for arithmetic expressions
*Operator precedence*for regular operations

·
*Equivalent* regular expressions –
specify the same language

*Regular Language -*language*specified*by some RE- Class of
*regular languages* - Example: RE for decimal numbers
- Our TA, homework 0

**Reading/homework**:

- Get the text book (Sipser,
edition 3)
- (regular operations) read p.44 up to middle of p. 45
- (regular expressions) read sec. 1.3 up to middle of p.
66
- Do homework 0 for next class (found in the “Homeworks” section of the course website)

**Skills:**

- Know and understand new definitions
- Given an RE, what is the expression tree for it?
- Given an RE, describe the corresponding regular
language (as a set, or in English)
- Given a string
*w*and an RE*R*, determine whether*w*is in the language defined by*R*