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

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

\end{enumerate}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: