diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw01.tex --- a/hws/hw01.tex Mon Oct 06 20:55:16 2014 +0100 +++ b/hws/hw01.tex Fri Oct 10 16:59:22 2014 +0100 @@ -7,58 +7,51 @@ \begin{enumerate} -\item {\bf (Optional)} If you want to run the code presented - in the lectures, install the Scala programming language - available (for free) from +\item {\bf (Optional)} If you want to run the code presented in the + lectures, install the Scala programming language available (for + free) from \begin{center} \url{http://www.scala-lang.org} \end{center} - If you want to follow the code I present during the - lectures, read the handout about Scala. - -\item {\bf (Optional)} Have a look at the crawler programs. - Can you find a usage for them in your daily programming - life? Can you improve them? (For example in cases there - are links that appear on different recursion levels, the - crawlers visit such web-pages several times. Can this be - avoided?) + If you want to follow the code I present during the lectures, + read the handout about Scala. -\item Read the handout of the first lecture and the handout - about notation. Make sure you understand the concepts of - strings and languages. +\item {\bf (Optional)} Have a look at the crawler programs. Can you + find a usage for them in your daily programming life? Can you + improve them? (For example in cases there are links that appear on + different recursion levels, the crawlers visit such web-pages + several times. Can this be avoided?) -\item In the context of the AFL-course, what is meant by the - term \emph{language}? +\item Read the handout of the first lecture and the handout about + notation. Make sure you understand the concepts of strings and + languages. In the context of the AFL-course, what is meant by the + term \emph{language}? -\item Give the definition for regular expressions. What is the - meaning of a regular expression? +\item Give the definition for regular expressions. What is the meaning + of a regular expression? (Hint: The meaning is defined recursively.) -\item Assume the concatenation operation of two strings is - written as $s_1 @ s_2$. Define the operation of - \emph{concatenating}, written $\_ \,@\, \_$ two sets of - strings. +\item Assume the concatenation operation of two strings is written as + $s_1 @ s_2$. Define the operation of \emph{concatenating}, written + $\_ \,@\, \_$ two sets of strings. -\item Assume a set $A$ contains 4 strings and a set $B$ 7 - strings, how many strings are in $A @ B$? +\item Assume a set $A$ contains 4 strings and a set $B$ 7 strings, how + many strings are in $A \,@\, B$? -\item How is the power of a language defined? (Hint: There are - two rules, one for $\_^0$ and one for - $\_^{n+1}$.) +\item How is the power of a language defined? (Hint: There are two + rules, one for $\_^0$ and one for $\_^{n+1}$.) -\item How many regular expressions are there to match the - string $abc$? How many if they cannot include - $\epsilon$ and $\varnothing$? How many if they are also - not allowed to contain stars? How many if they are also - not allowed to contain $\_ + \_$? +\item How many regular expressions are there to match the string + $abc$? How many if they cannot include $\epsilon$ and $\varnothing$? + How many if they are also not allowed to contain stars? How many if + they are also not allowed to contain $\_ + \_$? -\item When are two regular expressions equivalent? Can you - think of instances where two regular expressions match - the same strings, but it is not so obvious that they do? For - example $a + b$ and $b + a$ do not count\ldots they - obviously match the same strings, namely $[a]$ and $[b]$. - +\item When are two regular expressions equivalent? Can you think of + instances where two regular expressions match the same strings, but + it is not so obvious that they do? For example $a + b$ and $b + a$ + do not count\ldots they obviously match the same strings, namely + $[a]$ and $[b]$. \end{enumerate} \end{document}