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 |
|
347
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
|
23
|
11 |
\begin{enumerate}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
\item What is a regular language? Are there alternative ways
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
to define this notion? If yes, give an explanation why
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
they define the same notion.
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
\item Why is every finite set of strings a regular language?
|
132
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
\item Assume you have an alphabet consisting of the letters
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
$a$, $b$ and $c$ only. (1) Find a regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
that recognises the two strings $ab$ and $ac$. (2) Find
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
a regular expression that matches all strings
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\emph{except} these two strings. Note, you can only use
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
regular expressions of the form
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
\begin{center} $r ::=
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
\ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\;
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
r_1 \cdot r_2 \;|\; r^*$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
\item Define the function \textit{zeroable} which takes a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
regular expression as argument and returns a boolean.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
The function should satisfy the following property:
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
\begin{center}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
$\textit{zeroable(r)} \;\text{if and only if}\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
L(r) = \{\}$
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
states, say $q_0$ and $q_1$. The starting state is $q_0$ and the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
final state is $q_1$. The transition function is given by
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
\begin{tabular}{l}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
$(q_0, a) \rightarrow q_0$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
$(q_0, b) \rightarrow q_1$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
$(q_1, b) \rightarrow q_1$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
\end{center}
|
258
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
What is the language recognised by this automaton?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
\item Give a non-deterministic finite automaton that can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
recognise the language $L(a\cdot (a + b)^* \cdot c)$.
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
\item Given a deterministic finite automaton $A(Q, q_0, F,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
\delta)$, define which language is recognised by this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
automaton. Can you define also the language defined by a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
non-deterministic automaton?
|
23
|
60 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
\item Given the following deterministic finite automaton over
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
the alphabet $\{a, b\}$, find an automaton that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
recognises the complement language. (Hint: Recall that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
for the algorithm from the lectures, the automaton needs
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
to be in completed form, that is have a transition for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
every letter from the alphabet.)
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
\begin{center}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
\begin{tikzpicture}[>=stealth',very thick,auto,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
inner sep=2pt,draw=blue!50,very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
fill=blue!20},scale=2]
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
\node[state, initial] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
\node[state, accepting] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
\path[->] (q0) edge node[above] {$a$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
(q1) edge [loop right] node {$b$} ();
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
%\item Given the following deterministic finite automaton
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
%\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
%\begin{tikzpicture}[scale=3, line width=0.7mm]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
% \node[state, initial] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
% \node[state,accepting] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
% \node[state, accepting] (q2) at ( 2,1) {$q_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
% \path[->] (q0) edge node[above] {$b$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
% (q1) edge [loop above] node[above] {$a$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
% (q2) edge [loop above] node[above] {$a, b$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
% (q1) edge node[above] {$b$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
% (q0) edge[bend right] node[below] {$a$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
% ;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
%\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
%\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
%find the corresponding minimal automaton. State clearly which nodes
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
%can be merged.
|
31
|
99 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
\item Given the following non-deterministic finite automaton
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
over the alphabet $\{a, b\}$, find a deterministic
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
finite automaton that recognises the same language:
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
\begin{center}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
\begin{tikzpicture}[>=stealth',very thick,auto,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
inner sep=2pt,draw=blue!50,very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
fill=blue!20},scale=2]
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
\node[state, initial] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
\node[state] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
\node[state, accepting] (q2) at ( 2,1) {$q_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
\path[->] (q0) edge node[above] {$a$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
(q0) edge [loop above] node[above] {$b$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
(q0) edge [loop below] node[below] {$a$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
(q1) edge node[above] {$a$} (q2);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
|
271
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
\item Given the following deterministic finite automaton over the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
alphabet $\{0, 1\}$, find the corresponding minimal automaton. In
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
case states can be merged, state clearly which states can be merged.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
\begin{center}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
\begin{tikzpicture}[>=stealth',very thick,auto,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
inner sep=2pt,draw=blue!50,very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
fill=blue!20},scale=2]
|
271
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
\node[state, initial] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
\node[state] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
\node[state, accepting] (q4) at ( 2,1) {$q_4$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
\node[state] (q2) at (0.5,0) {$q_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
\node[state] (q3) at (1.5,0) {$q_3$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
\path[->] (q0) edge node[above] {$0$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
(q0) edge node[right] {$1$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
(q1) edge node[above] {$0$} (q4)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
(q1) edge node[right] {$1$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
(q2) edge node[above] {$0$} (q3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
(q2) edge [loop below] node {$1$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
(q3) edge node[left] {$0$} (q4)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
(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
|
141 |
(q4) edge [loop right] node {$0, 1$} ();
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
143 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
\item Given the following finite deterministic automaton over the alphabet $\{a, b\}$:
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
\begin{center}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
\begin{tikzpicture}[scale=2,>=stealth',very thick,auto,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
every state/.style={minimum size=0pt,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
150 |
inner sep=2pt,draw=blue!50,very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
fill=blue!20}]
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
\node[state, initial, accepting] (q0) at ( 0,1) {$q_0$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
\node[state, accepting] (q1) at ( 1,1) {$q_1$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
\node[state] (q2) at ( 2,1) {$q_2$};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
(q1) edge[bend left] node[above] {$b$} (q0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
(q2) edge[bend left=50] node[below] {$b$} (q0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
(q1) edge node[above] {$a$} (q2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
(q2) edge [loop right] node {$a$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
(q0) edge [loop below] node {$b$} ()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
\end{center}
|
31
|
164 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
Give a regular expression that can recognise the same language as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
this automaton. (Hint: If you use Brzozwski's method, you can assume
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
Arden's lemma which states that an equation of the form $q = q\cdot r + s$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
has the unique solution $q = s \cdot r^*$.)
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
\item If a non-deterministic finite automaton (NFA) has
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
$n$ states. How many states does a deterministic
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
automaton (DFA) that can recognise the same language
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
as the NFA maximal need?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
|
23
|
175 |
\end{enumerate}
|
|
176 |
|
|
177 |
\end{document}
|
|
178 |
|
|
179 |
%%% Local Variables:
|
|
180 |
%%% mode: latex
|
|
181 |
%%% TeX-master: t
|
|
182 |
%%% End:
|