188 The DFA has three states Q0,Q1,Q2 with Q0 starting state and Q2 accepting. |
188 The DFA has three states Q0,Q1,Q2 with Q0 starting state and Q2 accepting. |
189 The transitions are (Q0,a)-> Q1 (Q0,b)->Q0 (Q1,a)->Q2 (Q1,b)->Q0 |
189 The transitions are (Q0,a)-> Q1 (Q0,b)->Q0 (Q1,a)->Q2 (Q1,b)->Q0 |
190 (Q2,a)->Q2 (Q2,b)->Q0. |
190 (Q2,a)->Q2 (Q2,b)->Q0. |
191 } |
191 } |
192 |
192 |
193 \item %%\textbf{(Deleted for 2017, 2018, 2019)} |
193 %\item %%\textbf{(Deleted for 2017, 2018, 2019)} |
194 Given the following deterministic finite automaton over the |
194 % Given the following deterministic finite automaton over the |
195 alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
195 % alphabet $\{0, 1\}$, find the corresponding minimal automaton. In |
196 case states can be merged, state clearly which states can be merged. |
196 % case states can be merged, state clearly which states can be merged. |
197 |
197 % |
198 \begin{center} |
198 % \begin{center} |
199 \begin{tikzpicture}[>=stealth',very thick,auto, |
199 % \begin{tikzpicture}[>=stealth',very thick,auto, |
200 every state/.style={minimum size=0pt, |
200 % every state/.style={minimum size=0pt, |
201 inner sep=2pt,draw=blue!50,very thick, |
201 % inner sep=2pt,draw=blue!50,very thick, |
202 fill=blue!20},scale=2] |
202 % fill=blue!20},scale=2] |
203 \node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
203 % \node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
204 \node[state] (q1) at ( 1,1) {$Q_1$}; |
204 % \node[state] (q1) at ( 1,1) {$Q_1$}; |
205 \node[state, accepting] (q4) at ( 2,1) {$Q_4$}; |
205 % \node[state, accepting] (q4) at ( 2,1) {$Q_4$}; |
206 \node[state] (q2) at (0.5,0) {$Q_2$}; |
206 % \node[state] (q2) at (0.5,0) {$Q_2$}; |
207 \node[state] (q3) at (1.5,0) {$Q_3$}; |
207 % \node[state] (q3) at (1.5,0) {$Q_3$}; |
208 \path[->] (q0) edge node[above] {$0$} (q1) |
208 % \path[->] (q0) edge node[above] {$0$} (q1) |
209 (q0) edge node[right] {$1$} (q2) |
209 % (q0) edge node[right] {$1$} (q2) |
210 (q1) edge node[above] {$0$} (q4) |
210 % (q1) edge node[above] {$0$} (q4) |
211 (q1) edge node[right] {$1$} (q2) |
211 % (q1) edge node[right] {$1$} (q2) |
212 (q2) edge node[above] {$0$} (q3) |
212 % (q2) edge node[above] {$0$} (q3) |
213 (q2) edge [loop below] node {$1$} () |
213 % (q2) edge [loop below] node {$1$} () |
214 (q3) edge node[left] {$0$} (q4) |
214 % (q3) edge node[left] {$0$} (q4) |
215 (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
215 % (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
216 (q4) edge [loop right] node {$0, 1$} (); |
216 % (q4) edge [loop right] node {$0, 1$} (); |
217 \end{tikzpicture} |
217 % \end{tikzpicture} |
218 \end{center} |
218 % \end{center} |
219 |
219 |
220 \solution{Q0 and Q2 can be merged; and Q1 and Q3 as well} |
220 % \solution{Q0 and Q2 can be merged; and Q1 and Q3 as well} |
221 |
221 |
222 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
222 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$: |
223 |
223 |
224 \begin{center} |
224 \begin{center} |
225 \begin{tikzpicture}[scale=2,>=stealth',very thick,auto, |
225 \begin{tikzpicture}[scale=2,>=stealth',very thick,auto, |
270 \solution{The problem has to do with bounded regular expressions, |
270 \solution{The problem has to do with bounded regular expressions, |
271 such as $r^{\{n\}}$. They are represented as $n$-copies of some |
271 such as $r^{\{n\}}$. They are represented as $n$-copies of some |
272 automaton for $r$. If $n$ is large, then this can result in a |
272 automaton for $r$. If $n$ is large, then this can result in a |
273 large memory-footprint and slow runtime.} |
273 large memory-footprint and slow runtime.} |
274 |
274 |
|
275 \item On Mentimeter there was a question: \textit{``Why does the [regex] $(a^*)^*b$ takes much longer for |
|
276 strings of length 28 compared to say 25?''}\smallskip\\ |
|
277 |
|
278 For this consider a lake with $1000 m^3$ surface and an invasive plant |
|
279 that tries to cover the lake with leaves, think of the famous water lily that |
|
280 produces leaves on which you can stand. This plant starts out with a |
|
281 seedling covering just $0.001 m^3$ of the lake, but doubles every day |
|
282 the surface that is covers. So on day two it would cover $0.002 m^3$, |
|
283 on day three $0.004 m^3$ and so on. How many days does the plant need to |
|
284 cover the entire lake? How many days is the lake still 90\% \emph{un}covered? |
|
285 |
|
286 \solution{That is a classic example of the law of exponentiation, meaning an |
|
287 exponential function grows very slowly at first, but then explodes. It should take |
|
288 20 days to completely cover the lake: $0.001 * 2^{20}$. But up to day 16 still less |
|
289 than 10\% are covered. The remaining 90\% covering comes essentially in the last 3 |
|
290 days only. That is the same with any exponential algorithm: they are pretty ok for some |
|
291 small values, but then they suddenly explode where they are not ok anymore.\\ |
|
292 |
|
293 PS: After COVID, we should all be more aware of the incredible growth of |
|
294 exponential functions. That is why I liked that Ms~Merkel was in |
|
295 charge of Germany during COVID and managed to keep numbers of dead |
|
296 people in Germany relatively low...not all was smooth of course. But she |
|
297 was a scientist in her former life (actually a physicist) and knew about |
|
298 exponential growth. While we over here had this clown Boris Johnson in charge, |
|
299 who with his joke-education and smashing up restaurants, had no clue what an |
|
300 exponential function is.} |
|
301 |
275 \item Prove that for all regular expressions $r$ we have |
302 \item Prove that for all regular expressions $r$ we have |
276 |
303 |
277 \begin{center} |
304 \begin{center} |
278 $\textit{nullable}(r) \quad \text{if and only if} |
305 $\textit{nullable}(r) \quad \text{if and only if} |
279 \quad [] \in L(r)$ |
306 \quad [] \in L(r)$ |