\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?
\end{enumerate}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: