\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}
\item \textbf{(Deleted for 2017, 2018, 2019)}
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: