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