Binary file hws/hw01.pdf has changed
--- a/hws/hw01.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw01.tex Wed Apr 06 15:55:01 2016 +0100
@@ -9,27 +9,28 @@
\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.
+ 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 {\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 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 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? (Hint: The meaning is
@@ -55,9 +56,9 @@
\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 $\_ + \_$?
+ $\ONE$ and $\ZERO$? (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
Binary file hws/hw02.pdf has changed
--- a/hws/hw02.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw02.tex Wed Apr 06 15:55:01 2016 +0100
@@ -8,39 +8,42 @@
\HEADER
\begin{enumerate}
-\item What is the language recognised by the regular expressions
- $(\varnothing^*)^*$.
+
+\item What is the language recognised by the regular
+ expressions $(\ZERO^*)^*$.
-\item Review the first handout about sets of strings and read the
- second handout. Assuming the alphabet is the set $\{a, b\}$, decide
- which of the following equations are true in general for arbitrary
- languages $A$, $B$ and $C$:
+\item Review the first handout about sets of strings and read
+ the second handout. Assuming the alphabet is the set
+ $\{a, b\}$, decide which of the following equations are
+ true in general for arbitrary languages $A$, $B$ and
+ $C$:
- \begin{eqnarray}
- (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
- A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\
- A^* @ A^* & =^? & A^*\nonumber\\
- (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber
- \end{eqnarray}
+ \begin{eqnarray}
+ (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
+ A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\
+ A^* @ A^* & =^? & A^*\nonumber\\
+ (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber
+ \end{eqnarray}
- \noindent In case an equation is true, give an explanation; otherwise
- give a counter-example.
+ \noindent In case an equation is true, give an
+ explanation; otherwise give a counter-example.
-\item Given the regular expressions $r_1 = \epsilon$ and $r_2 =
- \varnothing$ and $r_3 = a$. How many strings can the regular
- expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
+\item Given the regular expressions $r_1 = \ONE$ and $r_2 =
+ \ZERO$ and $r_3 = a$. How many strings can the regular
+ expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
-\item Give regular expressions for (a) decimal numbers and for (b)
- binary numbers. (Hint: Observe that the empty string is not a
- number. Also observe that leading 0s are normally not written.)
+\item Give regular expressions for (a) decimal numbers and for
+ (b) binary numbers. (Hint: Observe that the empty string
+ is not a number. Also observe that leading 0s are
+ normally not written.)
\item Decide whether the following two regular expressions are
- equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot b)^* \cdot
- a \equiv^? a \cdot (b \cdot a)^*$.
+ equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot
+ b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
-\item Given the regular expression $r = (a \cdot b + b)^*$. Compute
- what the derivative of $r$ is with respect to $a$, $b$ and $c$. Is
- $r$ nullable?
+\item Given the regular expression $r = (a \cdot b + b)^*$.
+ Compute what the derivative of $r$ is with respect to
+ $a$, $b$ and $c$. Is $r$ nullable?
\item Prove that for all regular expressions $r$ we have
@@ -49,8 +52,8 @@
\quad [] \in L(r)$
\end{center}
- Write down clearly in each case what you need to prove and
- what are the assumptions.
+ Write down clearly in each case what you need to prove
+ and what are the assumptions.
\item Define what is meant by the derivative of a regular
expressions with respect to a character. (Hint: The
@@ -62,42 +65,42 @@
$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$
\end{center}
- What is the relation between $Der$ and the notion of derivative of
- regular expressions?
+ What is the relation between $Der$ and the notion of
+ derivative of regular expressions?
\item Give a regular expression over the alphabet $\{a,b\}$
- recognising all strings that do not contain any substring $bb$ and
- end in $a$.
+ recognising all strings that do not contain any
+ substring $bb$ and end in $a$.
-\item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define
- the same language?
+\item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) +
+ (b^*\cdot b^+)$ define the same language?
\item Define the function $zeroable$ by recursion over regular
- expressions. This function should satisfy the property
+ expressions. This function should satisfy the property
\[
- zeroable(r) \;\;\text{if and only if}\;\;L(r) = \varnothing\qquad(*)
+ zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}\qquad(*)
\]
- The function $nullable$ for the not-regular expressions can be defined
- by
+ The function $nullable$ for the not-regular expressions
+ can be defined by
\[
nullable(\sim r) \dn \neg(nullable(r))
\]
- Unfortunately, a similar definition for $zeroable$ does not satisfy
- the property in $(*)$:
+ Unfortunately, a similar definition for $zeroable$ does
+ not satisfy the property in $(*)$:
\[
zeroable(\sim r) \dn \neg(zeroable(r))
\]
- Find out why?
+ Find out why?
-\item Give a regular expressions that can recognise all strings from the
- language $\{a^n\;|\;\exists k. n = 3 k + 1 \}$.
-\end{enumerate}
+\item Give a regular expressions that can recognise all
+ strings from the language $\{a^n\;|\;\exists k.\; n = 3 k
+ + 1 \}$. \end{enumerate}
\end{document}
Binary file hws/hw03.pdf has changed
--- a/hws/hw03.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw03.tex Wed Apr 06 15:55:01 2016 +0100
@@ -9,28 +9,31 @@
\HEADER
\begin{enumerate}
-\item What is a regular language? Are there alternative ways to define this
- notion? If yes, give an explanation why they define the same notion.
+\item What is a regular language? Are there alternative ways
+ to define this notion? If yes, give an explanation why
+ they define the same notion.
\item Why is every finite set of strings a regular language?
-\item Assume you have an alphabet consisting of the letters $a$, $b$
- and $c$ only. (1) Find a regular expression that recognises the two
- strings $ab$ and $ac$. (2) Find a regular expression that matches
- all strings \emph{except} these two strings. Note, you can only use
- regular expressions of the form
+\item Assume you have an alphabet consisting of the letters
+ $a$, $b$ and $c$ only. (1) Find a regular expression
+ that recognises the two strings $ab$ and $ac$. (2) Find
+ a regular expression that matches all strings
+ \emph{except} these two strings. Note, you can only use
+ regular expressions of the form
\begin{center} $r ::=
- \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;
+ \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\;
r_1 \cdot r_2 \;|\; r^*$
\end{center}
-\item Define the function \textit{zeroable} which takes a regular
- expression as argument and returns a boolean. The function should
- satisfy the following property:
+\item Define the function \textit{zeroable} which takes a
+ regular expression as argument and returns a boolean.
+ The function should satisfy the following property:
\begin{center}
- $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
+ $\textit{zeroable(r)} \;\text{if and only if}\;
+ L(r) = \{\}$
\end{center}
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two
Binary file hws/hw04.pdf has changed
--- a/hws/hw04.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw04.tex Wed Apr 06 15:55:01 2016 +0100
@@ -33,8 +33,8 @@
\begin{center}
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
- $rev(\varnothing)$ & $\dn$ & $\varnothing$\\
- $rev(\epsilon)$ & $\dn$ & $\epsilon$\\
+ $rev(\ZERO)$ & $\dn$ & $\ZERO$\\
+ $rev(\ONE)$ & $\dn$ & $\ONE$\\
$rev(c)$ & $\dn$ & $c$\\
$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
@@ -56,44 +56,47 @@
holds.
-\item Assume the delimiters for comments are \texttt{$\slash$*} and
- \texttt{*$\slash$}. Give a regular expression that can recognise
- comments of the form
+\item Assume the delimiters for comments are
+ \texttt{$\slash$*} and \texttt{*$\slash$}. Give a
+ regular expression that can recognise comments of the
+ form
\begin{center}
\texttt{$\slash$*~\ldots{}~*$\slash$}
\end{center}
- where the three dots stand for arbitrary characters, but not comment delimiters.
- (Hint: You can assume you are already given a regular expression written \texttt{ALL},
- that can recognise any character, and a regular expression \texttt{NOT} that recognises
- the complement of a regular expression.)
+ where the three dots stand for arbitrary characters, but
+ not comment delimiters. (Hint: You can assume you are
+ already given a regular expression written \texttt{ALL},
+ that can recognise any character, and a regular
+ expression \texttt{NOT} that recognises the complement
+ of a regular expression.)
\item Simplify the regular expression
\[
-(\varnothing \cdot (b \cdot c)) +
-((\varnothing \cdot c) + \epsilon)
+(\ZERO \cdot (b \cdot c)) +
+((\ZERO \cdot c) + \ONE)
\]
-Does simplification always preserve the meaning of a regular
-expression?
+ Does simplification always preserve the meaning of a
+ regular expression?
-\item The Sulzmann \& Lu algorithm contains the function $mkeps$
- which answers how a regular expression can match the
- empty string. What is the answer of $mkeps$ for the
+\item The Sulzmann \& Lu algorithm contains the function
+ $mkeps$ which answers how a regular expression can match
+ the empty string. What is the answer of $mkeps$ for the
regular expressions:
\[
\begin{array}{l}
- (\varnothing \cdot (b \cdot c)) +
- ((\varnothing \cdot c) + \epsilon)\\
- (a + \varepsilon) \cdot (\varepsilon + \varepsilon)
+ (\ZERO \cdot (b \cdot c)) +
+ ((\ZERO \cdot c) + \ONE)\\
+ (a + \ONE) \cdot (\ONE + \ONE)
\end{array}
\]
-\item What is the purpose of the record regular expression
- in the Sulzmann \& Lu algorithm?
+\item What is the purpose of the record regular expression in
+ the Sulzmann \& Lu algorithm?
%\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
Binary file hws/hw05.pdf has changed
--- a/hws/hw05.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw05.tex Wed Apr 06 15:55:01 2016 +0100
@@ -18,21 +18,21 @@
\item Consider the basic regular expressions
\begin{center}
-$r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
+$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
\end{center}
-and suppose you want to show a property $P(r)$ for all regular
-expressions $r$ by structural induction. Write down which cases do you
-need to analyse. State clearly the induction hypotheses if applicable
-in a case.
+ and suppose you want to show a property $P(r)$ for all
+ regular expressions $r$ by structural induction. Write
+ down which cases do you need to analyse. State clearly
+ the induction hypotheses if applicable in a case.
-\item Define a regular expression, written $ALL$, that can match
-every string. This definition should be in terms of the
-following extended regular expressions:
+\item Define a regular expression, written $ALL$, that can
+ match every string. This definition should be in terms
+ of the following extended regular expressions:
\begin{center}
-$r ::= \varnothing \;|\;
- \epsilon \;|\;
+$r ::= \ZERO \;|\;
+ \ONE \;|\;
c \;|\;
r_1 + r_2 \;|\;
r_1 \cdot r_2 \;|\;
@@ -66,17 +66,17 @@
in terms of the usual basic regular expressions
\begin{center}
-$r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
+$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
\end{center}
\item Give the regular expressions for lexing a language
-consisting of identifiers, left-parenthesis \texttt{(},
-right-parenthesis \texttt{)}, numbers that can be either
-positive or negative, and the operations \texttt{+},
-\texttt{-} and \texttt{*}.
+ consisting of identifiers, left-parenthesis \texttt{(},
+ right-parenthesis \texttt{)}, numbers that can be either
+ positive or negative, and the operations \texttt{+},
+ \texttt{-} and \texttt{*}.
-Decide whether the following strings
-can be lexed in this language?
+ Decide whether the following strings can be lexed in
+ this language?
\begin{enumerate}
\item \texttt{"(a3+3)*b"}
@@ -88,14 +88,15 @@
Observe the maximal munch rule and the priorities of your regular
expressions that make the process of lexing unambiguous.)
-\item (Optional) Recall the definitions for $Der$ and $der$ from the lectures.
-Prove by induction on $r$ the property that
+\item (Optional) Recall the definitions for $Der$ and $der$
+ from the lectures. Prove by induction on $r$ the
+ property that
\[
L(der\,c\,r) = Der\,c\,(L(r))
\]
-holds.
+ holds.
\end{enumerate}
Binary file hws/hw06.pdf has changed
--- a/hws/hw06.tex Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw06.tex Wed Apr 06 15:55:01 2016 +0100
@@ -10,11 +10,11 @@
\begin{enumerate}
\item (i) Give the regular expressions for lexing a language
-consisting of whitespaces, identifiers (some letters followed by digits), numbers,
-operations \texttt{=}, \texttt{<} and \texttt{>}, and the keywords
-\texttt{if}, \texttt{then} and \texttt{else}.
-(ii) Decide whether the following strings
-can be lexed in this language?
+ consisting of whitespaces, identifiers (some letters
+ followed by digits), numbers, operations \texttt{=},
+ \texttt{<} and \texttt{>}, and the keywords \texttt{if},
+ \texttt{then} and \texttt{else}. (ii) Decide whether the
+ following strings can be lexed in this language?
\begin{enumerate}
\item \texttt{"if y4 = 3 then 1 else 3"}