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 $\_ + \_$? |