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