|
23
|
1 |
\documentclass{article}
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../graphics}
|
|
23
|
4 |
|
|
|
5 |
\begin{document}
|
|
|
6 |
|
|
|
7 |
\section*{Homework 3}
|
|
|
8 |
|
|
|
9 |
\begin{enumerate}
|
132
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
\item What is a regular language?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
\item Assume you have an alphabet consisting of the letters
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
$a$, $b$ and $c$ only. (1) Find a regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
that recognises the two strings $ab$ and $ac$. (2) Find
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
a regular expression that matches all strings
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
\emph{except} these two strings. Note, you can only use
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
regular expressions of the form
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
\begin{center} $r ::=
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
\varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
r_1 \cdot r_2 \;|\; r^*$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
\item Define the function \textit{zeroable} which takes a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
regular expression as argument and returns a boolean.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
The function should satisfy the following property:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
|
|
23
|
28 |
\begin{center}
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
$\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
|
|
23
|
30 |
\end{center}
|
|
|
31 |
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
The starting state is $q_0$ and the final state is $q_1$. The transition
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
function is given by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
\begin{tabular}{l}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
$(q_0, a) \rightarrow q_0$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
$(q_0, b) \rightarrow q_1$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
$(q_1, b) \rightarrow q_1$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
What is the languages recognised by this automaton?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
\item Give a non-deterministic finite automaton that can recognise
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
the language $L(a\cdot (a + b)^* \cdot c)$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
|
|
27
|
49 |
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
\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
|
51 |
find the corresponding minimal automaton. In case states can be merged,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
state clearly which states can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
be merged.
|
|
31
|
54 |
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
\begin{tikzpicture}[scale=3, line width=0.7mm]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
\node[state, initial] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
\node[state] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
\node[state, accepting] (q4) at ( 2,1) {$q_4$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
\node[state] (q2) at (0.5,0) {$q_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
\node[state] (q3) at (1.5,0) {$q_3$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
\path[->] (q0) edge node[above] {$0$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
(q0) edge node[right] {$1$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
(q1) edge node[above] {$0$} (q4)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
(q1) edge node[right] {$1$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
(q2) edge node[above] {$0$} (q3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
(q2) edge [loop below] node {$1$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
(q3) edge node[left] {$0$} (q4)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
(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
|
70 |
(q4) edge [loop right] node {$0, 1$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
\item Define the language $L(M)$ accepted by a deterministic finite automaton $M$.
|
|
31
|
76 |
|
|
23
|
77 |
\end{enumerate}
|
|
|
78 |
|
|
31
|
79 |
|
|
27
|
80 |
|
|
23
|
81 |
\end{document}
|
|
|
82 |
|
|
|
83 |
%%% Local Variables:
|
|
|
84 |
%%% mode: latex
|
|
|
85 |
%%% TeX-master: t
|
|
|
86 |
%%% End:
|