equal
deleted
inserted
replaced
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. |
|
13 Assuming the alphabet is $\{a, b\}$, decide which of the following equations are true |
|
14 in general for arbitrary languages $A$, $B$ and $C$: |
|
15 \begin{eqnarray} |
|
16 (A \cup B) @ C & = & A @ C \cup B @ C\nonumber\\ |
|
17 A^* \cup B^* & = & (A \cup B)^*\nonumber\\ |
|
18 A^* @ A^* & = & A^*\nonumber\\ |
|
19 (A \cap B)@ C & = & (A@C) \cap (B@C)\nonumber |
|
20 \end{eqnarray} |
|
21 |
|
22 \noindent |
|
23 In case an equation is true, give an explanation; otherwise give a counter-example. |
|
24 |
12 \item What is the meaning of a regular expression? Give an inductive definition. |
25 \item What is the meaning of a regular expression? Give an inductive definition. |
13 |
26 |
14 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 = \varnothing$ and $r_3 = a$. |
27 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 = \varnothing$ and $r_3 = a$. |
15 How many strings can the regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
28 How many strings can the regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
16 |
29 |