hws/hw02.tex
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--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
22
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     1
\documentclass{article}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
\usepackage{charter}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
\usepackage{hyperref}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     4
\usepackage{amssymb}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     5
\usepackage{amsmath}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
\begin{document}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
\section*{Homework 2}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    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
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    18
\item Give regular expressions for (a) decimal numbers and for (b) binary numbers. 
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
(Hint: Observe that the empty string is not a number. Also observe that leading 0s 
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    20
are normally not written.)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    21
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
\item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and 
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    23
$(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
\item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    26
$a$ and $b$. Is $r$ nullable?
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    27
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
\item What is a regular language?
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    30
\item Prove that for all regular expressions $r$ we have
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    31
\begin{center}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    33
\end{center}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    34
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    35
\end{enumerate}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    36
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    37
\end{document}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    38
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    39
%%% Local Variables: 
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    40
%%% mode: latex
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    41
%%% TeX-master: t
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    42
%%% End: