diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw03.tex
--- a/hws/hw03.tex	Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw03.tex	Fri Oct 10 16:59:22 2014 +0100
@@ -7,77 +7,146 @@
 \section*{Homework 3}
 
 \begin{enumerate}
-\item What is a regular language?
+\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 \;|\;
-      r_1 \cdot r_2 \;|\; r^*$ 
-      \end{center}
+  \begin{center} $r ::=
+    \varnothing \;|\; \epsilon \;|\; 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:
+
+  \begin{center}
+    $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
+  \end{center}
+
+\item Given the alphabet $\{a,b\}$. Draw the automaton that has two
+  states, say $q_0$ and $q_1$.  The starting state is $q_0$ and the
+  final state is $q_1$. The transition function is given by
 
-\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}
+    \begin{tabular}{l}
+      $(q_0, a) \rightarrow q_0$\\
+      $(q_0, b) \rightarrow q_1$\\
+      $(q_1, b) \rightarrow q_1$
+    \end{tabular}
+  \end{center}
 
-\begin{center}
-$\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
-\end{center}
+  What is the language recognised by this automaton?
+
+\item Give a non-deterministic finite automaton that can recognise the
+  language $L(a\cdot (a + b)^* \cdot c)$.
+
+\item Given a deterministic finite automata $A(Q, q_0, F, \delta)$,
+  define which language is recognised by this automaton. Can you 
+  define also the language defined by a non-deterministic automaton?
 
-\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say  $q_0$ and $q_1$.
-The starting state is $q_0$ and the final state is $q_1$. The transition
-function is given by
+\item Given the following deterministic finite automata over the
+  alphabet $\{a, b\}$, find an automaton that recognises the
+  complement language.  (Hint: Recall that for the algorithm from the
+  lectures, the automaton needs to be in completed form, that is have
+  a transition for every letter from the alphabet.)
 
-\begin{center}
-\begin{tabular}{l}
-$(q_0, a) \rightarrow q_0$\\
-$(q_0, b) \rightarrow q_1$\\
-$(q_1, b) \rightarrow q_1$
-\end{tabular}
-\end{center}
+  \begin{center}
+    \begin{tikzpicture}[scale=2, line width=0.7mm]
+      \node[state, initial]        (q0) at ( 0,1) {$q_0$};
+      \node[state, accepting]  (q1) at ( 1,1) {$q_1$};
+      \path[->] (q0) edge node[above] {$a$} (q1)
+                (q1) edge [loop right] node {$b$} ();
+    \end{tikzpicture}
+  \end{center}
+
+\item Given the following deterministic finite automaton over the
+  alphabet $\{0, 1\}$, find the corresponding minimal automaton. In
+  case states can be merged, state clearly which states can be merged.
 
