22
+ − 1
\documentclass{article}
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 2
\usepackage{../style}
889
+ − 3
\usepackage{../graphicss}
+ − 4
22
+ − 5
\begin{document}
+ − 6
+ − 7
\section*{Homework 2}
+ − 8
916
+ − 9
%\HEADER
347
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 10
22
+ − 11
\begin{enumerate}
499
+ − 12
\item What is the difference between \emph{basic} regular expressions
885
+ − 13
and \emph{extended} regular expressions?
+ − 14
+ − 15
\solution{Basic regular expressions are $\ZERO$, $\ONE$, $c$, $r_1 + r_2$,
+ − 16
$r_1 \cdot r_2$, $r^*$. The extended ones are the bounded
+ − 17
repetitions, not, etc.}
499
+ − 18
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 19
\item What is the language recognised by the regular
885
+ − 20
expressions $(\ZERO^*)^*$.
+ − 21
+ − 22
\solution{$L(\ZERO^*{}^*) = \{[]\}$,
+ − 23
remember * always includes the empty string}
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 24
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 25
\item Review the first handout about sets of strings and read
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 26
the second handout. Assuming the alphabet is the set
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 27
$\{a, b\}$, decide which of the following equations are
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 28
true in general for arbitrary languages $A$, $B$ and
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 29
$C$:
115
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 30
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 31
\begin{eqnarray}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 32
(A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 33
A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 34
A^* @ A^* & =^? & A^*\nonumber\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 35
(A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 36
\end{eqnarray}
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 37
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 38
\noindent In case an equation is true, give an
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 39
explanation; otherwise give a counter-example.
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 40
885
+ − 41
\solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where
889
+ − 42
$A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$\medskip
+ − 43
+ − 44
For equations like 3 it is always a god idea to prove the
+ − 45
two inclusions
+ − 46
+ − 47
\[
+ − 48
A^* \subseteq A^* @ A^* \qquad
+ − 49
A^* @ A^* \subseteq A^*
+ − 50
\]
+ − 51
+ − 52
This means for every string $s$ we have to show
+ − 53
+ − 54
\[
+ − 55
s \in A^* \;\textit{implies}\; s \in A^* @ A^* \qquad
+ − 56
s \in A^* @ A^* \;\textit{implies}\; s \in A^*
+ − 57
\]
+ − 58
+ − 59
The first one is easy because $[] \in A^*$ and therefore
+ − 60
$s @ [] \in A^* @ A^*$.
+ − 61
+ − 62
The second one says that $s$ must be of the form $s = s_1 @ s_2$ with
+ − 63
$s_1 \in A^*$ and $s_2 \in A^*$. We have to show that
+ − 64
$s_1 @ s_2 \in A^*$.
+ − 65
+ − 66
If $s_1 \in A^*$ then there exists an $n$ such that $s_1 \in A^n$, and
+ − 67
if $s_2 \in A^*$ then there exists an $m$ such that $s_2 \in A^m$.\bigskip
+ − 68
+ − 69
+ − 70
Aside: We are going to show that
+ − 71
+ − 72
\[
+ − 73
A^n \,@\, A^m = A^{n+m}
+ − 74
\]
+ − 75
+ − 76
We prove that by induction on $n$.
+ − 77
+ − 78
Case $n = 0$: $A^0 \,@\, A^m = A^{0+m}$ holds because $A^0 = \{[]\}$
+ − 79
and $\{[]\} \,@\, A^m = A ^ m$ and $0 + m = m$.\medskip
+ − 80
+ − 81
Case $n + 1$: The induction hypothesis is
+ − 82
+ − 83
\[ A^n \,@\, A^m = A^{n+m}
+ − 84
\]
+ − 85
+ − 86
We need to prove
+ − 87
+ − 88
\[
+ − 89
A^{n+1} \,@\, A^m = A^{(n+1)+m}
+ − 90
\]
+ − 91
+ − 92
The left-hand side is $(A \,@\, A^n) \,@\, A^m$ by the definition of
+ − 93
the power operation. We can rearrange that
+ − 94
to $A \,@\, (A^n \,@\, A^m)$. \footnote{Because for all languages $A$, $B$, $C$ we have $(A @ B) @ C = A @ (B @ C)$.}
+ − 95
+ − 96
By the induction hypothesis we know that $A^n \,@\, A^m = A^{n+m}$.
+ − 97
+ − 98
So we have $A \,@\, (A^{n+m})$. But this is $A^{(n+m)+1}$ again if we
+ − 99
apply the definition of the power operator. If we
+ − 100
rearrange that we get $A^{(n+1)+m}$ and are done with
+ − 101
what we need to prove for the power law.\bigskip
+ − 102
+ − 103
Picking up where we left, we know that $s_1 \in A^n$ and $s_2 \in A^m$. This now implies that $s_1 @ s_2\in A^n @ A^m$. By the power law this means
+ − 104
$s_1 @ s_2\in A^{n+m}$. But this also means $s_1 @ s_2\in A^*$.
+ − 105
}
885
+ − 106
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 107
\item Given the regular expressions $r_1 = \ONE$ and $r_2 =
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 108
\ZERO$ and $r_3 = a$. How many strings can the regular
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 109
expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 110
885
+ − 111
\solution{$r_1$ and $r_2$ can match the empty string only, $r_3$ can
+ − 112
match $[]$, $a$, $aa$, ....}
+ − 113
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 114
\item Give regular expressions for (a) decimal numbers and for
617
+ − 115
(b) binary numbers. Hint: Observe that the empty string
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 116
is not a number. Also observe that leading 0s are
617
+ − 117
normally not written---for example the JSON format for numbers
891
+ − 118
explicitly forbids this. So 007 is not a number according to JSON.
22
+ − 119
885
+ − 120
\solution{Just numbers without leading 0s: $0 + (1..9)\cdot(0..1)^*$;
+ − 121
can be extended to decimal; similar for binary numbers
+ − 122
}
+ − 123
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 124
\item Decide whether the following two regular expressions are
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 125
equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 126
b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
22
+ − 127
885
+ − 128
\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.}
+ − 129
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 130
\item Given the regular expression $r = (a \cdot b + b)^*$.
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 131
Compute what the derivative of $r$ is with respect to
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 132
$a$, $b$ and $c$. Is $r$ nullable?
22
+ − 133
881
+ − 134
\item Give an argument for why the following holds:
885
+ − 135
if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$.
+ − 136
+ − 137
\solution{This was from last week; I just explicitly added it here.}
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 138
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 139
\item Define what is meant by the derivative of a regular
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 140
expressions with respect to a character. (Hint: The
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 141
derivative is defined recursively.)
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 142
885
+ − 143
\solution{the recursive function for $der$}
+ − 144
768
+ − 145
\item Assume the set $Der$ is defined as
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 147
\begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 148
$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 149
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 150
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 151
What is the relation between $Der$ and the notion of
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 152
derivative of regular expressions?
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 153
885
+ − 154
\solution{Main property is $L(der\,c\,r) = Der\,c\,(L(r))$.}
+ − 155
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 156
\item Give a regular expression over the alphabet $\{a,b\}$
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 157
recognising all strings that do not contain any
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 158
substring $bb$ and end in $a$.
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 159
889
+ − 160
\solution{$((ba)^* \cdot (a)^*)^*\,\cdot\,a$}
885
+ − 161
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 162
\item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) +
885
+ − 163
(b^*\cdot b^+)$ define the same language?
+ − 164
889
+ − 165
\solution{No, the first one can match for example abababababbbbb
+ − 166
while the second can only match for example aaaaaabbbbb or bbbbbbb}
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 167
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 168
\item Define the function $zeroable$ by recursion over regular
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 169
expressions. This function should satisfy the property
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 170
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 171
\[
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 172
zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}\qquad(*)
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 173
\]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 174
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 175
The function $nullable$ for the not-regular expressions
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 176
can be defined by
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 178
\[
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 179
nullable(\sim r) \dn \neg(nullable(r))
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 180
\]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 181
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 182
Unfortunately, a similar definition for $zeroable$ does
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 183
not satisfy the property in $(*)$:
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 184
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 185
\[
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 186
zeroable(\sim r) \dn \neg(zeroable(r))
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 187
\]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 188
889
+ − 189
Find a counter example?
+ − 190
+ − 191
+ − 192
\solution{
+ − 193
Here the idea is that nullable for NOT can be defined as
+ − 194
+ − 195
\[nullable(\sim r) \dn \neg(nullable(r))\]
+ − 196
+ − 197
This will satisfy the property
+ − 198
$nullable(r) \;\;\text{if and only if}\;\;[] \in L(r)$. (Remember how
+ − 199
$L(\sim r)$ is defined).\bigskip
+ − 200
+ − 201
But you cannot define
+ − 202
+ − 203
\[zeroable(\sim r) \dn \neg(zeroable(r))\]
+ − 204
+ − 205
because if $r$ for example is $\ONE$ then $\sim \ONE$ can match
+ − 206
some strings (all non-empty strings). So $zeroable$ should be false. But if we follow
+ − 207
the above definition we would obtain $\neg(zeroable(\ONE))$. According
+ − 208
to the definition of $zeroable$ for $\ONE$ this would be false,
+ − 209
but if we now negate false, we get actually true. So the above
+ − 210
definition would not satisfy the property
+ − 211
+ − 212
\[
+ − 213
zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}
+ − 214
\]
+ − 215
}
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 216
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 217
\item Give a regular expressions that can recognise all
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 218
strings from the language $\{a^n\;|\;\exists k.\; n = 3 k
885
+ − 219
+ 1 \}$.
+ − 220
+ − 221
\solution{$a(aaa)^*$}
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 222
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 223
\item Give a regular expression that can recognise an odd
889
+ − 224
number of $a$s or an even number of $b$s.
+ − 225
+ − 226
\solution{
+ − 227
If the a's and b's are meant to be separate, then this is easy
+ − 228
+ − 229
\[a(aa)^* + (bb)^*\]
+ − 230
+ − 231
If the letters are mixed, then this is difficult
+ − 232
+ − 233
\[(aa|bb|(ab|ba)\cdot (aa|bb)^* \cdot (ba|ab))^* \cdot (b|(ab|ba)(bb|aa)^* \cdot a)
+ − 234
\]
+ − 235
+ − 236
(copied from somewhere ;o)
+ − 237
+ − 238
The idea behind it is essentially the DFA
+ − 239
+ − 240
\begin{center}
+ − 241
\begin{tikzpicture}[scale=1,>=stealth',very thick,
+ − 242
every state/.style={minimum size=0pt,
+ − 243
draw=blue!50,very thick,fill=blue!20}]
+ − 244
\node[state,initial] (q0) at (0,2) {$q_0$};
+ − 245
\node[state,accepting] (q1) at (2,2) {$q_1$};
+ − 246
\node[state] (q2) at (0,0) {$q_2$};
+ − 247
\node[state] (q3) at (2,0) {$q_3$};
+ − 248
+ − 249
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
+ − 250
(q1) edge[bend left] node[above] {$a$} (q0)
+ − 251
(q2) edge[bend left] node[above] {$a$} (q3)
+ − 252
(q3) edge[bend left] node[above] {$a$} (q2)
+ − 253
(q0) edge[bend left] node[right] {$b$} (q2)
+ − 254
(q2) edge[bend left] node[left] {$b$} (q0)
+ − 255
(q1) edge[bend left] node[right] {$b$} (q3)
+ − 256
(q3) edge[bend left] node[left] {$b$} (q1);
+ − 257
\end{tikzpicture}
+ − 258
\end{center}
+ − 259
}
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 261
\item \POSTSCRIPT
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 262
\end{enumerate}
22
+ − 263
+ − 264
\end{document}
+ − 265
+ − 266
%%% Local Variables:
+ − 267
%%% mode: latex
+ − 268
%%% TeX-master: t
+ − 269
%%% End: