\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 4}

\begin{enumerate}

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

\item What is the language recognised by the regular expressions $(\varnothing^*)^*$.

\item If a regular expression $r$ does not contain any occurrence of $\varnothing$,  

is it possible for $L(r)$ to be empty?

\item Assume that $s^{-1}$ stands for the operation of reversing a

string $s$. Given the following \emph{reversing} function on regular 

expressions

\begin{center}

\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

$rev(\varnothing)$   & $\dn$ & $\varnothing$\\

$rev(\epsilon)$         & $\dn$ & $\epsilon$\\

$rev(c)$                      & $\dn$ & $c$\\

$rev(r_1 + r_2)$        & $\dn$ & $rev(r_1) + rev(r_2)$\\

$rev(r_1 \cdot r_2)$  & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\

$rev(r^*)$                   & $\dn$ & $rev(r)^*$\\

\end{tabular}

\end{center}

and the set

\begin{center}

$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$

\end{center}

prove whether

\begin{center}

$L(rev(r)) = Rev (L(r))$

\end{center}

holds.

\item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings 

that do not contain any substring $bb$ and end in $a$.

\item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}.

Give a regular expression that can recognise comments

of the form 

\begin{center}

\texttt{$\slash$*~\ldots{}~*$\slash$} 

\end{center}

where the three dots stand for arbitrary characters, but not comment delimiters.

(Hint: You can assume you are already given a regular expression written \texttt{ALL},

that can recognise any character, and a regular expression \texttt{NOT} that recognises

the complement of a regular expression.)

\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 languages 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 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}[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] (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 (Optional) The tokenizer in \texttt{regexp3.scala} takes as

%argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so 

%that it filters out all comments and whitespace from the result.

%\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it

%implements the \texttt{findAll} function. This function takes a regular

%expressions and a string, and returns all substrings in this string that 

%match the regular expression.

\end{enumerate}

% explain what is a context-free grammar and the language it generates 

%

%

% Define the language L(M) accepted by a deterministic finite automaton M.

%

%

% does (a + b)*b+ and (a*b+) + (b*b+) define the same language

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: