author | Christian Urban <christian dot urban at kcl dot ac dot uk> |
Thu, 26 Sep 2013 11:05:54 +0100 | |
changeset 104 | ffde837b1db1 |
parent 102 | 1ab41c59e3d3 |
child 115 | 86c1c049eb3e |
permissions | -rw-r--r-- |
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} |
|
104
ffde837b1db1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
12 |
\item What is the meaning of a regular expression? Give an inductive definition. |
ffde837b1db1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
13 |
|
ffde837b1db1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
14 |
\item Given the regular expressions $r_1 = \epsilon$ and $r_2 = \varnothing$ and $r_3 = a$. |
ffde837b1db1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
15 |
How many strings can the regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match? |
ffde837b1db1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
16 |
|
ffde837b1db1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
17 |
|
22 | 18 |
\item Give regular expressions for (a) decimal numbers and for (b) binary numbers. |
19 |
(Hint: Observe that the empty string is not a number. Also observe that leading 0s |
|
20 |
are normally not written.) |
|
21 |
||
22 |
\item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and |
|
23 |
$(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
|
24 |
||
25 |
\item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to |
|
26 |
$a$ and $b$. Is $r$ nullable? |
|
27 |
||
28 |
\item What is a regular language? |
|
29 |
||
30 |
\item Prove that for all regular expressions $r$ we have |
|
31 |
\begin{center} |
|
32 |
$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$ |
|
33 |
\end{center} |
|
34 |
||
35 |
\end{enumerate} |
|
36 |
||
37 |
\end{document} |
|
38 |
||
39 |
%%% Local Variables: |
|
40 |
%%% mode: latex |
|
41 |
%%% TeX-master: t |
|
42 |
%%% End: |