# HG changeset patch # User Christian Urban # Date 1459954501 -3600 # Node ID 5d85dc9779b13312793b9a447ef89ab3cb480751 # Parent e4afe3f46c295d806d8441d65a2688c23fbd9f00 updated diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw01.tex --- 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 diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw02.tex --- 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} diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw03.tex --- 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 diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw04.tex --- 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 diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw05.tex --- 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} diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw06.tex --- 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"}