diff -r ce767ca23244 -r 377c59df7297 hws/hw01.tex --- a/hws/hw01.tex Mon Sep 15 04:42:48 2014 +0100 +++ b/hws/hw01.tex Mon Sep 15 04:54:01 2014 +0100 @@ -1,46 +1,62 @@ \documentclass{article} -\usepackage{charter} -\usepackage{hyperref} -\usepackage{amssymb} +\usepackage{../style} \begin{document} \section*{Homework 1} \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} -\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 (in cases they are linked on different levels, -they visit web-pages several times)? + 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?) -\item Read the handout of the first lecture and make sure you -understand the concepts of strings and languages. +\item Read the handout of the first lecture and the handout + about notation. Make sure you understand the concepts of + strings and languages. -\item In the context of the AFL-course, what is meant by the term \emph{language}? +\item 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? -\item Assume the concatenation operation of two strings is written as $s_1 @ s_2$. -Define the operation of \emph{concatenating} 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} 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 also are + not allowed to contain stars? How many if they also are + not allowed to contain $\_ + \_$?) -\item How many regular expressions are there to match the string $abc$? -(How many if they cannot include $\epsilon$ and $\varempty$? -How many if they also are not allowed to contain stars? -How many if they also are not allowed to contain $+$?) +\item When are two regular expressions equivalent? Can you + think of instances where two regular expressions are + equivalent, but it is not so obvious that they are? For + example $a + b$ and $b + a$ do not count\ldots they + are obviously equivalent. \end{enumerate}