regular expressions (REs)

• APPLICATIONS

  • Regular expressions are powerful tools for text searching, notably used in: UNIX/Linux utilities like grep and sed.
  • Compiler generators (e.g., Lex, Flex) for lexical analysis.
  • Widely applied in pattern searching applications such as: Intrusion detection systems and Anti-virus software.
  • Integrated into programming languages (e.g., re module in Python). Accessible through APIs in various languages, e.g., Javas java.util.regex.
• REGULAR EXPRESSIONS

  • Regular expressions are an alternative to NFAs (including-NFAs) and DFAs.
  • They are equivalent in expressive power to NFAs and DFAs.
  • Algebraic characteristics of regular expressions allow for specifying the strings of a language in an expressive manner.
  • Regular expressions de ne languages by specifying patterns that strings of the language must follow.

  
• RECORDA: UNION OF LANGUAGES

  The union of two languages L and M, L M, is the set of strings belonging to either L, M, or both.

  Example: L = {001,10,111}, M = {ε,001} ⇒ L ∪ M = {ε,001,10,111}
• RECORDA: CONCATENATION OF LANGUAGES

  Concatenation, LM, forms strings by joining any string in L with any in M. Example: L and M as before, LM = {001,10,111,001001,10001,111001}
• RECORDA: CLOSURE OF A LANGUAGE

  
• CLOSURE EXAMPLES

  
• REGULAR EXPRESSIONS: CONSTRUCTION

  
• REGULAR EXPRESSIONS OPERATORS

  • Parentheses can be used to force a certain order
  • + used to represent 1 or more occurrences

  A) *

  B) .

  C) +

  D) |

  E) U

  
• What is the order of precedence of REs operators?

  * > . > +
• EXAMPLE