\documentclass{article}+
−
\usepackage{charter}+
−
\usepackage{hyperref}+
−
\usepackage{amssymb}+
−
\usepackage{amsmath}+
−
+
−
\begin{document}+
−
+
−
\section*{Homework 2}+
−
+
−
\begin{enumerate}+
−
\item Review the first handout about sets of strings and read+
−
      the second handout. Assuming the alphabet is $\{a, b\}$,+
−
      decide which of the following equations are true in+
−
      general for arbitrary languages $A$, $B$ and $C$:+
−
+
−
\begin{eqnarray}+
−
(A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\+
−
A^* \cup B^*   & =^? & (A \cup B)^*\nonumber\\+
−
A^* @ A^*      & =^? & A^*\nonumber\\+
−
(A \cap B)@ C  & =^? & (A@C) \cap (B@C)\nonumber+
−
\end{eqnarray}+
−
+
−
\noindent In case an equation is true, give an explanation;+
−
otherwise give a counter-example.+
−
+
−
\item What is the meaning of a regular expression? Give an+
−
      inductive definition.+
−
+
−
\item Given the regular expressions $r_1 = \epsilon$ and $r_2+
−
      = \varnothing$ and $r_3 = a$. How many strings can the+
−
      regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each+
−
      match?+
−
+
−
+
−
\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$, $b$ and $c$. Is $r$ nullable?+
−
+
−
\item Prove that for all regular expressions $r$ we have+
−
      +
−
\begin{center} +
−
  $\textit{nullable}(r) \quad \text{if and only if} +
−
  \quad [] \in L(r)$ +
−
\end{center}+
−
+
−
  Write down clearly in each case what you need to prove and+
−
  what are the assumptions. +
−
  +
−
\end{enumerate}+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−