\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}

\begin{document}

\section*{Homework 3}

\begin{enumerate}
\item What is 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 
      
      \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

\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}

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)$. 


\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.

\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 Define the language $L(M)$ accepted by a deterministic finite automaton $M$.

\end{enumerate}



\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: