\documentclass{article}

\usepackage{../style}

\usepackage{../graphics}

\begin{document}

\section*{Homework 3}

\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 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(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 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: