Module #3: Pattern Matching, Regular Expressions
& Languages and Finite Automata

Objectives

1. Determine if a string matches a pattern
   
2. Define a regular expression
   
3. Build regular expressios
   
4. Show regular languages are closed under union, intersection, concatenation, complement, and *
   
5. Convert dfa's to regular expressions
   
6. Convert regular expressions to automata
   
7. Use regular expressions for lexical analysis
   
8. Find patterns in text
   
9. Show equivalence of regular expressions
   

Topics

1. Pattern Matching
   
2. Regular expressions
   
3. Equivalence of Regular Expressions and Finite Automata
   
4. Closure Properties of Regular languages
   

Background Material

0. Texts

Hopcroft, Motwani and Ullman: Chapter 3
Kozen: Lectures 7-9
Sudkamp: Sections 6.1-6.4

1. Wikepedia: Regular Expressions
1. Grahne Text Slides: Pages 53-88 and tape
2. Busch, Shiri & Grahne: Regular Expressions
3. Tom LeBlanc: Regular Expressions
4. Lemone: Lex Examples [PDF] from CS544
5. robelle: Grep examples
6.Old Homework [DOC] [PDF]
7. Old Homework Solutions [PPT] [DOC] [PDF]

Homework [DOC] [PDF]

Homework Solutions [PDF]