Binary file hws/hw03.pdf has changed
--- a/hws/hw03.tex Fri Oct 14 12:16:07 2022 +0100
+++ b/hws/hw03.tex Fri Oct 21 13:30:12 2022 +0100
@@ -2,6 +2,14 @@
\usepackage{../style}
\usepackage{../graphics}
+\newcommand{\solution}[1]{%
+ \begin{quote}\sf%
+ #1%
+ \end{quote}}
+\renewcommand{\solution}[1]{}
+
+
+
\begin{document}
\section*{Homework 3}
@@ -12,13 +20,26 @@
\item The regular expression matchers in Java, Python and Ruby can be
very slow with some (basic) regular expressions. What is the main
reason for this inefficient computation?
+
+ \solution{Many matchers employ DFS type of algorithms to check
+ if a string is matched by the regex or not. Such algorithms
+ require backtracking if have gone down the wrong path which
+ can be very slow. There are also problems with bounded regular
+ expressions and backreferences.}
\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.
+ \solution{A regular language is a language for which every string
+ can be recognized by some regular expression. Another definition is
+ that it is a language for which a finite automaton can be
+ constructed. Both define the same set of languages.}
+
\item Why is every finite set of strings a regular language?
+ \solution{Take a regex composed of all strings (works for finite languages)}
+
\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
@@ -40,6 +61,8 @@
% L(r) = \{\}$
% \end{center}
+ \solution{Done in the video but there I forgot to include the empty string.}
+
\item Given the alphabet $\{a,b\}$. Draw the automaton that has two
states, say $Q_0$ and $Q_1$. The starting state is $Q_0$ and the
final state is $Q_1$. The transition function is given by
@@ -62,6 +85,33 @@
automaton. Can you define also the language defined by a
non-deterministic automaton?
+
+ \solution{
+ A formula for DFAs is
+
+ \[L(A) \dn \{s \;|\; \hat{\delta}(start_q, s) \in F\}\]
+
+ For NFAs you need to first define what $\hat{\rho}$ means. If
+ $\rho$ is given as a relation, you can define:
+
+ \[
+ \hat{\rho}(qs, []) \dn qs \qquad
+ \hat{\rho}(qs, c::s) \dn \bigcup_{q\in qs} \{ q' \; | \; \rho(q, c, q')\}
+ \]
+
+ This ``collects'' all the states reachable in a breadth-first
+ manner. Once you have all the states reachable by an NFA, you can define
+ the language as
+
+ \[
+ L(N) \dn \{s \;|\; \hat{\rho}(qs_{start}, s) \cap F \not= \emptyset\}
+ \]
+
+ Here you test whether the all states reachable (for $s$) contain at least
+ a single accepting state.
+
+ }
+
\item Given the following deterministic finite automaton over
the alphabet $\{a, b\}$, find an automaton that
recognises the complement language. (Hint: Recall that
@@ -69,6 +119,17 @@
to be in completed form, that is have a transition for
every letter from the alphabet.)
+ \solution{
+ Before exchanging accepting and non-accepting states, it is important that
+ the automaton is completed (meamning has a transition for every letter
+ of the alphabet). If not completed, you have to introduce a sink state.
+
+ For fun you can try out the example with
+ out completion: Then the original automaton can recognise
+ strings of the form $a$, $ab...b$; but the ``uncompleted'' automaton would
+ recognise only the empty string.
+ }
+
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,
@@ -147,6 +208,8 @@
\end{tikzpicture}
\end{center}
+ \solution{Q0 and Q2 can be merged; and Q1 and Q3 as well}
+
\item Given the following finite deterministic automaton over the alphabet $\{a, b\}$:
\begin{center}
@@ -177,6 +240,15 @@
automaton (DFA) that can recognise the same language
as the NFA maximal need?
+ \solution{ $2^n$ in the worst-case and for some regexes the worst case
+ cannot be avoided.
+
+ Other comments: $r^{\{n\}}$ can only be represented as $n$
+ copies of the automaton for $r$, which can explode the automaton for bounded
+ regular expressions. Similarly, we have no idea how backreferences can be
+ represented as automaton.
+ }
+
\item Prove that for all regular expressions $r$ we have
\begin{center}
--- a/hws/hw04.tex Fri Oct 14 12:16:07 2022 +0100
+++ b/hws/hw04.tex Fri Oct 21 13:30:12 2022 +0100
@@ -127,7 +127,7 @@
\textit{infinitestrings} (for regular expressions that can match
infinitely many strings).
-\item There are two kinds of automata that are generate for
+\item There are two kinds of automata that are generated for
regular expression matching---DFAs and NFAs. (1) Regular expression engines like
the one in Python generate NFAs. Explain what is the problem with such
NFAs and what is the reason why they use NFAs. (2) Regular expression
Binary file slides/slides03.pdf has changed
--- a/slides/slides03.tex Fri Oct 14 12:16:07 2022 +0100
+++ b/slides/slides03.tex Fri Oct 21 13:30:12 2022 +0100
@@ -1806,10 +1806,11 @@
\begin{frame}[c]
\begin{itemize}
- \item CW
+ \item CW / censored some msgs
\item power law / proof
\item CW feedback
- \item too polished CW submissions
+ \item too polished CW submissions
+ \item no open book
\end{itemize}
\end{frame}
Binary file slides/slides04.pdf has changed
--- a/slides/slides04.tex Fri Oct 14 12:16:07 2022 +0100
+++ b/slides/slides04.tex Fri Oct 21 13:30:12 2022 +0100
@@ -31,21 +31,21 @@
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
- \LARGE Compilers and \\[-2mm]
- \LARGE Formal Languages\\[3mm]
+ \LARGE Compilers and \\[-1mm]
+ \LARGE Formal Languages\\[-5mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
- Email: & christian.urban at kcl.ac.uk\\
- %Office Hours: & Thursdays 12 -- 14\\
- %Location: & N7.07 (North Wing, Bush House)\\
- Slides \& Progs: & KEATS (also homework is there)\\
+ Email: & christian.urban at kcl.ac.uk\\
+ Office Hour: & Fridays 11 -- 12\\
+ Location: & N7.07 (North Wing, Bush House)\\
+ Slides \& Progs: & KEATS\\
+ Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
\end{tabular}
\end{center}
-
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
@@ -1652,59 +1652,29 @@
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\begin{mybox3}{}
- Are dfas completed by definition as in do they have a to have transitions
- for every char at every state?
-\end{mybox3}
-\end{frame}
-
-\begin{frame}[t]
-\begin{mybox3}{}
- How can you tell if a language will be regular or irregular?
-\end{mybox3}
-\end{frame}
-
-\begin{frame}<1-18>[c]
-\end{frame}
-
-\end{document}
-
-\begin{frame}[c]
- \small
- \begin{itemize}
-\item[$\bullet$] contentwise probably the most enjoyable module I have had so far at KCL
-
-\item[$\bullet$] I personally found the coursework sheets a bit unclear. For example I couldnt see what was required from the CFUN section but once explained it actually was very easy and didnt take long to get working
-
-\item[$\bullet$] Please can tutorial sessions be recorded \& linked on Keats.
-
-\item[$\bullet$] One of the best taught modules I've had, with a genuinely interested and engaging lecturer. Thanks Dr.~Urban!
-\end{itemize}
-\end{frame}
-
-\begin{frame}[c]
- \small
- \begin{itemize}
-\item[$\bullet$] Dr.~Urban is honestly a great lecturer, he's incredibly helpful and responsive. He also teaches at a very good pace and explains things clearly so students who sometimes struggle with the content like myself can keep up. It's a pleasure to learn from him.
-
-\item[$\bullet$] I just wish the Coursework content was explained better, in such a way that allows students to get on with the coursework as soon as possible.
-
-\item[$\bullet$] I'm thoroughly enjoying the module so far. I find that the handouts and homework really solidify my knowledge and the feedback is extremely useful. I enjoy doing the homework and then using the feedback alongside the workshop to correct where I have gone wrong.
-
-\item[$\bullet$] I enjoy this module and think it is taught well. The homework is very useful.
-\end{itemize}
+\begin{frame}<1-28>[c]
\end{frame}
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
- \includegraphics[scale=0.3]{s1.png} &
- \includegraphics[scale=0.3]{s2.png} \\
- \includegraphics[scale=0.3]{s3.png} &
- \includegraphics[scale=0.3]{s4.png} \\
+ \includegraphics[scale=0.27]{s1.png} &
+ \includegraphics[scale=0.27]{s2.png} \\
+ \includegraphics[scale=0.27]{s3.png} &
+ \includegraphics[scale=0.27]{s4.png} \\
+ \end{tabular}
+ \end{center}
+\end{frame}
+
+\begin{frame}[c]
+ \begin{center}
+ \begin{tabular}{cc}
+ \includegraphics[scale=0.27]{s5.png} &
+ \includegraphics[scale=0.27]{s6.png} \\
+ \includegraphics[scale=0.27]{s7.png} &
+ \includegraphics[scale=0.27]{s8.png} \\
\end{tabular}
\end{center}
\end{frame}
@@ -1712,22 +1682,108 @@
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
- \includegraphics[scale=0.3]{s5.png} &
- \includegraphics[scale=0.3]{s6.png} \\
- \includegraphics[scale=0.3]{s7.png} &
- \includegraphics[scale=0.3]{s8.png} \\
+ \includegraphics[scale=0.3]{s9.png} &
+ \includegraphics[scale=0.3]{s10.png}
\end{tabular}
\end{center}
\end{frame}
+
+
\begin{frame}[c]
- \begin{center}
- \begin{tabular}{cc}
- \includegraphics[scale=0.3]{s9.png}
- \end{tabular}
- \end{center}
+ \small
+ \begin{itemize}
+ \item[$\bullet$] I'm impressed by the speed of the answers on KEATS,
+ even on weekends. It's amazing. Obviously, the lecturer cares about
+ the students.\pause
+
+ \item[$\bullet$] The handouts and materials on KEATS are very
+ helpful and your explanation is easy to understand especially
+ after both reading the handout and watch the lectures. The LGT is
+ also engaging and I will try my best to engage more. I am actually
+ already impressed by your teaching since 5CCS2PEP.\pause
+
+ \item[$\bullet$] I believe the module is great, if possible, it
+ would be nice to have a small handout that recaps Scala syntax
+ from PEP last year.
+\end{itemize}
+\end{frame}
+
+\begin{frame}[c]
+ \small
+ \begin{itemize}
+ \item[$\bullet$] While I understand you want people to attend the
+ small groups, not providing the solutions to the homework
+ exercises disadvantages those with disabilities (e.g. processing
+ difficulties) as most students take notes of the solutions during
+ the SGTs, and those of us who are unable to do so cannot obtain
+ the full benefit of the sessions. Even if the exam is based on
+ those questions, it is closed-book anyway, so there is no harm in
+ providing the answers. At least allow the TAs to give the
+ solutions to those who attend the SGTs please?
+
+ \item[$\bullet$] Really enjoy the content, but would appreciate
+ uploads of the tutorial answers as sometimes we do not have time
+ to go through all of them in the SGTs.
+\end{itemize}
\end{frame}
+\begin{frame}[c]
+ \small
+ \begin{itemize}
+ \item[$\bullet$] CFL is a very interesting module and the LGTs are
+ helpful to consolidate information. The homeworks and courseworks
+ are useful for learning the content. My only criticism is that it
+ feels like there is too much content crammed into each
+ week. Between the time taken each week by 2h LGT, 1h SGT, 3-4h of
+ videos, 1-2h homework and time for courseworks, I find it
+ difficult making time for all aspects of this module each week.
+
+\end{itemize}
+\end{frame}
+
+\begin{frame}[c]
+ \small
+ \begin{itemize}
+ \item[$\bullet$] i like this course
+ \item[$\bullet$] I could learn the material better if the LGTs could
+ somehow be recorded because I've sometimes felt a need to go back
+ to them while revising stuff
+ \item[$\bullet$] I feel that, as with most modules, there is a lot
+ happening at once. Since we only went through the first coursework
+ it's too early to call, but the workload tends to pile up. I
+ understand it's in the nature of the module, and the work, though
+ difficult, is enjoyable, but there's gotta be a way to mitigate
+ this. Other than that, I am enjoying this module and you, Chris,
+ are a great lecturer!
+\end{itemize}
+\end{frame}
+
+\begin{frame}[c]
+ \small
+ \begin{itemize}
+ \item[$\bullet$] Strongly advise you, the lecturer, to take into
+ account that your students have not been studying the subject for
+ as long as you have. Also, that some of us are still waiting to be
+ convinced of the interesting-ness and relevance of the subject,
+ which you often fail to mention in the sessions and in the
+ videos. I find myself lost trying to find a context for the things
+ we are learning.
+
+ \ldots
+
+ I thoroughly enjoy the SGTS where my concerns and questions are
+ welcomed. But I feel uncomfortable to ask you questions in your
+ LGTs because of the way I have heard you respond to other
+ students.
+
+\end{itemize}
+\end{frame}
+
+\end{document}
+\end{document}
+
+
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t