35 \item Give the definition for regular expressions. What is the |
35 \item Give the definition for regular expressions. What is the |
36 meaning of a regular expression? |
36 meaning of a regular expression? |
37 |
37 |
38 \item Assume the concatenation operation of two strings is |
38 \item Assume the concatenation operation of two strings is |
39 written as $s_1 @ s_2$. Define the operation of |
39 written as $s_1 @ s_2$. Define the operation of |
40 \emph{concatenating} two sets of strings. |
40 \emph{concatenating}, written $\_ \,@\, \_$ two sets of |
|
41 strings. |
41 |
42 |
42 \item Assume a set $A$ contains 4 strings and a set $B$ 7 |
43 \item Assume a set $A$ contains 4 strings and a set $B$ 7 |
43 strings, how many strings are in $A @ B$? |
44 strings, how many strings are in $A @ B$? |
44 |
45 |
45 \item How is the power of a language defined? (Hint: There are |
46 \item How is the power of a language defined? (Hint: There are |
46 two rules, one for $\_^0$ and one for |
47 two rules, one for $\_^0$ and one for |
47 $\_^{n+1}$.) |
48 $\_^{n+1}$.) |
48 |
49 |
49 \item How many regular expressions are there to match the |
50 \item How many regular expressions are there to match the |
50 string $abc$? (How many if they cannot include |
51 string $abc$? How many if they cannot include |
51 $\epsilon$ and $\varnothing$? How many if they are also |
52 $\epsilon$ and $\varnothing$? How many if they are also |
52 not allowed to contain stars? How many if they are also |
53 not allowed to contain stars? How many if they are also |
53 not allowed to contain $\_ + \_$?) |
54 not allowed to contain $\_ + \_$? |
54 |
55 |
55 \item When are two regular expressions equivalent? Can you |
56 \item When are two regular expressions equivalent? Can you |
56 think of instances where two regular expressions match |
57 think of instances where two regular expressions match |
57 teh same strings, but it is not so obvious that they do? For |
58 the same strings, but it is not so obvious that they do? For |
58 example $a + b$ and $b + a$ do not count\ldots they |
59 example $a + b$ and $b + a$ do not count\ldots they |
59 obviously match the same strings, namely $[a]$ and $[b]$. |
60 obviously match the same strings, namely $[a]$ and $[b]$. |
60 |
61 |
61 \end{enumerate} |
62 \end{enumerate} |
62 |
63 |