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

\begin{document}

\section*{Homework 3}

\HEADER

\begin{enumerate}
\item The regular expression matchers in Java, Python and Ruby can be
  very slow with some (basic) regular expressions. What is the main
  reason for this inefficient computation?
  
\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
      
  \begin{center} $r ::=
    \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:
%
%  \begin{center}
%    $\textit{zeroable(r)} \;\text{if and only if}\; 
%    L(r) = \{\}$
%  \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 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 automaton $A(\varSigma, 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 following deterministic finite automaton 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{tikzpicture}[>=stealth',very thick,auto,
                        every state/.style={minimum size=0pt,
                        inner sep=2pt,draw=blue!50,very thick,
                        fill=blue!20},scale=2]
      \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
%
%\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.

\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}[>=stealth',very thick,auto,
                        every state/.style={minimum size=0pt,
                        inner sep=2pt,draw=blue!50,very thick,
                        fill=blue!20},scale=2]
      \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 %%\textbf{(Deleted for 2017, 2018, 2019)}
  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}[>=stealth',very thick,auto,
                        every state/.style={minimum size=0pt,
                        inner sep=2pt,draw=blue!50,very thick,
                        fill=blue!20},scale=2]
      \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 finite deterministic automaton over the alphabet $\{a, b\}$:

  \begin{center}
    \begin{tikzpicture}[scale=2,>=stealth',very thick,auto,
                        every state/.style={minimum size=0pt,
                        inner sep=2pt,draw=blue!50,very thick,
                        fill=blue!20}]
      \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^*$.)

\item If a non-deterministic finite automaton (NFA) has
  $n$ states. How many states does a deterministic 
  automaton (DFA) that can recognise the same language
  as the NFA maximal need?

\item Prove that for all regular expressions $r$ we have
      
\begin{center} 
  $\textit{nullable}(r) \quad \text{if and only if} 
  \quad [] \in L(r)$ 
\end{center}

      Write down clearly in each case what you need to prove
      and what are the assumptions. 

  
\item \POSTSCRIPT  
\end{enumerate}

\end{document}

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