hws/hw01.tex
changeset 293 ca349cfe3474
parent 267 a1544b804d1e
child 294 c29853b672fb
equal deleted inserted replaced
292:7ed2a25dd115 293:ca349cfe3474
    32 \item Give the definition for regular expressions. What is the meaning
    32 \item Give the definition for regular expressions. What is the meaning
    33   of a regular expression? (Hint: The meaning is defined recursively.)
    33   of a regular expression? (Hint: The meaning is defined recursively.)
    34 
    34 
    35 \item Assume the concatenation operation of two strings is written as
    35 \item Assume the concatenation operation of two strings is written as
    36   $s_1 @ s_2$. Define the operation of \emph{concatenating}, written
    36   $s_1 @ s_2$. Define the operation of \emph{concatenating}, written
    37   $\_ \,@\, \_$ two sets of strings.
    37   $\_ \,@\, \_$, two sets of strings.
    38 
    38 
    39 \item Assume a set $A$ contains 4 strings and a set $B$ 7 strings, how
    39 \item Assume a set $A$ contains 4 strings and a set $B$ 7 strings. None
    40   many strings are in $A \,@\, B$?
    40   of the strings is the empty string. How many strings are in $A \,@\, B$?
    41 
    41 
    42 \item How is the power of a language defined? (Hint: There are two
    42 \item How is the power of a language defined? (Hint: There are two
    43   rules, one for $\_^0$ and one for $\_^{n+1}$.)
    43   rules, one for $\_^0$ and one for $\_^{n+1}$.)
       
    44 
       
    45 \item Let $A = \{[], [a], [b], [c]\}$. How many strings are in $A^4$?
    44 
    46 
    45 \item How many regular expressions are there to match the string
    47 \item How many regular expressions are there to match the string
    46   $abc$? How many if they cannot include $\epsilon$ and $\varnothing$?
    48   $abc$? How many if they cannot include $\epsilon$ and $\varnothing$?
    47   How many if they are also not allowed to contain stars? How many if
    49   How many if they are also not allowed to contain stars? How many if
    48   they are also not allowed to contain $\_ + \_$?
    50   they are also not allowed to contain $\_ + \_$?