1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
2 \usepackage{../style} |
|
3 |
|
4 \newcommand{\solution}[1]{% |
|
5 \begin{quote}\sf% |
|
6 #1% |
|
7 \end{quote}} |
|
8 \renewcommand{\solution}[1]{} |
|
9 |
3 |
10 |
4 \begin{document} |
11 \begin{document} |
5 |
12 |
6 \section*{Homework 2} |
13 \section*{Homework 2} |
7 |
14 |
8 \HEADER |
15 \HEADER |
9 |
16 |
10 \begin{enumerate} |
17 \begin{enumerate} |
11 \item What is the difference between \emph{basic} regular expressions |
18 \item What is the difference between \emph{basic} regular expressions |
12 and \emph{extended} regular expressions? |
19 and \emph{extended} regular expressions? |
|
20 |
|
21 \solution{Basic regular expressions are $\ZERO$, $\ONE$, $c$, $r_1 + r_2$, |
|
22 $r_1 \cdot r_2$, $r^*$. The extended ones are the bounded |
|
23 repetitions, not, etc.} |
13 |
24 |
14 \item What is the language recognised by the regular |
25 \item What is the language recognised by the regular |
15 expressions $(\ZERO^*)^*$. |
26 expressions $(\ZERO^*)^*$. |
|
27 |
|
28 \solution{$L(\ZERO^*{}^*) = \{[]\}$, |
|
29 remember * always includes the empty string} |
16 |
30 |
17 \item Review the first handout about sets of strings and read |
31 \item Review the first handout about sets of strings and read |
18 the second handout. Assuming the alphabet is the set |
32 the second handout. Assuming the alphabet is the set |
19 $\{a, b\}$, decide which of the following equations are |
33 $\{a, b\}$, decide which of the following equations are |
20 true in general for arbitrary languages $A$, $B$ and |
34 true in general for arbitrary languages $A$, $B$ and |
28 \end{eqnarray} |
42 \end{eqnarray} |
29 |
43 |
30 \noindent In case an equation is true, give an |
44 \noindent In case an equation is true, give an |
31 explanation; otherwise give a counter-example. |
45 explanation; otherwise give a counter-example. |
32 |
46 |
|
47 \solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where |
|
48 $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$} |
|
49 |
33 \item Given the regular expressions $r_1 = \ONE$ and $r_2 = |
50 \item Given the regular expressions $r_1 = \ONE$ and $r_2 = |
34 \ZERO$ and $r_3 = a$. How many strings can the regular |
51 \ZERO$ and $r_3 = a$. How many strings can the regular |
35 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
52 expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
|
53 |
|
54 \solution{$r_1$ and $r_2$ can match the empty string only, $r_3$ can |
|
55 match $[]$, $a$, $aa$, ....} |
36 |
56 |
37 \item Give regular expressions for (a) decimal numbers and for |
57 \item Give regular expressions for (a) decimal numbers and for |
38 (b) binary numbers. Hint: Observe that the empty string |
58 (b) binary numbers. Hint: Observe that the empty string |
39 is not a number. Also observe that leading 0s are |
59 is not a number. Also observe that leading 0s are |
40 normally not written---for example the JSON format for numbers |
60 normally not written---for example the JSON format for numbers |
41 explicitly forbids this. |
61 explicitly forbids this. |
42 |
62 |
|
63 \solution{Just numbers without leading 0s: $0 + (1..9)\cdot(0..1)^*$; |
|
64 can be extended to decimal; similar for binary numbers |
|
65 } |
|
66 |
43 \item Decide whether the following two regular expressions are |
67 \item Decide whether the following two regular expressions are |
44 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
68 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
45 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
69 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
|
70 |
|
71 \solution{Both are equivalent, but why the second? Essentially you have to show that each string in one set is in the other. For 2 this means you can do an induction proof that $(ab)^na$ is the same string as $a(ba)^n$, where the former is in the first set and the latter in the second.} |
46 |
72 |
47 \item Given the regular expression $r = (a \cdot b + b)^*$. |
73 \item Given the regular expression $r = (a \cdot b + b)^*$. |
48 Compute what the derivative of $r$ is with respect to |
74 Compute what the derivative of $r$ is with respect to |
49 $a$, $b$ and $c$. Is $r$ nullable? |
75 $a$, $b$ and $c$. Is $r$ nullable? |
50 |
76 |
51 \item Give an argument for why the following holds: |
77 \item Give an argument for why the following holds: |
52 if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$. |
78 if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$. |
|
79 |
|
80 \solution{This was from last week; I just explicitly added it here.} |
53 |
81 |
54 \item Define what is meant by the derivative of a regular |
82 \item Define what is meant by the derivative of a regular |
55 expressions with respect to a character. (Hint: The |
83 expressions with respect to a character. (Hint: The |
56 derivative is defined recursively.) |
84 derivative is defined recursively.) |
57 |
85 |
|
86 \solution{the recursive function for $der$} |
|
87 |
58 \item Assume the set $Der$ is defined as |
88 \item Assume the set $Der$ is defined as |
59 |
89 |
60 \begin{center} |
90 \begin{center} |
61 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
91 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
62 \end{center} |
92 \end{center} |
63 |
93 |
64 What is the relation between $Der$ and the notion of |
94 What is the relation between $Der$ and the notion of |
65 derivative of regular expressions? |
95 derivative of regular expressions? |
66 |
96 |
|
97 \solution{Main property is $L(der\,c\,r) = Der\,c\,(L(r))$.} |
|
98 |
67 \item Give a regular expression over the alphabet $\{a,b\}$ |
99 \item Give a regular expression over the alphabet $\{a,b\}$ |
68 recognising all strings that do not contain any |
100 recognising all strings that do not contain any |
69 substring $bb$ and end in $a$. |
101 substring $bb$ and end in $a$. |
70 |
102 |
|
103 |
|
104 |
71 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + |
105 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + |
72 (b^*\cdot b^+)$ define the same language? |
106 (b^*\cdot b^+)$ define the same language? |
|
107 |
|
108 \solution{No, the first one can match for example abababababbbbb} |
73 |
109 |
74 \item Define the function $zeroable$ by recursion over regular |
110 \item Define the function $zeroable$ by recursion over regular |
75 expressions. This function should satisfy the property |
111 expressions. This function should satisfy the property |
76 |
112 |
77 \[ |
113 \[ |