31
|
1 |
\documentclass{article}
|
|
2 |
\usepackage{charter}
|
|
3 |
\usepackage{hyperref}
|
|
4 |
\usepackage{amssymb}
|
|
5 |
\usepackage{amsmath}
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
6 |
\usepackage{tikz}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
\usetikzlibrary{automata}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
|
31
|
9 |
|
32
|
10 |
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
|
|
11 |
|
31
|
12 |
\begin{document}
|
|
13 |
|
|
14 |
\section*{Homework 4}
|
|
15 |
|
|
16 |
\begin{enumerate}
|
34
|
17 |
\item Why is every finite set of strings a regular language?
|
|
18 |
|
42
|
19 |
\item What is the language recognised by the regular expressions $(\varnothing^*)^*$.
|
34
|
20 |
|
166
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
\item If a regular expression $r$ does not contain any occurrence of $\varnothing$,
|
42
|
22 |
is it possible for $L(r)$ to be empty?
|
32
|
23 |
|
|
24 |
\item Assume that $s^{-1}$ stands for the operation of reversing a
|
|
25 |
string $s$. Given the following \emph{reversing} function on regular
|
|
26 |
expressions
|
|
27 |
|
34
|
28 |
\begin{center}
|
|
29 |
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
|
|
30 |
$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
|
|
31 |
$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
|
|
32 |
$rev(c)$ & $\dn$ & $c$\\
|
|
33 |
$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
|
|
34 |
$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
|
|
35 |
$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
|
|
36 |
\end{tabular}
|
|
37 |
\end{center}
|
|
38 |
|
|
39 |
|
32
|
40 |
and the set
|
|
41 |
|
31
|
42 |
\begin{center}
|
32
|
43 |
$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
|
31
|
44 |
\end{center}
|
|
45 |
|
34
|
46 |
prove whether
|
32
|
47 |
|
31
|
48 |
\begin{center}
|
32
|
49 |
$L(rev(r)) = Rev (L(r))$
|
31
|
50 |
\end{center}
|
|
51 |
|
32
|
52 |
holds.
|
31
|
53 |
|
42
|
54 |
\item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings
|
|
55 |
that do not contain any substring $bb$ and end in $a$.
|
|
56 |
|
|
57 |
\item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}.
|
|
58 |
Give a regular expression that can recognise comments
|
|
59 |
of the form
|
|
60 |
|
|
61 |
\begin{center}
|
|
62 |
\texttt{$\slash$*~\ldots{}~*$\slash$}
|
|
63 |
\end{center}
|
|
64 |
|
|
65 |
where the three dots stand for arbitrary characters, but not comment delimiters.
|
|
66 |
(Hint: You can assume you are already given a regular expression written \texttt{ALL},
|
55
|
67 |
that can recognise any character, and a regular expression \texttt{NOT} that recognises
|
|
68 |
the complement of a regular expression.)
|
42
|
69 |
|
45
|
70 |
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$.
|
42
|
71 |
The starting state is $q_0$ and the final state is $q_1$. The transition
|
|
72 |
function is given by
|
|
73 |
|
|
74 |
\begin{center}
|
|
75 |
\begin{tabular}{l}
|
|
76 |
$(q_0, a) \rightarrow q_0$\\
|
|
77 |
$(q_0, b) \rightarrow q_1$\\
|
|
78 |
$(q_1, b) \rightarrow q_1$
|
|
79 |
\end{tabular}
|
|
80 |
\end{center}
|
|
81 |
|
|
82 |
What is the languages recognised by this automaton?
|
|
83 |
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
\item Give a non-deterministic finite automaton that can recognise
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
the language $L(a\cdot (a + b)^* \cdot c)$.
|
42
|
86 |
|
31
|
87 |
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
\item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
find the corresponding minimal automaton. In case states can be merged,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
state clearly which states can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
be merged.
|
31
|
92 |
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
\begin{tikzpicture}[scale=3, line width=0.7mm]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
\node[state, initial] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
\node[state] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
\node[state, accepting] (q4) at ( 2,1) {$q_4$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
\node[state] (q2) at (0.5,0) {$q_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
\node[state] (q3) at (1.5,0) {$q_3$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
\path[->] (q0) edge node[above] {$0$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
(q0) edge node[right] {$1$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
(q1) edge node[above] {$0$} (q4)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
(q1) edge node[right] {$1$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
(q2) edge node[above] {$0$} (q3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
(q2) edge [loop below] node {$1$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
(q3) edge node[left] {$0$} (q4)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
(q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
(q4) edge [loop right] node {$0, 1$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
%\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
%argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
%that it filters out all comments and whitespace from the result.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
%\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
%implements the \texttt{findAll} function. This function takes a regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
%expressions and a string, and returns all substrings in this string that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
%match the regular expression.
|
31
|
122 |
\end{enumerate}
|
|
123 |
|
42
|
124 |
% explain what is a context-free grammar and the language it generates
|
|
125 |
%
|
|
126 |
%
|
|
127 |
% Define the language L(M) accepted by a deterministic finite automaton M.
|
|
128 |
%
|
|
129 |
%
|
|
130 |
% does (a + b)*b+ and (a*b+) + (b*b+) define the same language
|
43
|
131 |
|
31
|
132 |
|
|
133 |
\end{document}
|
|
134 |
|
|
135 |
%%% Local Variables:
|
|
136 |
%%% mode: latex
|
|
137 |
%%% TeX-master: t
|
|
138 |
%%% End:
|