Page 1 1 CS 172: Computability and Complexity Regular Expressions Sanjit A. Seshia EECS, UC Berkeley Acknowledgments: L.von Ahn, L. Blum, M. Blum S. A. Seshia 2 The Picture So Far DFA NFA Regular language Page 2 1 CS 172: Computability and Complexity Regular Expressions Sanjit A. Seshia EECS, UC Berkeley Acknowledgments: L.von Ahn, L. Blum, M. Blum S. A. Seshia 2 The Picture So Far DFA NFA Regular language 2 S. A. Seshia 3 Today’s Lecture DFA NFA Regular language Regular expression S. A. Seshia 4 Regular Expressions • What is a regular expression? Page 3 1 CS 172: Computability and Complexity Regular Expressions Sanjit A. Seshia EECS, UC Berkeley Acknowledgments: L.von Ahn, L. Blum, M. Blum S. A. Seshia 2 The Picture So Far DFA NFA Regular language 2 S. A. Seshia 3 Today’s Lecture DFA NFA Regular language Regular expression S. A. Seshia 4 Regular Expressions • What is a regular expression? 3 S. A. Seshia 5 Regular Expressions • Q. What is a regular expression? • A. It’s a “textual”/ “algebraic” representation of a regular language – A DFA can be viewed as a “pictorial” / “explicit” representation • We will prove that a regular expressions (regexps) indeed represent regular languages S. A. Seshia 6 s is a regular expression representing {s s s s} ( s s s s ? ? ? ? S S S S ) e is a regular expression representing {e} Ø Ø Ø Ø is a regular expression representing Ø Ø Ø Ø If R 1 and R 2 are regular expressions representing L 1 and L 2 then: (R 1 R 2 ) represents L 1 · ·· ·L 2 (R 1 ? ? ? ? R 2 ) represents L 1 ? ? ? ? L 2 (R 1 )* represents L 1 * Regular Expressions: Definition Page 4 1 CS 172: Computability and Complexity Regular Expressions Sanjit A. Seshia EECS, UC Berkeley Acknowledgments: L.von Ahn, L. Blum, M. Blum S. A. Seshia 2 The Picture So Far DFA NFA Regular language 2 S. A. Seshia 3 Today’s Lecture DFA NFA Regular language Regular expression S. A. Seshia 4 Regular Expressions • What is a regular expression? 3 S. A. Seshia 5 Regular Expressions • Q. What is a regular expression? • A. It’s a “textual”/ “algebraic” representation of a regular language – A DFA can be viewed as a “pictorial” / “explicit” representation • We will prove that a regular expressions (regexps) indeed represent regular languages S. A. Seshia 6 s is a regular expression representing {s s s s} ( s s s s ? ? ? ? S S S S ) e is a regular expression representing {e} Ø Ø Ø Ø is a regular expression representing Ø Ø Ø Ø If R 1 and R 2 are regular expressions representing L 1 and L 2 then: (R 1 R 2 ) represents L 1 · ·· ·L 2 (R 1 ? ? ? ? R 2 ) represents L 1 ? ? ? ? L 2 (R 1 )* represents L 1 * Regular Expressions: Definition 4 S. A. Seshia 7 * * * * ···· ? ? ? ? Operator Precedence 1. 2. 3. ( often left out; a · · · · b ab ) S. A. Seshia 8 R 2 R 1 * ( R 1 *R 2 ? ? ? ? R 3 = ( ) )? ? ? ? R 3 Example of Precedence Page 5 1 CS 172: Computability and Complexity Regular Expressions Sanjit A. Seshia EECS, UC Berkeley Acknowledgments: L.von Ahn, L. Blum, M. Blum S. A. Seshia 2 The Picture So Far DFA NFA Regular language 2 S. A. Seshia 3 Today’s Lecture DFA NFA Regular language Regular expression S. A. Seshia 4 Regular Expressions • What is a regular expression? 3 S. A. Seshia 5 Regular Expressions • Q. What is a regular expression? • A. It’s a “textual”/ “algebraic” representation of a regular language – A DFA can be viewed as a “pictorial” / “explicit” representation • We will prove that a regular expressions (regexps) indeed represent regular languages S. A. Seshia 6 s is a regular expression representing {s s s s} ( s s s s ? ? ? ? S S S S ) e is a regular expression representing {e} Ø Ø Ø Ø is a regular expression representing Ø Ø Ø Ø If R 1 and R 2 are regular expressions representing L 1 and L 2 then: (R 1 R 2 ) represents L 1 · ·· ·L 2 (R 1 ? ? ? ? R 2 ) represents L 1 ? ? ? ? L 2 (R 1 )* represents L 1 * Regular Expressions: Definition 4 S. A. Seshia 7 * * * * ···· ? ? ? ? Operator Precedence 1. 2. 3. ( often left out; a · · · · b ab ) S. A. Seshia 8 R 2 R 1 * ( R 1 *R 2 ? ? ? ? R 3 = ( ) )? ? ? ? R 3 Example of Precedence 5 S. A. Seshia 9 { w | w has exactly a single 1 } 0*10* What’s the regexp? S. A. Seshia 10 What language does Ø Ø Ø Ø * represent? {e}Read More