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:

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 r₁ and r₂ indicates any string described by r₁ immediately followed by any string described by r₂. 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, ...}.