\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{automata}

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

\begin{document}

\section*{Homework 5}

\begin{enumerate}
\item Define the following regular expressions 

\begin{center}
\begin{tabular}{ll}
$r^+$ & (one or more matches)\\
$r^?$   & (zero or one match)\\
$r^{\{n\}}$ & (exactly $n$ matches)\\
$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
&  \phantom{(}assumption $m \le n$)\\
\end{tabular}
\end{center}

in terms of the usual regular expressions

\begin{center}
$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
\end{center}

\item Given a deterministic finite automata $A(Q, q_0, F, \delta)$, 
define which language is recognised by this automaton.

\item Given the following deterministic finite automata 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}[scale=3, line width=0.7mm]
  \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}[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] (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 finite deterministic automaton over the alphabet $\{a, b\}$:

\begin{center}
\begin{tikzpicture}[scale=2, line width=0.5mm]
  \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 Recall the definitions for $Der$ and $der$ from the lectures. 
Prove by induction on $r$ the property that 

\[
L(der\,c\,r) = Der\,c\,(L(r))
\]

holds.
\end{enumerate}

\end{document}

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