Regular Expression

Basics

• Regular expression is an algebra for defining patterns (vs. FSA being a machine for defining patterns).
• The algebra consists of:
  • Operands (atomic)
    • single character -- e.g. a, b
    • e (epsilon) -- for empty string ""
    • {} (empty set)
    • variable
  • Operators
    • union ( | ) -- e.g. (a | b) | c
    • concatenation -- e.g. abc
    • closure ( * ), 0 or more occurrence of string/char -- e.g. (a*)
  • Precedence of operators
    • closure > concatenation > union
• More examples of regular expressions

  regular expression	Example strings that match the pattern
  (a | b) c
  (ab)*c
  (ab)*(c|e)
  a | bc*d
  (ab*c)*b

• A regular expression denotes/specifies a language -- a set of strings that meet the pattern.
  • Expressions with atomic operand only:
    • L(a) = {a}
    • L(e) = {e}
    • L({}) = {}
  • Expression with operators:
    • L(R | S) = L(R) U L(S)
    • L(RS) = {rs | r Î L(R) and s Î L(S)}
    • L(R*) = {e} | L(RR*)
• Examples

  language	(some) strings in the language
  L( ea )
  L( (a | b)* )
  L( (a*b*)* )
  L( (a*ba*b)* a* )

Unix Pattern Matching

• Unix operating systems allows commands with regular expressions to do pattern matching (in editors and grep command).
• Some extensions:
  • union of characters by [ ] -- e.g. [abc] == (a | b | c)
  • range of characters by - inside [ ] -- e.g. [a-zA-Z]
  • line beginning by ^ -- e.g. ^TO:
  • line ending by $ -- e.g. ^a[bc]*d$
  • escape character by \
  • wild card by . -- for any character except for newline
  • optional char by ? -- e.g. L(abc?) = {e} U L(abc)
  • "one or more" by ⁺ -- e.g. (a⁺b⁺c⁺)
• Examples:
  1. A social security number (in the form "999-99-9999")
     
     
     
     
  2. A line which starts with words of the form "Q1" or "Q1.2" or "Q1.3.2"
     
     
     
     
  3. A word with vowels in order
     
     
     
     

Equivalence of Regular Expressions

• Two regular expressions R and S are equivalent (i.e., R º S) if and only if L(R) = L(S).