2. Examples of regular expressions

Example 2

Given the following language:

$$\begin{array}{rl}L& =\text{all the strings consisting of some number (possibly none)}\\ & \text{ of }a\text{ followed by some number (possibly none) of }b\\ & =\{ϵ,a,b,aa,bb,ab,aaa,aab,bbb,abb,abb,...,aaaabbbbbbb\}\end{array}$$

We can use the regular expression:

$$a^{\ast }{b}^{\ast }⇝L\text{ is represented by the regular expression }{a}^{\ast }{b}^{\ast }$$

We use the notation: $\boxed{L=\text{Language\_of}(a^{\ast }{b}^{\ast })}$ Which we read as “the language of $a^{\ast }{b}^{\ast }$ is $L$”, or “the language represented by $a^{\ast }{b}^{\ast }$ is $L$”.

Example 3

$$\begin{array}{rl}\text{Langauge\_of}(a(a^{\ast }\cup b^{\ast }))& =\text{all words starting with }a\text{ followed by either a}\\ & \text{(possibly empty) word of }a\text{ or a (possibly empty)}\\ & \text{word of }b\\ & =\{a,aa,ab,aaa,abb,aaaa,abbb,aaaaaa,abbbbbbb\}\end{array}$$

Example 4

$$\begin{array}{rl}\text{Language\_of}(a(a\cup b^{\ast }))& =\text{all words starting with }a\text{ followed by}\\ & \text{any word over }\{a,b\}\\ & =\text{all words over }\{a,b\}\text{ starting with }a\\ & =\{a,aa,ab,aaa,aab,aba,abb,aaaaa\}\end{array}$$

Example 5

Find the $\text{Language\_of}((b\cup aa{a}^{\ast })\ast )$.

1. Start by finding $\text{Language\_of}(aa{a}^{\ast })$

   $$\begin{array}{rl}\text{Language\_of}(aa{a}^{\ast })& =\text{all words of }a\text{ of length }\ge 2\\ & =\{aa,aaa,aaaa,aaaaa,...\}\end{array}$$

2. Find $\text{Language\_of}(b\cup aa{a}^{\ast })$

   $$\begin{array}{rl}\text{Language\_of}(b\cup aa{a}^{\ast })& =\text{ as above plus the word }b\\ & =\{b,aa,aaa,aaaa,...\}\end{array}$$

3. Find $\text{Language\_of}((b\cup aa{a}^{\ast })\ast )$ We can take any number (possibly none) of words from $\text{Language\_of}(b\cup aa{a}^{\ast })$ and concatenate them together.

Example 6

Find the $\text{Language\_of}((b\cup a)a{a}^{\ast })$.

1. Find $\text{Language\_of}(b\vee a)=\{a,b\}$.
2. Find $\text{Language\_of}((b\vee a)a)=\{aa,ba\}$.
3. Find $\text{Language\_of}((b\vee a)aa\ast )=$ all words starting with $aa$ or $ba$ followed by a (possibly empty) word of $a$s.

Example 7

Find the $\text{Language\_of}(ϵ\vee c^{\ast }(a\vee b{c}^{\ast }))$

All the strings that are either empty or start with some (possibly none) $c$s followed by either an $a$, or a $b$ followed by (possibly none) $c$s.

For example, $\{ϵ,a,b,be,bee,ca,cb,cbc\}$.