--- a/hws/hw03.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw03.tex Wed Apr 06 15:55:01 2016 +0100
@@ -9,28 +9,31 @@
\HEADER
\begin{enumerate}
-\item What is a regular language? Are there alternative ways to define this
- notion? If yes, give an explanation why they define the same notion.
+\item What is a regular language? Are there alternative ways
+ to define this notion? If yes, give an explanation why
+ they define the same notion.
\item Why is every finite set of strings a regular language?
-\item Assume you have an alphabet consisting of the letters $a$, $b$
- and $c$ only. (1) Find a regular expression that recognises the two
- strings $ab$ and $ac$. (2) Find a regular expression that matches
- all strings \emph{except} these two strings. Note, you can only use
- regular expressions of the form
+\item Assume you have an alphabet consisting of the letters
+ $a$, $b$ and $c$ only. (1) Find a regular expression
+ that recognises the two strings $ab$ and $ac$. (2) Find
+ a regular expression that matches all strings
+ \emph{except} these two strings. Note, you can only use
+ regular expressions of the form
\begin{center} $r ::=
- \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;
+ \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\;
r_1 \cdot r_2 \;|\; r^*$
\end{center}
-\item Define the function \textit{zeroable} which takes a regular
- expression as argument and returns a boolean. The function should
- satisfy the following property:
+\item Define the function \textit{zeroable} which takes a
+ regular expression as argument and returns a boolean.
+ The function should satisfy the following property:
\begin{center}
- $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
+ $\textit{zeroable(r)} \;\text{if and only if}\;
+ L(r) = \{\}$
\end{center}
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two