$1.$ Write a regular expression for each of the following:

Note: Intuitive Reading of Regular Expressions

Concatenation $==$is followed by$$

$|==$or$$

$*==$zero or more occurrences$$

$0$ or $11$ or $101$

$$ Answer: $0|11|101$

$$ all strings over $\{$a$,$b$\}$ that start with an a

$$ Answer: a$($a$|$b$)*$

$$ only $0$s

$$ all binary strings

$$ all binary strings except empty string

$$ all strings over the alphabet $\{0,1\}$ that begin with $1,$ end with $1$

$$ all strings over the alphabet $\{0,1\}$ that end with $00$

$$ all strings over the alphabet $\{0,1\}$ that contain at least three $1$s

$$ all strings over the alphabet $\{0,1\}$ that contain at least three consecutive $1$s

$$ all strings over the alphabet $\{0,1\}$ that contain the substring $110$

$$ all strings over the alphabet $\{0,1\}$ that don't contain the substring $110$

$$ Answer: $(0|10)*1*$

$$ all strings over the alphabet $\{0,1\}$ that contain at least two $0$s but not

consecutive $0$s

$$ all strings over the alphabet $\{0,1\}$ that have at least $3$ characters, and the third

character is $0$

$$ Answer: $(0|1)(0|1)0(0|1)*$

$$ all strings over the alphabet $\{0,1\}$ that the number of $0$s is a multiple of $3$

$$ all strings over the alphabet $\{0,1\}$ that start and end with the same character

$$ odd length

$$ all strings over the alphabet $\{$ a$,$ b $\}$ with $$ab$$ as substring