author | Christian Urban <christian.urban@kcl.ac.uk> |
Fri, 21 Oct 2022 13:30:12 +0100 | |
changeset 892 | f4df090a84d0 |
parent 778 | 3e5f5d19f514 |
child 916 | 10f834eb0a9e |
permissions | -rw-r--r-- |
23 | 1 |
\documentclass{article} |
264
4deef8ac5d72
uodated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
258
diff
changeset
|
2 |
\usepackage{../style} |
4deef8ac5d72
uodated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
258
diff
changeset
|
3 |
\usepackage{../graphics} |
23 | 4 |
|
892 | 5 |
\newcommand{\solution}[1]{% |
6 |
\begin{quote}\sf% |
|
7 |
#1% |
|
8 |
\end{quote}} |
|
9 |
\renewcommand{\solution}[1]{} |
|
10 |
||
11 |
||
12 |
||
23 | 13 |
\begin{document} |
14 |
||
15 |
\section*{Homework 3} |
|
16 |
||
347
22b5294daa2a
updated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
294
diff
changeset
|
17 |
\HEADER |
22b5294daa2a
updated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
294
diff
changeset
|
18 |
|
23 | 19 |
\begin{enumerate} |
647 | 20 |
\item The regular expression matchers in Java, Python and Ruby can be |
21 |
very slow with some (basic) regular expressions. What is the main |
|
22 |
reason for this inefficient computation? |
|
892 | 23 |
|
24 |
\solution{Many matchers employ DFS type of algorithms to check |
|
25 |
if a string is matched by the regex or not. Such algorithms |
|
26 |
require backtracking if have gone down the wrong path which |
|
27 |
can be very slow. There are also problems with bounded regular |
|
28 |
expressions and backreferences.} |
|
647 | 29 |
|
401
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
30 |
\item What is a regular language? Are there alternative ways |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
31 |
to define this notion? If yes, give an explanation why |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
32 |
they define the same notion. |
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
33 |
|
892 | 34 |
\solution{A regular language is a language for which every string |
35 |
can be recognized by some regular expression. Another definition is |
|
36 |
that it is a language for which a finite automaton can be |
|
37 |
constructed. Both define the same set of languages.} |
|
38 |
||
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
39 |
\item Why is every finite set of strings a regular language? |
132
04264d0c43bb
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
102
diff
changeset
|
40 |
|
892 | 41 |
\solution{Take a regex composed of all strings (works for finite languages)} |
42 |
||
401
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
43 |
\item Assume you have an alphabet consisting of the letters |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
44 |
$a$, $b$ and $c$ only. (1) Find a regular expression |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
45 |
that recognises the two strings $ab$ and $ac$. (2) Find |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
46 |
a regular expression that matches all strings |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
47 |
\emph{except} these two strings. Note, you can only use |
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
48 |
regular expressions of the form |
258
1e4da6d2490c
updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
146
diff
changeset
|
49 |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
50 |
\begin{center} $r ::= |
401
5d85dc9779b1
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
355
diff
changeset
|
51 |
\ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; |
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
52 |
r_1 \cdot r_2 \;|\; r^*$ |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
53 |
\end{center} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
54 |
|
647 | 55 |
%\item Define the function \textit{zeroable} which takes a |
56 |
% regular expression as argument and returns a boolean. |
|
57 |
% The function should satisfy the following property: |
|
58 |
% |
|
59 |
% \begin{center} |
|
60 |
% $\textit{zeroable(r)} \;\text{if and only if}\; |
|
61 |
% L(r) = \{\}$ |
|
62 |
% \end{center} |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
63 |
|
892 | 64 |
\solution{Done in the video but there I forgot to include the empty string.} |
65 |
||
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
66 |
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
517 | 67 |
states, say $Q_0$ and $Q_1$. The starting state is $Q_0$ and the |
68 |
final state is $Q_1$. The transition function is given by |
|
258
1e4da6d2490c
updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
146
diff
changeset
|
69 |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
70 |
\begin{center} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
71 |
\begin{tabular}{l} |
517 | 72 |
$(Q_0, a) \rightarrow Q_0$\\ |
73 |
$(Q_0, b) \rightarrow Q_1$\\ |
|
74 |
$(Q_1, b) \rightarrow Q_1$ |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
75 |
\end{tabular} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
76 |
\end{center} |
258
1e4da6d2490c
updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
146
diff
changeset
|
77 |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
78 |
What is the language recognised by this automaton? |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
79 |
|
355
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
80 |
\item Give a non-deterministic finite automaton that can |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
81 |
recognise the language $L(a\cdot (a + b)^* \cdot c)$. |
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
82 |
|
517 | 83 |
\item Given a deterministic finite automaton $A(\varSigma, Q, Q_0, F, |
355
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
84 |
\delta)$, define which language is recognised by this |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
85 |
automaton. Can you define also the language defined by a |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
86 |
non-deterministic automaton? |
23 | 87 |
|
892 | 88 |
|
89 |
\solution{ |
|
90 |
A formula for DFAs is |
|
91 |
||
92 |
\[L(A) \dn \{s \;|\; \hat{\delta}(start_q, s) \in F\}\] |
|
93 |
||
94 |
For NFAs you need to first define what $\hat{\rho}$ means. If |
|
95 |
$\rho$ is given as a relation, you can define: |
|
96 |
||
97 |
\[ |
|
98 |
\hat{\rho}(qs, []) \dn qs \qquad |
|
99 |
\hat{\rho}(qs, c::s) \dn \bigcup_{q\in qs} \{ q' \; | \; \rho(q, c, q')\} |
|
100 |
\] |
|
101 |
||
102 |
This ``collects'' all the states reachable in a breadth-first |
|
103 |
manner. Once you have all the states reachable by an NFA, you can define |
|
104 |
the language as |
|
105 |
||
106 |
\[ |
|
107 |
L(N) \dn \{s \;|\; \hat{\rho}(qs_{start}, s) \cap F \not= \emptyset\} |
|
108 |
\] |
|
109 |
||
110 |
Here you test whether the all states reachable (for $s$) contain at least |
|
111 |
a single accepting state. |
|
112 |
||
113 |
} |
|
114 |
||
355
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
115 |
\item Given the following deterministic finite automaton over |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
116 |
the alphabet $\{a, b\}$, find an automaton that |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
117 |
recognises the complement language. (Hint: Recall that |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
118 |
for the algorithm from the lectures, the automaton needs |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
119 |
to be in completed form, that is have a transition for |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
120 |
every letter from the alphabet.) |
264
4deef8ac5d72
uodated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
258
diff
changeset
|
121 |
|
892 | 122 |
\solution{ |
123 |
Before exchanging accepting and non-accepting states, it is important that |
|
124 |
the automaton is completed (meamning has a transition for every letter |
|
125 |
of the alphabet). If not completed, you have to introduce a sink state. |
|
126 |
||
127 |
For fun you can try out the example with |
|
128 |
out completion: Then the original automaton can recognise |
|
129 |
strings of the form $a$, $ab...b$; but the ``uncompleted'' automaton would |
|
130 |
recognise only the empty string. |
|
131 |
} |
|
132 |
||
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
133 |
\begin{center} |
292
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
134 |
\begin{tikzpicture}[>=stealth',very thick,auto, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
135 |
every state/.style={minimum size=0pt, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
136 |
inner sep=2pt,draw=blue!50,very thick, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
137 |
fill=blue!20},scale=2] |
517 | 138 |
\node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
139 |
\node[state, accepting] (q1) at ( 1,1) {$Q_1$}; |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
140 |
\path[->] (q0) edge node[above] {$a$} (q1) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
141 |
(q1) edge [loop right] node {$b$} (); |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
142 |
\end{tikzpicture} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
143 |
\end{center} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
144 |
|
264
4deef8ac5d72
uodated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
258
diff
changeset
|
145 |
|
4deef8ac5d72
uodated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
258
diff
changeset
|
146 |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
147 |
%\item Given the following deterministic finite automaton |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
148 |
% |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
149 |
%\begin{center} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
150 |
%\begin{tikzpicture}[scale=3, line width=0.7mm] |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
151 |
% \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
152 |
% \node[state,accepting] (q1) at ( 1,1) {$q_1$}; |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
153 |
% \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
154 |
% \path[->] (q0) edge node[above] {$b$} (q1) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
155 |
% (q1) edge [loop above] node[above] {$a$} () |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
156 |
% (q2) edge [loop above] node[above] {$a, b$} () |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
157 |
% (q1) edge node[above] {$b$} (q2) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
158 |
% (q0) edge[bend right] node[below] {$a$} (q2) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
159 |
% ; |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
160 |
%\end{tikzpicture} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
161 |
%\end{center} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
162 |
%find the corresponding minimal automaton. State clearly which nodes |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
163 |
%can be merged. |
31 | 164 |
|
355
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
165 |
\item Given the following non-deterministic finite automaton |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
166 |
over the alphabet $\{a, b\}$, find a deterministic |
a259eec25156
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
347
diff
changeset
|
167 |
finite automaton that recognises the same language: |
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
168 |
|
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
169 |
\begin{center} |
292
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
170 |
\begin{tikzpicture}[>=stealth',very thick,auto, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
171 |
every state/.style={minimum size=0pt, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
172 |
inner sep=2pt,draw=blue!50,very thick, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
173 |
fill=blue!20},scale=2] |
517 | 174 |
\node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
175 |
\node[state] (q1) at ( 1,1) {$Q_1$}; |
|
176 |
\node[state, accepting] (q2) at ( 2,1) {$Q_2$}; |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
177 |
\path[->] (q0) edge node[above] {$a$} (q1) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
178 |
(q0) edge [loop above] node[above] {$b$} () |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
179 |
(q0) edge [loop below] node[below] {$a$} () |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
180 |
(q1) edge node[above] {$a$} (q2); |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
181 |
\end{tikzpicture} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
182 |
\end{center} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
183 |
|
778 | 184 |
\item %%\textbf{(Deleted for 2017, 2018, 2019)} |
517 | 185 |
Given the following deterministic finite automaton over the |
271
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
186 |
alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
187 |
case states can be merged, state clearly which states can be merged. |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
188 |
|
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
189 |
\begin{center} |
292
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
190 |
\begin{tikzpicture}[>=stealth',very thick,auto, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
191 |
every state/.style={minimum size=0pt, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
192 |
inner sep=2pt,draw=blue!50,very thick, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
193 |
fill=blue!20},scale=2] |
517 | 194 |
\node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
195 |
\node[state] (q1) at ( 1,1) {$Q_1$}; |
|
196 |
\node[state, accepting] (q4) at ( 2,1) {$Q_4$}; |
|
197 |
\node[state] (q2) at (0.5,0) {$Q_2$}; |
|
198 |
\node[state] (q3) at (1.5,0) {$Q_3$}; |
|
271
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
199 |
\path[->] (q0) edge node[above] {$0$} (q1) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
200 |
(q0) edge node[right] {$1$} (q2) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
201 |
(q1) edge node[above] {$0$} (q4) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
202 |
(q1) edge node[right] {$1$} (q2) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
203 |
(q2) edge node[above] {$0$} (q3) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
204 |
(q2) edge [loop below] node {$1$} () |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
205 |
(q3) edge node[left] {$0$} (q4) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
206 |
(q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
207 |
(q4) edge [loop right] node {$0, 1$} (); |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
208 |
\end{tikzpicture} |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
209 |
\end{center} |
b9b54574ee41
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
267
diff
changeset
|
210 |
|
892 | 211 |
\solution{Q0 and Q2 can be merged; and Q1 and Q3 as well} |
212 |
||
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
213 |
\item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
264
4deef8ac5d72
uodated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
258
diff
changeset
|
214 |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
215 |
\begin{center} |
292
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
216 |
\begin{tikzpicture}[scale=2,>=stealth',very thick,auto, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
217 |
every state/.style={minimum size=0pt, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
218 |
inner sep=2pt,draw=blue!50,very thick, |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
271
diff
changeset
|
219 |
fill=blue!20}] |
517 | 220 |
\node[state, initial, accepting] (q0) at ( 0,1) {$Q_0$}; |
221 |
\node[state, accepting] (q1) at ( 1,1) {$Q_1$}; |
|
222 |
\node[state] (q2) at ( 2,1) {$Q_2$}; |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
223 |
\path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
224 |
(q1) edge[bend left] node[above] {$b$} (q0) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
225 |
(q2) edge[bend left=50] node[below] {$b$} (q0) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
226 |
(q1) edge node[above] {$a$} (q2) |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
227 |
(q2) edge [loop right] node {$a$} () |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
228 |
(q0) edge [loop below] node {$b$} () |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
229 |
; |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
230 |
\end{tikzpicture} |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
231 |
\end{center} |
31 | 232 |
|
267
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
233 |
Give a regular expression that can recognise the same language as |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
234 |
this automaton. (Hint: If you use Brzozwski's method, you can assume |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
235 |
Arden's lemma which states that an equation of the form $q = q\cdot r + s$ |
a1544b804d1e
updated homeworks
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
264
diff
changeset
|
236 |
has the unique solution $q = s \cdot r^*$.) |
294
c29853b672fb
updated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
237 |
|
c29853b672fb
updated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
238 |
\item If a non-deterministic finite automaton (NFA) has |
770 | 239 |
$n$ states. How many states does a deterministic |
240 |
automaton (DFA) that can recognise the same language |
|
241 |
as the NFA maximal need? |
|
294
c29853b672fb
updated hws
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
242 |
|
892 | 243 |
\solution{ $2^n$ in the worst-case and for some regexes the worst case |
244 |
cannot be avoided. |
|
245 |
||
246 |
Other comments: $r^{\{n\}}$ can only be represented as $n$ |
|
247 |
copies of the automaton for $r$, which can explode the automaton for bounded |
|
248 |
regular expressions. Similarly, we have no idea how backreferences can be |
|
249 |
represented as automaton. |
|
250 |
} |
|
251 |
||
770 | 252 |
\item Prove that for all regular expressions $r$ we have |
253 |
||
254 |
\begin{center} |
|
255 |
$\textit{nullable}(r) \quad \text{if and only if} |
|
256 |
\quad [] \in L(r)$ |
|
257 |
\end{center} |
|
258 |
||
259 |
Write down clearly in each case what you need to prove |
|
260 |
and what are the assumptions. |
|
261 |
||
262 |
||
444
3056a4c071b0
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
401
diff
changeset
|
263 |
\item \POSTSCRIPT |
23 | 264 |
\end{enumerate} |
265 |
||
266 |
\end{document} |
|
267 |
||
268 |
%%% Local Variables: |
|
269 |
%%% mode: latex |
|
270 |
%%% TeX-master: t |
|
271 |
%%% End: |