--- a/hws/hw01.tex Fri Oct 16 14:27:20 2015 +0100
+++ b/hws/hw01.tex Sat Oct 17 11:24:41 2015 +0100
@@ -31,33 +31,40 @@
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? (Hint: The meaning is defined recursively.)
+\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} two sets of strings. This operation
+ is also written as $\_ \,@\, \_$.
-\item Assume a set $A$ contains 4 strings and a set $B$ 7 strings. None
- of the strings is the empty string. How many strings are in $A \,@\, B$?
+\item Assume a set $A$ contains 4 strings and a set $B$
+ contains 7 strings. None of the strings is the empty
+ string. 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 Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$?
- Consider the case of $A^4$ where one of the strings in $A$ is the
- empty string, for example $A = \{[a], [b], [c], []\}$.
+\item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
+ are in $A^4$? (2) Consider the case of $A^4$ where one of
+ the strings in $A$ is the empty string, for example $A =
+ \{[a], [b], [c], []\}$.
-\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 basic regular expressions are there to match
+ the string $abcd$? (ii) How many if they cannot include
+ $\epsilon$ and $\varnothing$? (iii) How many if they are
+ also not allowed to contain stars? (iv) 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}