6 \section*{Homework 2} |
6 \section*{Homework 2} |
7 |
7 |
8 \HEADER |
8 \HEADER |
9 |
9 |
10 \begin{enumerate} |
10 \begin{enumerate} |
11 \item What is the language recognised by the regular expressions |
|
12 $(\varnothing^*)^*$. |
|
13 |
11 |
14 \item Review the first handout about sets of strings and read the |
12 \item What is the language recognised by the regular |
15 second handout. Assuming the alphabet is the set $\{a, b\}$, decide |
13 expressions $(\ZERO^*)^*$. |
16 which of the following equations are true in general for arbitrary |
|
17 languages $A$, $B$ and $C$: |
|
18 |
14 |
19 \begin{eqnarray} |
15 \item Review the first handout about sets of strings and read |
20 (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\ |
16 the second handout. Assuming the alphabet is the set |
21 A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\ |
17 $\{a, b\}$, decide which of the following equations are |
22 A^* @ A^* & =^? & A^*\nonumber\\ |
18 true in general for arbitrary languages $A$, $B$ and |
23 (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber |
19 $C$: |
24 \end{eqnarray} |
|
25 |
20 |
26 \noindent In case an equation is true, give an explanation; otherwise |
21 \begin{eqnarray} |
27 give a counter-example. |
22 (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\ |
|
23 A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\ |
|
24 A^* @ A^* & =^? & A^*\nonumber\\ |
|
25 (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber |
|
26 \end{eqnarray} |
28 |
27 |
29 \item Given the regular expressions $r_1 = \epsilon$ and $r_2 = |
28 \noindent In case an equation is true, give an |
30 \varnothing$ and $r_3 = a$. How many strings can the regular |
29 explanation; otherwise give a counter-example. |
31 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
|
32 |
30 |
33 \item Give regular expressions for (a) decimal numbers and for (b) |
31 \item Given the regular expressions $r_1 = \ONE$ and $r_2 = |
34 binary numbers. (Hint: Observe that the empty string is not a |
32 \ZERO$ and $r_3 = a$. How many strings can the regular |
35 number. Also observe that leading 0s are normally not written.) |
33 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
|
34 |
|
35 \item Give regular expressions for (a) decimal numbers and for |
|
36 (b) binary numbers. (Hint: Observe that the empty string |
|
37 is not a number. Also observe that leading 0s are |
|
38 normally not written.) |
36 |
39 |
37 \item Decide whether the following two regular expressions are |
40 \item Decide whether the following two regular expressions are |
38 equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot b)^* \cdot |
41 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
39 a \equiv^? a \cdot (b \cdot a)^*$. |
42 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
40 |
43 |
41 \item Given the regular expression $r = (a \cdot b + b)^*$. Compute |
44 \item Given the regular expression $r = (a \cdot b + b)^*$. |
42 what the derivative of $r$ is with respect to $a$, $b$ and $c$. Is |
45 Compute what the derivative of $r$ is with respect to |
43 $r$ nullable? |
46 $a$, $b$ and $c$. Is $r$ nullable? |
44 |
47 |
45 \item Prove that for all regular expressions $r$ we have |
48 \item Prove that for all regular expressions $r$ we have |
46 |
49 |
47 \begin{center} |
50 \begin{center} |
48 $\textit{nullable}(r) \quad \text{if and only if} |
51 $\textit{nullable}(r) \quad \text{if and only if} |
49 \quad [] \in L(r)$ |
52 \quad [] \in L(r)$ |
50 \end{center} |
53 \end{center} |
51 |
54 |
52 Write down clearly in each case what you need to prove and |
55 Write down clearly in each case what you need to prove |
53 what are the assumptions. |
56 and what are the assumptions. |
54 |
57 |
55 \item Define what is meant by the derivative of a regular |
58 \item Define what is meant by the derivative of a regular |
56 expressions with respect to a character. (Hint: The |
59 expressions with respect to a character. (Hint: The |
57 derivative is defined recursively.) |
60 derivative is defined recursively.) |
58 |
61 |
60 |
63 |
61 \begin{center} |
64 \begin{center} |
62 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
65 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
63 \end{center} |
66 \end{center} |
64 |
67 |
65 What is the relation between $Der$ and the notion of derivative of |
68 What is the relation between $Der$ and the notion of |
66 regular expressions? |
69 derivative of regular expressions? |
67 |
70 |
68 \item Give a regular expression over the alphabet $\{a,b\}$ |
71 \item Give a regular expression over the alphabet $\{a,b\}$ |
69 recognising all strings that do not contain any substring $bb$ and |
72 recognising all strings that do not contain any |
70 end in $a$. |
73 substring $bb$ and end in $a$. |
71 |
74 |
72 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define |
75 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + |
73 the same language? |
76 (b^*\cdot b^+)$ define the same language? |
74 |
77 |
75 \item Define the function $zeroable$ by recursion over regular |
78 \item Define the function $zeroable$ by recursion over regular |
76 expressions. This function should satisfy the property |
79 expressions. This function should satisfy the property |
77 |
80 |
78 \[ |
81 \[ |
79 zeroable(r) \;\;\text{if and only if}\;\;L(r) = \varnothing\qquad(*) |
82 zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}\qquad(*) |
80 \] |
83 \] |
81 |
84 |
82 The function $nullable$ for the not-regular expressions can be defined |
85 The function $nullable$ for the not-regular expressions |
83 by |
86 can be defined by |
84 |
87 |
85 \[ |
88 \[ |
86 nullable(\sim r) \dn \neg(nullable(r)) |
89 nullable(\sim r) \dn \neg(nullable(r)) |
87 \] |
90 \] |
88 |
91 |
89 Unfortunately, a similar definition for $zeroable$ does not satisfy |
92 Unfortunately, a similar definition for $zeroable$ does |
90 the property in $(*)$: |
93 not satisfy the property in $(*)$: |
91 |
94 |
92 \[ |
95 \[ |
93 zeroable(\sim r) \dn \neg(zeroable(r)) |
96 zeroable(\sim r) \dn \neg(zeroable(r)) |
94 \] |
97 \] |
95 |
98 |
96 Find out why? |
99 Find out why? |
97 |
100 |
98 \item Give a regular expressions that can recognise all strings from the |
101 \item Give a regular expressions that can recognise all |
99 language $\{a^n\;|\;\exists k. n = 3 k + 1 \}$. |
102 strings from the language $\{a^n\;|\;\exists k.\; n = 3 k |
100 \end{enumerate} |
103 + 1 \}$. \end{enumerate} |
101 |
104 |
102 \end{document} |
105 \end{document} |
103 |
106 |
104 %%% Local Variables: |
107 %%% Local Variables: |
105 %%% mode: latex |
108 %%% mode: latex |