-What is the languages recognised by this automaton?
-
-\item Give a non-deterministic finite automaton that can recognise 
-the language $L(a\cdot (a + b)^* \cdot c)$. 
+  \begin{center}
+    \begin{tikzpicture}[scale=2, line width=0.7mm]
+      \node[state, initial]        (q0) at ( 0,1) {$q_0$};
+      \node[state]                    (q1) at ( 1,1) {$q_1$};
+      \node[state, accepting] (q4) at ( 2,1) {$q_4$};
+      \node[state]                    (q2) at (0.5,0) {$q_2$};
+      \node[state]                    (q3) at (1.5,0) {$q_3$};
+      \path[->] (q0) edge node[above] {$0$} (q1)
+                (q0) edge node[right] {$1$} (q2)
+                (q1) edge node[above] {$0$} (q4)
+                (q1) edge node[right] {$1$} (q2)
+                (q2) edge node[above] {$0$} (q3)
+                (q2) edge [loop below] node {$1$} ()
+                (q3) edge node[left] {$0$} (q4)
+                (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
+                (q4) edge [loop right] node {$0, 1$} ();
+    \end{tikzpicture}
+  \end{center}
 
-
-\item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,
-find the corresponding minimal automaton. In case states can be merged,
-state clearly which states can
-be merged.
+%\item Given the following deterministic finite automaton
+%
+%\begin{center}
+%\begin{tikzpicture}[scale=3, line width=0.7mm]
+%  \node[state, initial]        (q0) at ( 0,1) {$q_0$};
+%  \node[state,accepting]  (q1) at ( 1,1) {$q_1$};
+%  \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+%  \path[->] (q0) edge node[above] {$b$} (q1)
+%                  (q1) edge [loop above] node[above] {$a$} ()
+%                  (q2) edge [loop above] node[above] {$a, b$} ()
+%                  (q1) edge node[above] {$b$} (q2)
+%                  (q0) edge[bend right] node[below] {$a$} (q2)
+%                  ;
+%\end{tikzpicture}
+%\end{center}
+%find the corresponding minimal automaton. State clearly which nodes
+%can be merged.
 
-\begin{center}
-\begin{tikzpicture}[scale=3, line width=0.7mm]
-  \node[state, initial]        (q0) at ( 0,1) {$q_0$};
-  \node[state]                    (q1) at ( 1,1) {$q_1$};
-  \node[state, accepting] (q4) at ( 2,1) {$q_4$};
-  \node[state]                    (q2) at (0.5,0) {$q_2$};
-  \node[state]                    (q3) at (1.5,0) {$q_3$};
-  \path[->] (q0) edge node[above] {$0$} (q1)
-                  (q0) edge node[right] {$1$} (q2)
-                  (q1) edge node[above] {$0$} (q4)
-                  (q1) edge node[right] {$1$} (q2)
-                  (q2) edge node[above] {$0$} (q3)
-                  (q2) edge [loop below] node {$1$} ()
-                  (q3) edge node[left] {$0$} (q4)
-                  (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
-                  (q4) edge [loop right] node {$0, 1$} ()
-                  ;
-\end{tikzpicture}
-\end{center}
+\item Given the following non-deterministic finite automaton over the
+  alphabet $\{a, b\}$, find a deterministic finite automaton that
+  recognises the same language:
+
+  \begin{center}
+    \begin{tikzpicture}[scale=3, line width=0.7mm]
+      \node[state, initial]        (q0) at ( 0,1) {$q_0$};
+      \node[state]                    (q1) at ( 1,1) {$q_1$};
+      \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+      \path[->] (q0) edge node[above] {$a$} (q1)
+                (q0) edge [loop above] node[above] {$b$} ()
+                (q0) edge [loop below] node[below] {$a$} ()
+                (q1) edge node[above] {$a$} (q2);
+    \end{tikzpicture}
+  \end{center}
+
+\item Given the following finite deterministic automaton over the alphabet $\{a, b\}$:
 
-\item Define the language $L(M)$ accepted by a deterministic finite automaton $M$.
+  \begin{center}
+    \begin{tikzpicture}[scale=2, line width=0.5mm]
+      \node[state, initial, accepting]        (q0) at ( 0,1) {$q_0$};
+      \node[state, accepting]                    (q1) at ( 1,1) {$q_1$};
+      \node[state] (q2) at ( 2,1) {$q_2$};
+      \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
+                (q1) edge[bend left] node[above] {$b$} (q0)
+                (q2) edge[bend left=50] node[below] {$b$} (q0)
+                (q1) edge node[above] {$a$} (q2)
+                (q2) edge [loop right] node {$a$} ()
+                (q0) edge [loop below] node {$b$} ()
+            ;
+    \end{tikzpicture}
+  \end{center}
 
+  Give a regular expression that can recognise the same language as
+  this automaton. (Hint: If you use Brzozwski's method, you can assume
+  Arden's lemma which states that an equation of the form $q = q\cdot r + s$
+  has the unique solution $q = s \cdot r^*$.)
 \end{enumerate}
 
-
-
 \end{document}
 
 %%% Local Variables: