[Overview] [Previous] [Next]

Languages Defined by Regular Expressions

There is a simple correspondence between regular expressions and the languages they denote:

Regular expression L(regular expression)
x, for each x is a member of sigma {x}
empty string {empty string}
null set { }
(r1) L(r1)
r1* (L(r1))*
r1 r2 L(r1) L(r2)
r1 + r2 L(r1) union L(r2)

Copyright © 1996 by David Matuszek
Last modified Feb 5, 1996