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

- If r
_{1}is a regular expression, then so is (r_{1}). - If r
_{1}is a regular expression, then so is r_{1}*. - If If r
_{1}and r_{2}are regular expressions, then so is r_{1}r_{2}. - If If r
_{1}and r_{2}are regular expressions, then so is r_{1}+r_{2}.

- 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
_{1}and r_{2}indicates any string described by r_{1}immediately followed by any string described by r_{2}. 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}.

Copyright © 1996 by David Matuszek

Last modified Feb 4, 1996