1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{charter} |
2 \usepackage{../style} |
3 \usepackage{hyperref} |
|
4 \usepackage{amssymb} |
|
5 \usepackage{amsmath} |
|
6 |
3 |
7 \begin{document} |
4 \begin{document} |
8 |
5 |
9 \section*{Homework 2} |
6 \section*{Homework 2} |
10 |
7 |
11 \begin{enumerate} |
8 \begin{enumerate} |
12 \item Review the first handout about sets of strings and read |
9 \item What is the language recognised by the regular expressions |
13 the second handout. Assuming the alphabet is $\{a, b\}$, |
10 $(\varnothing^*)^*$. |
14 decide which of the following equations are true in |
|
15 general for arbitrary languages $A$, $B$ and $C$: |
|
16 |
11 |
17 \begin{eqnarray} |
12 \item Review the first handout about sets of strings and read the |
18 (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\ |
13 second handout. Assuming the alphabet is the set $\{a, b\}$, decide |
19 A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\ |
14 which of the following equations are true in general for arbitrary |
20 A^* @ A^* & =^? & A^*\nonumber\\ |
15 languages $A$, $B$ and $C$: |
21 (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber |
|
22 \end{eqnarray} |
|
23 |
16 |
24 \noindent In case an equation is true, give an explanation; |
17 \begin{eqnarray} |
25 otherwise give a counter-example. |
18 (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\ |
|
19 A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\ |
|
20 A^* @ A^* & =^? & A^*\nonumber\\ |
|
21 (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber |
|
22 \end{eqnarray} |
26 |
23 |
27 \item What is the meaning of a regular expression? Give an |
24 \noindent In case an equation is true, give an explanation; otherwise |
28 inductive definition. |
25 give a counter-example. |
29 |
26 |
30 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 |
27 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 = |
31 = \varnothing$ and $r_3 = a$. How many strings can the |
28 \varnothing$ and $r_3 = a$. How many strings can the regular |
32 regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each |
29 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
33 match? |
|
34 |
30 |
35 |
31 \item Give regular expressions for (a) decimal numbers and for (b) |
36 \item Give regular expressions for (a) decimal numbers and for |
32 binary numbers. (Hint: Observe that the empty string is not a |
37 (b) binary numbers. (Hint: Observe that the empty string |
33 number. Also observe that leading 0s are normally not written.) |
38 is not a number. Also observe that leading 0s are |
|
39 normally not written.) |
|
40 |
34 |
41 \item Decide whether the following two regular expressions are |
35 \item Decide whether the following two regular expressions are |
42 equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot |
36 equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot b)^* \cdot |
43 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
37 a \equiv^? a \cdot (b \cdot a)^*$. |
44 |
38 |
45 \item Given the regular expression $r = (a \cdot b + b)^*$. |
39 \item Given the regular expression $r = (a \cdot b + b)^*$. Compute |
46 Compute what the derivative of $r$ is with respect to |
40 what the derivative of $r$ is with respect to $a$, $b$ and $c$. Is |
47 $a$, $b$ and $c$. Is $r$ nullable? |
41 $r$ nullable? |
48 |
42 |
49 \item Prove that for all regular expressions $r$ we have |
43 \item Prove that for all regular expressions $r$ we have |
50 |
44 |
51 \begin{center} |
45 \begin{center} |
52 $\textit{nullable}(r) \quad \text{if and only if} |
46 $\textit{nullable}(r) \quad \text{if and only if} |
54 \end{center} |
48 \end{center} |
55 |
49 |
56 Write down clearly in each case what you need to prove and |
50 Write down clearly in each case what you need to prove and |
57 what are the assumptions. |
51 what are the assumptions. |
58 |
52 |
|
53 \item Define what is mean by the derivative of a regular expressions |
|
54 with respoect to a character. (Hint: The derivative is defined |
|
55 recursively.) |
|
56 |
|
57 \item Assume the set $Der$ is defined as |
|
58 |
|
59 \begin{center} |
|
60 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
|
61 \end{center} |
|
62 |
|
63 What is the relation between $Der$ and the notion of derivative of |
|
64 regular expressions? |
|
65 |
|
66 \item Give a regular expression over the alphabet $\{a,b\}$ |
|
67 recognising all strings that do not contain any substring $bb$ and |
|
68 end in $a$. |
|
69 |
|
70 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define |
|
71 the same language? |
59 \end{enumerate} |
72 \end{enumerate} |
60 |
73 |
61 \end{document} |
74 \end{document} |
62 |
75 |
63 %%% Local Variables: |
76 %%% Local Variables: |