86 automaton. Can you define also the language defined by a |
86 automaton. Can you define also the language defined by a |
87 non-deterministic automaton? |
87 non-deterministic automaton? |
88 |
88 |
89 |
89 |
90 \solution{ |
90 \solution{ |
91 A formula for DFAs is |
91 s A formula for DFAs is |
92 |
92 eed |
93 \[L(A) \dn \{s \;|\; \hat{\delta}(start_q, s) \in F\}\] |
93 \[L(A) \dn \{s \;|\; \hat{\delta}(start_q, s) \in F\}\] |
94 |
94 |
95 For NFAs you need to first define what $\hat{\rho}$ means. If |
95 For NFAs you need to first define what $\hat{\rho}$ means. If |
96 $\rho$ is given as a relation, you can define: |
96 $\rho$ is given as a relation, you can define: |
97 |
97 |
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 |
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\\ |
276 strings of length 28 compared to say 25?''}\smallskip\\ |
277 |
277 |
278 For this consider a lake with $1000 m^3$ surface and an invasive plant |
278 For this consider a lake with $1000 m^2$ surface and an invasive plant |
279 that tries to cover the lake with leaves, think of the famous water lily that |
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 |
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 |
281 seedling covering just $0.001 m^2$ of the lake, but doubles every day |
282 the surface that is covers. So on day two it would cover $0.002 m^3$, |
282 the surface that is covers. So on day two it would cover $0.002 m^2$, |
283 on day three $0.004 m^3$ and so on. How many days does the plant need to |
283 on day three $0.004 m^2$ 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? |
284 cover the entire lake? How many days is the lake still 90\% \emph{un}covered? |
285 |
285 |
286 \solution{That is a classic example of the law of exponentiation, meaning an |
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 |
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 |
288 20 days to completely cover the lake: $0.001 * 2^{20}$. But up to day 16 still less |