\item Give the definition for regular expressions. What is the

      meaning of a regular expression? (Hint: The meaning is

      defined recursively.)

\item Assume the concatenation operation of two strings is

      written as $s_1 @ s_2$. Define the operation of

      \emph{concatenating} two sets of strings. This operation

      is also written as $\_ \,@\, \_$.

\item Assume a set $A$ contains 4 strings and a set $B$

      contains 7 strings. None of the strings is the empty

      string. How many strings are in $A \,@\, B$?

\item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings

      are in $A^4$? (2) Consider the case of $A^4$ where one of

      the strings in $A$ is the empty string, for example $A =

      \{[a], [b], [c], []\}$.

\item How many basic regular expressions are there to match

      the string $abcd$? (ii) How many if they cannot include

      $\epsilon$ and $\varnothing$? (iii) How many if they are

      also not allowed to contain stars? (iv) How many if they

      are also not allowed to contain $\_ + \_$?

\item When are two regular expressions equivalent? Can you

      think of instances where two regular expressions match

      the same strings, but it is not so obvious that they do?

      For example $a + b$ and $b + a$ do not count\ldots they

      obviously match the same strings, namely $[a]$ and

      $[b]$.