Building Regular Expressions

Introduction: Assume that S = {a, b, c}

Zero or more: a* means “zero or more a’s”,

To say “zero or more ab’s,” i.e., {l, ab, abab, . . . } you need to say (ab)*.

One or more: Since a* means “zero or more a’s”, you can use aa* (or equivalently a*a) to mean “one or more a’s”. Similarly to describe ‘one or more ab’s”, that is {ab, abab, ababab, KK}, you can use ab (ab)*. Zero or one: It can be described as an optional ‘a’ with (a l).

• Any string at all: To describe any string at all (with S = {a, b, c} you can use (a b c)*.
• Any nonempty string: This is written any character from S = {a, b, c} followed by any string at all: (a b c) (a b c)*
• Any string not containing ..........: To describe any string at all that does not contain an ‘a’ (with S = {a, b, c}), you can use (b c)*.
• Any string containing exactly one ........: To describe any string that contains exactly one ‘a’ put “any string not containing an a”, on either side of the ‘a’ like: (b c)* a(b c)* .

Languages defined by Regular Expressions: There is a very simple correspondence between regular expressions and the languages they denote: