\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: +
−