Regular Expressions

Page 1

Language

informal language English or French

formal language - a series of words whose letters are taken from an alphabet, and are formed according to a set of rules

regular language

regular language can be defined using a Regular Expression

* zero or more

+ one or more

? zero or one

| "or"

ab*|c

(A followed by 0 or more B) or a C

1|01+

(1) or (0 followed by one or more 1)

Page 2

b*c

zero or more B followed by a C

b?c

zero or one B followed by a C

letter b, followed by zero or more occurrences of the string cd followed by either a single letter e or the string fg.

b(cd)*(e|fg)

any number of A followed by two B

a*bb

a followed by zero or more of ba OR b followed by zero or more of ab

a(ba)* | b(ab) *

Page 3

(a*b*)*c

A* followed by a B OR B* followed by A followed by any number of A or B

(a*b|b*a) (a*b*)*