2 \usepackage{../style}

     2 \usepackage{../style}

     3 

     3 

     4 \begin{document}

     4 \begin{document}

     5 

     5 

     6 \section*{Homework 1}

     6 \section*{Homework 1}

     7 

     9 

     8 \begin{enumerate}

    10 \begin{enumerate}

     9 

    11 

    10 \item {\bf (Optional)} If you want to run the code presented in the

    12 \item {\bf (Optional)} If you want to run the code presented in the

    11   lectures, install the Scala programming language available (for

    13   lectures, install the Scala programming language available (for

    42 \item How is the power of a language defined? (Hint: There are two

    44 \item How is the power of a language defined? (Hint: There are two

    43   rules, one for $\_^0$ and one for $\_^{n+1}$.)

    45   rules, one for $\_^0$ and one for $\_^{n+1}$.)

    44 

    46 

    45 \item Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$?

    47 \item Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$?

    46   Consider the case of $A^4$ where one of the strings in $A$ is the 

    48   Consider the case of $A^4$ where one of the strings in $A$ is the 

    48 

    50 

    49 \item How many regular expressions are there to match the string

    51 \item How many regular expressions are there to match the string

    50   $abc$? How many if they cannot include $\epsilon$ and $\varnothing$?

    52   $abc$? How many if they cannot include $\epsilon$ and $\varnothing$?

    51   How many if they are also not allowed to contain stars? How many if

    53   How many if they are also not allowed to contain stars? How many if

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

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