diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw03.tex --- 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