# HG changeset patch # User Christian Urban # Date 1475874483 -3600 # Node ID 3056a4c071b043089246fc57fc3f6c992860066a # Parent cd43d8c6eb840ecd4ffade20899c8c8794921702 updated diff -r cd43d8c6eb84 -r 3056a4c071b0 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 handouts/ho03.tex --- a/handouts/ho03.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/handouts/ho03.tex Fri Oct 07 22:08:03 2016 +0100 @@ -184,16 +184,16 @@ The reason for introducing NFAs is that there is a relatively simple (recursive) translation of regular expressions into -NFAs. Consider the simple regular expressions $\varnothing$, -$\epsilon$ and $c$. They can be translated as follows: +NFAs. Consider the simple regular expressions $\ZERO$, +$\ONE$ and $c$. They can be translated as follows: \begin{center} \begin{tabular}[t]{l@{\hspace{10mm}}l} -\raisebox{1mm}{$\varnothing$} & +\raisebox{1mm}{$\ZERO$} & \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] \node[state, initial] (q_0) {$\mbox{}$}; \end{tikzpicture}\\\\ -\raisebox{1mm}{$\epsilon$} & +\raisebox{1mm}{$\ONE$} & \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] \node[state, initial, accepting] (q_0) {$\mbox{}$}; \end{tikzpicture}\\\\ @@ -548,7 +548,7 @@ system \begin{eqnarray} -q_0 & = & \epsilon + q_0\,b + q_1\,b + q_2\,b\\ +q_0 & = & \ONE + q_0\,b + q_1\,b + q_2\,b\\ q_1 & = & q_0\,a\\ q_2 & = & q_1\,a + q_2\,a \end{eqnarray} @@ -569,7 +569,7 @@ will make you stay in $q_2$. The right-hand side of the first equation is constructed similarly: there are three incoming edges, therefore there are three terms. There is -one exception in that we also ``add'' $\epsilon$ to the +one exception in that we also ``add'' $\ONE$ to the first equation, because it corresponds to the starting state in the DFA. @@ -582,7 +582,7 @@ into the other two. This gives \begin{eqnarray} -q_0 & = & \epsilon + q_0\,b + q_0\,a\,b + q_2\,b\\ +q_0 & = & \ONE + q_0\,b + q_0\,a\,b + q_2\,b\\ q_2 & = & q_0\,a\,a + q_2\,a \end{eqnarray} @@ -591,7 +591,7 @@ Equation (4) to obtain the following two equations: \begin{eqnarray} -q_0 & = & \epsilon + q_0\,(b + a\,b) + q_2\,b\\ +q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\ q_2 & = & q_0\,a\,a + q_2\,a \end{eqnarray} @@ -607,7 +607,7 @@ (7) to obtain the two new equations \begin{eqnarray} -q_0 & = & \epsilon + q_0\,(b + a\,b) + q_2\,b\\ +q_0 & = & \ONE + q_0\,(b + a\,b) + q_2\,b\\ q_2 & = & q_0\,a\,a\,(a^*) \end{eqnarray} @@ -615,26 +615,26 @@ the first in order to eliminate the variable $q_2$. \begin{eqnarray} -q_0 & = & \epsilon + q_0\,(b + a\,b) + q_0\,a\,a\,(a^*)\,b +q_0 & = & \ONE + q_0\,(b + a\,b) + q_0\,a\,a\,(a^*)\,b \end{eqnarray} \noindent Pulling $q_0$ out as a single factor gives: \begin{eqnarray} -q_0 & = & \epsilon + q_0\,(b + a\,b + a\,a\,(a^*)\,b) +q_0 & = & \ONE + q_0\,(b + a\,b + a\,a\,(a^*)\,b) \end{eqnarray} \noindent This equation is again of the form so that we can apply Arden's rule ($r$ is $b + a\,b + a\,a\,(a^*)\,b$ and $s$ -is $\epsilon$). This gives as solution for $q_0$ the following +is $\ONE$). This gives as solution for $q_0$ the following regular expression: \begin{eqnarray} -q_0 & = & \epsilon\,(b + a\,b + a\,a\,(a^*)\,b)^* +q_0 & = & \ONE\,(b + a\,b + a\,a\,(a^*)\,b)^* \end{eqnarray} \noindent Since this is a regular expression, we can simplify -away the $\epsilon$ to obtain the slightly simpler regular +away the $\ONE$ to obtain the slightly simpler regular expression \begin{eqnarray} diff -r cd43d8c6eb84 -r 3056a4c071b0 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 handouts/ho04.tex --- a/handouts/ho04.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/handouts/ho04.tex Fri Oct 07 22:08:03 2016 +0100 @@ -537,7 +537,7 @@ \noindent This completes the high-level version of the simplification function, which is shown again in Figure~\ref{simp}. The Scala code -for the simplifaction function is in Figure~\ref{simprect}. +for the simplification function is in Figure~\ref{simprect}. \begin{figure}[t] \begin{center} diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw01.tex --- a/hws/hw01.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/hws/hw01.tex Fri Oct 07 22:08:03 2016 +0100 @@ -54,10 +54,10 @@ the strings in $A$ is the empty string, for example $A = \{[a], [b], [c], []\}$. -\item How many basic regular expressions are there to match - the string $abcd$? (ii) How many if they cannot include - $\ONE$ and $\ZERO$? (iii) How many if they are also not - allowed to contain stars? (iv) How many if they are also +\item (1)How many basic regular expressions are there to match + the string $abcd$? (2) How many if they cannot include + $\ONE$ and $\ZERO$? (3) How many if they are also not + allowed to contain stars? (4) How many if they are also not allowed to contain $\_ + \_$? \item When are two regular expressions equivalent? Can you @@ -68,7 +68,7 @@ $[b]$. \item What is meant by the notions \emph{evil regular expressions} - and \emph{catastrophic backtracking}? + and by \emph{catastrophic backtracking}? \item \POSTSCRIPT \end{enumerate} diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw02.tex --- a/hws/hw02.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/hws/hw02.tex Fri Oct 07 22:08:03 2016 +0100 @@ -104,7 +104,8 @@ \item Give a regular expression that can recognise an odd number of $a$s or an even number of $b$s. - + +\item \POSTSCRIPT \end{enumerate} \end{document} diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw03.tex --- a/hws/hw03.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/hws/hw03.tex Fri Oct 07 22:08:03 2016 +0100 @@ -172,6 +172,7 @@ automaton (DFA) that can recognise the same language as the NFA maximal need? +\item \POSTSCRIPT \end{enumerate} \end{document} diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw04.tex --- a/hws/hw04.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/hws/hw04.tex Fri Oct 07 22:08:03 2016 +0100 @@ -10,7 +10,7 @@ \begin{enumerate} -\item If a regular expression $r$ does not contain any occurrence of $\varnothing$, +\item If a regular expression $r$ does not contain any occurrence of $\ZERO$, is it possible for $L(r)$ to be empty? \item Define the tokens and regular expressions for a language @@ -106,7 +106,9 @@ %\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it %implements the \texttt{findAll} function. This function takes a regular %expressions and a string, and returns all substrings in this string that -%match the regular expression. + %match the regular expression. + +\item \POSTSCRIPT \end{enumerate} diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r cd43d8c6eb84 -r 3056a4c071b0 hws/hw05.tex --- a/hws/hw05.tex Tue Oct 04 15:09:08 2016 +0100 +++ b/hws/hw05.tex Fri Oct 07 22:08:03 2016 +0100 @@ -88,7 +88,7 @@ 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$ +\item {\bf(Optional)} Recall the definitions for $Der$ and $der$ from the lectures. Prove by induction on $r$ the property that @@ -98,6 +98,7 @@ holds. +\item \POSTSCRIPT \end{enumerate} \end{document}