\documentclass{article}+ −
\usepackage{charter}+ −
\usepackage{hyperref}+ −
\usepackage{amssymb}+ −
\usepackage{amsmath}+ −
+ −
\begin{document}+ −
+ −
\section*{Homework 2}+ −
+ −
\begin{enumerate}+ −
\item Give regular expressions for (a) decimal numbers and for (b) binary numbers. + −
(Hint: Observe that the empty string is not a number. Also observe that leading 0s + −
are normally not written.)+ −
+ −
\item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and + −
$(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.+ −
+ −
\item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to+ −
$a$ and $b$. Is $r$ nullable?+ −
+ −
\item What is a regular language?+ −
+ −
\item Prove that for all regular expressions $r$ we have+ −
\begin{center}+ −
$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$+ −
\end{center}+ −
+ −
\end{enumerate}+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −