|
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}
|
|
|
12 |
\item Give regular expressions for (a) decimal numbers and for (b) binary numbers.
|
|
|
13 |
(Hint: Observe that the empty string is not a number. Also observe that leading 0s
|
|
|
14 |
are normally not written.)
|
|
|
15 |
|
|
|
16 |
\item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and
|
|
|
17 |
$(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
|
|
|
18 |
|
|
|
19 |
\item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to
|
|
|
20 |
$a$ and $b$. Is $r$ nullable?
|
|
|
21 |
|
|
|
22 |
\item What is a regular language?
|
|
|
23 |
|
|
|
24 |
\item Prove that for all regular expressions $r$ we have
|
|
|
25 |
\begin{center}
|
|
|
26 |
$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$
|
|
|
27 |
\end{center}
|
|
|
28 |
|
|
|
29 |
\end{enumerate}
|
|
|
30 |
|
|
|
31 |
\end{document}
|
|
|
32 |
|
|
|
33 |
%%% Local Variables:
|
|
|
34 |
%%% mode: latex
|
|
|
35 |
%%% TeX-master: t
|
|
|
36 |
%%% End:
|