[Overview] [Previous] [Next]

# Regular Expressions

Every primitive regular expression is a regular expression.

We can compose additional regular expressions by applying the following rules a finite number of times:

• If r1 is a regular expression, then so is (r1).
• If r1 is a regular expression, then so is r1*.
• If If r1 and r2 are regular expressions, then so is r1r2.
• If If r1 and r2 are regular expressions, then so is r1+r2.
Here's what the above notation means:
• Parentheses are just used for grouping.

• The postfix star indicates zero or more repetitions of the preceding regular expression. Thus, if x , then the regular expression x* denotes the language {, x, xx, xxx, ...}.

• Juxtaposition of r1 and r2 indicates any string described by r1 immediately followed by any string described by r2. For example, if x, y , then the regular expression xy describes the language {xy}.

• The plus sign, read as "or," denotes the language containing strings described by either of the component regular expressions. For example, if x, y , then the regular expression x+y describes the language {x, y}.
Precedence: * binds most tightly, then justaposition, then +. For example, a+bc* denotes the language {a, b, bc, bcc, bccc, bcccc, ...}.