3. Describing regular expressions by recursion

Describing regular expressions by recursion

Regular expression

A regular expression (over alphabet $S$) is a string consisting of:

• symbols from $S$
• and symbols from $\cup ,{}^{\ast },(,),ϵ,\varnothing$.

Link to original

The infinite set of regular expression over $S$ is defined recursively as follows:

• Basis case: $\varnothing$, $ϵ$, and each symbol in the alphabet $S$ are regular expressions.
• Recursive step: if $R$ and $Z$ are regular expressions, then so are $(R\cup Z)$, $(RZ)$, and $(R^{\ast })$.

Notational conventions

There are some conventions to follow when working with regular expressions:

• Outermost brackets are omitted.
• Brackets are omitted when concatenating expressions. e.g. writing $abaab$ instead of $(((ab)(ab))b)$.
• ‘binds’ take precedence over concatenation e.g. we write $aa{b}^{\ast }$ instead of $(aa)(b^{\ast })$