Role of regular expressions

A regular expression is a compact algebraic way of describing a set of strings (a regular language) using the symbols of an alphabet with three operations: union (+ or |), concatenation and Kleene star (*). For example, (a+b)*ab describes all strings over {a, b} that end in ab.

Roles:

• Describing languages: they give a precise, short description of the strings a finite automaton accepts. By Kleene's theorem, a language is regular if and only if some regular expression (or finite automaton) describes it. So they are used to define and prove properties of regular languages.
• Lexical analysis: compilers define tokens (identifiers, numbers, keywords) by regular expressions, and a scanner generator (such as Lex) converts them to finite automata. For example, identifier = letter(letter + digit)*.
• Pattern matching and searching: text editors, grep, search and replace, and form validation (e-mail, phone numbers) use them.
• Design of automata: writing the regular expression first, then converting it to an NFA and DFA, is an easy way to design circuits and protocols that recognise input patterns.