diff -r 86b2aeae3e98 -r a259eec25156 hws/hw01.tex --- 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}