Regular Expressions

Return to List of Lectures

Previous Lecture

• Questions?
• Regular Expressions
  • Section 1.3 through “Formal Definition of a Regular Expression”
    • Formal definition
      • For each a in Σ, a is a regular expression
      • ε is regular expression
      • ∅ also
      • If R₁ and R₂ are regular expressions, then so are the following
        • (R₁ ∪ R₂) - union operator
        • (R₁ R₂) - concatenation operator
        • (R₁*) - star * operator
  • Examples / Questions
    • Regular expression for language over {a,b,c} in which all a’s come before all c’s (e.g., abc, abaabcbccb, a, c, ε, etc.)
      • (a∪b)* (c∪b)*
    • Regular expression for conventional notation for positive integers, i.e., strings of digits without leading 0s, unless only digit is 0
      • ((1∪2∪3∪4∪5∪6∪7∪8∪9)(0∪1∪2∪3∪4∪5∪6∪7∪8∪9)*) ∪ 0
      • Shorthand R⁺ = R R*
  • Use of extended regular expression notation in grep-style pattern matchers, e.g., in text editor search commands
  • Do you really need ε as a primitive regular expression?
    • No, ∅* = {ε}
  • Prove that every regular expression that doesn’t use * produces a finite language
    • Induction (technically on length of regular expression)
    • Base cases: ∅, ε, a produce finite languages
    • Induction: Assume R₁ and R₂ produce finite languages
      • (R₁∪R₂) is finite
      • (R₁R₂) is finite
    • Structural induction
• Next
  • Regular expressions are equivalent to regular languages
  • Read “Equivalence with Finite Automata”

Next Lecture