10 \item What is a regular language?

    10 \item What is a regular language? Are there alternative ways to define this

    11   notion? If yes, give an explanation why they define the same notion.

    12 \item Assume you have an alphabet consisting of the letters

    13 \item Why is every finite set of strings a regular language?

    13       $a$, $b$ and $c$ only. (1) Find a regular expression

    14 

    14       that recognises the two strings $ab$ and $ac$. (2) Find

    15 \item Assume you have an alphabet consisting of the letters $a$, $b$

    15       a regular expression that matches all strings

    16   and $c$ only. (1) Find a regular expression that recognises the two

    16       \emph{except} these two strings. Note, you can only use

    17   strings $ab$ and $ac$. (2) Find a regular expression that matches

    17       regular expressions of the form 

    18   all strings \emph{except} these two strings. Note, you can only use

    19   regular expressions of the form

    19       \begin{center} $r ::=

    21   \begin{center} $r ::=

    20       \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;

    22     \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;

    21       r_1 \cdot r_2 \;|\; r^*$ 

    23     r_1 \cdot r_2 \;|\; r^*$ 

    22       \end{center}

    24   \end{center}

    24 \item Define the function \textit{zeroable} which takes a

    26 \item Define the function \textit{zeroable} which takes a regular

    25       regular expression as argument and returns a boolean.

    27   expression as argument and returns a boolean.  The function should

    26       The function should satisfy the following property:

    28   satisfy the following property:

    28 \begin{center}

    30   \begin{center}

    29 $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$

    31     $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$

    30 \end{center}

    32   \end{center}

    32 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say  $q_0$ and $q_1$.

    34 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two

    33 The starting state is $q_0$ and the final state is $q_1$. The transition

    35   states, say $q_0$ and $q_1$.  The starting state is $q_0$ and the

    34 function is given by

    36   final state is $q_1$. The transition function is given by

    36 \begin{center}

    38   \begin{center}

    37 \begin{tabular}{l}

    39     \begin{tabular}{l}

    38 $(q_0, a) \rightarrow q_0$\\

    40       $(q_0, a) \rightarrow q_0$\\

    39 $(q_0, b) \rightarrow q_1$\\

    41       $(q_0, b) \rightarrow q_1$\\

    40 $(q_1, b) \rightarrow q_1$

    42       $(q_1, b) \rightarrow q_1$

    41 \end{tabular}

    43     \end{tabular}

    42 \end{center}

    44   \end{center}

    44 What is the languages recognised by this automaton?

    46   What is the language recognised by this automaton?

    46 \item Give a non-deterministic finite automaton that can recognise 

    48 \item Give a non-deterministic finite automaton that can recognise the

    47 the language $L(a\cdot (a + b)^* \cdot c)$. 

    49   language $L(a\cdot (a + b)^* \cdot c)$.

    50 \item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,

    55 \item Given the following deterministic finite automata over the

    51 find the corresponding minimal automaton. In case states can be merged,

    56   alphabet $\{a, b\}$, find an automaton that recognises the

    52 state clearly which states can

    57   complement language.  (Hint: Recall that for the algorithm from the

    53 be merged.

    58   lectures, the automaton needs to be in completed form, that is have

    59   a transition for every letter from the alphabet.)

    55 \begin{center}

    61   \begin{center}

    56 \begin{tikzpicture}[scale=3, line width=0.7mm]

    62     \begin{tikzpicture}[scale=2, line width=0.7mm]

    57   \node[state, initial]        (q0) at ( 0,1) {$q_0$};

    63       \node[state, initial]        (q0) at ( 0,1) {$q_0$};

    58   \node[state]                    (q1) at ( 1,1) {$q_1$};

    64       \node[state, accepting]  (q1) at ( 1,1) {$q_1$};

    59   \node[state, accepting] (q4) at ( 2,1) {$q_4$};

    65       \path[->] (q0) edge node[above] {$a$} (q1)

    60   \node[state]                    (q2) at (0.5,0) {$q_2$};

    66                 (q1) edge [loop right] node {$b$} ();

    61   \node[state]                    (q3) at (1.5,0) {$q_3$};

    67     \end{tikzpicture}

    62   \path[->] (q0) edge node[above] {$0$} (q1)

    68   \end{center}

    63                   (q0) edge node[right] {$1$} (q2)

    64                   (q1) edge node[above] {$0$} (q4)

    65                   (q1) edge node[right] {$1$} (q2)

    66                   (q2) edge node[above] {$0$} (q3)

    67                   (q2) edge [loop below] node {$1$} ()

    68                   (q3) edge node[left] {$0$} (q4)

    69                   (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)

    70                   (q4) edge [loop right] node {$0, 1$} ()

    71                   ;

    72 \end{tikzpicture}

    73 \end{center}

    75 \item Define the language $L(M)$ accepted by a deterministic finite automaton $M$.

    70 \item Given the following deterministic finite automaton over the

    71   alphabet $\{0, 1\}$, find the corresponding minimal automaton. In

    72   case states can be merged, state clearly which states can be merged.