**Lecture 2
(Regular Expressions), 1/18/18**

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

*Language operations*:*concatenation*L1 o L2,*star**L*^{*}- The difference between {} and {
*e*} *Regular operations*(over languages): *, o, U*Regular Expressions*(REs) specify languages (each regular expression evaluates to some language)- 3 types of simple REs
- 3 types of complex REs
*Expression trees*for REs- Analogous to expression trees for arithmetic expressions
- Leaves represent values, internal nodes represent operations
- Evaluation takes place upwards from the leaves to the roots
*Operator precedence*for regular operations- Applications for REs:
- pattern matching
template when searching for substrings, for a utility such as
*grep* - specifying syntax of
programming language tokens, for a compiler or interpreter

**Reading/homework**:

- Get the text book (Sipser,
edition 3)
- (regular operations) read p.44 (after figure 1.22) up
to middle of p. 45 (before theorem 1.25)
- (regular expressions) read sec. 1.3 up to middle of p.
66 (before "equivalence with finite automata")
- 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*