7 \begin{document} |
7 \begin{document} |
8 |
8 |
9 \section*{Homework 2} |
9 \section*{Homework 2} |
10 |
10 |
11 \begin{enumerate} |
11 \begin{enumerate} |
12 \item Review the first handout about sets of strings and read the second handout. |
12 \item Review the first handout about sets of strings and read |
13 Assuming the alphabet is $\{a, b\}$, decide which of the following equations are true |
13 the second handout. Assuming the alphabet is $\{a, b\}$, |
14 in general for arbitrary languages $A$, $B$ and $C$: |
14 decide which of the following equations are true in |
|
15 general for arbitrary languages $A$, $B$ and $C$: |
|
16 |
15 \begin{eqnarray} |
17 \begin{eqnarray} |
16 (A \cup B) @ C & = & A @ C \cup B @ C\nonumber\\ |
18 (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\ |
17 A^* \cup B^* & = & (A \cup B)^*\nonumber\\ |
19 A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\ |
18 A^* @ A^* & = & A^*\nonumber\\ |
20 A^* @ A^* & =^? & A^*\nonumber\\ |
19 (A \cap B)@ C & = & (A@C) \cap (B@C)\nonumber |
21 (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber |
20 \end{eqnarray} |
22 \end{eqnarray} |
21 |
23 |
22 \noindent |
24 \noindent In case an equation is true, give an explanation; |
23 In case an equation is true, give an explanation; otherwise give a counter-example. |
25 otherwise give a counter-example. |
24 |
26 |
25 \item What is the meaning of a regular expression? Give an inductive definition. |
27 \item What is the meaning of a regular expression? Give an |
|
28 inductive definition. |
26 |
29 |
27 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 = \varnothing$ and $r_3 = a$. |
30 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 |
28 How many strings can the regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
31 = \varnothing$ and $r_3 = a$. How many strings can the |
|
32 regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each |
|
33 match? |
29 |
34 |
30 |
35 |
31 \item Give regular expressions for (a) decimal numbers and for (b) binary numbers. |
36 \item Give regular expressions for (a) decimal numbers and for |
32 (Hint: Observe that the empty string is not a number. Also observe that leading 0s |
37 (b) binary numbers. (Hint: Observe that the empty string |
33 are normally not written.) |
38 is not a number. Also observe that leading 0s are |
|
39 normally not written.) |
34 |
40 |
35 \item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and |
41 \item Decide whether the following two regular expressions are |
36 $(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
42 equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot |
|
43 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
37 |
44 |
38 \item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to |
45 \item Given the regular expression $r = (a \cdot b + b)^*$. |
39 $a$ and $b$. Is $r$ nullable? |
46 Compute what the derivative of $r$ is with respect to |
|
47 $a$, $b$ and $c$. Is $r$ nullable? |
40 |
48 |
41 \item Prove that for all regular expressions $r$ we have |
49 \item Prove that for all regular expressions $r$ we have |
42 \begin{center} |
50 |
43 $\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$ |
51 \begin{center} |
|
52 $\textit{nullable}(r) \quad \text{if and only if} |
|
53 \quad [] \in L(r)$ |
44 \end{center} |
54 \end{center} |
45 |
55 |
|
56 Write down clearly in each case what you need to prove and |
|
57 what are the assumptions. |
|
58 |
46 \end{enumerate} |
59 \end{enumerate} |
47 |
60 |
48 \end{document} |
61 \end{document} |
49 |
62 |
50 %%% Local Variables: |
63 %%% Local Variables: |