22
|
1 |
\documentclass{article}
|
|
2 |
\usepackage{charter}
|
|
3 |
\usepackage{hyperref}
|
|
4 |
\usepackage{amssymb}
|
|
5 |
\usepackage{amsmath}
|
|
6 |
|
|
7 |
\begin{document}
|
|
8 |
|
|
9 |
\section*{Homework 2}
|
|
10 |
|
|
11 |
\begin{enumerate}
|
115
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
\item Review the first handout about sets of strings and read the second handout.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
Assuming the alphabet is $\{a, b\}$, decide which of the following equations are true
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
in general for arbitrary languages $A$, $B$ and $C$:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
\begin{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
(A \cup B) @ C & = & A @ C \cup B @ C\nonumber\\
|
132
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
A^* \cup B^* & = & (A \cup B)^*\nonumber\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
A^* @ A^* & = & A^*\nonumber\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
(A \cap B)@ C & = & (A@C) \cap (B@C)\nonumber
|
115
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
\end{eqnarray}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
In case an equation is true, give an explanation; otherwise give a counter-example.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
|
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
\item What is the meaning of a regular expression? Give an inductive definition.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
\item Given the regular expressions $r_1 = \epsilon$ and $r_2 = \varnothing$ and $r_3 = a$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
How many strings can the regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
|
22
|
31 |
\item Give regular expressions for (a) decimal numbers and for (b) binary numbers.
|
|
32 |
(Hint: Observe that the empty string is not a number. Also observe that leading 0s
|
|
33 |
are normally not written.)
|
|
34 |
|
|
35 |
\item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and
|
|
36 |
$(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
|
|
37 |
|
|
38 |
\item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to
|
|
39 |
$a$ and $b$. Is $r$ nullable?
|
|
40 |
|
|
41 |
\item Prove that for all regular expressions $r$ we have
|
|
42 |
\begin{center}
|
|
43 |
$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$
|
|
44 |
\end{center}
|
|
45 |
|
|
46 |
\end{enumerate}
|
|
47 |
|
|
48 |
\end{document}
|
|
49 |
|
|
50 |
%%% Local Variables:
|
|
51 |
%%% mode: latex
|
|
52 |
%%% TeX-master: t
|
|
53 |
%%% End:
|