\documentclass[dvipsnames,14pt,t]{beamer}

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\hfuzz=220pt 

\pgfplotsset{compat=1.11}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}  

% beamer stuff 

\renewcommand{\slidecaption}{CFL 03, King's College London}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\[-3mm]

  \LARGE Compilers and \\[-2mm] 

  \LARGE Formal Languages (3)\\[3mm] 

  \end{tabular}}

\normalsize

  \begin{center}

  \begin{tabular}{lp{8cm}}

  Email:  & christian.urban at kcl.ac.uk\\

  Office: & N\liningnums{7.07} (North Wing, Bush House)\\

  Slides: & KEATS (also homework and coursework is there)\\

  \end{tabular}

  \end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Scala Book, Exams}

\begin{itemize}

\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize

\item homework (written exam 80\%)

\item coursework (20\%)\bigskip

\item short survey at KEATS; to be answered until Sunday    

\end{itemize}

\end{frame}

%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Regular Expressions}

In programming languages they are often used to recognise:\medskip

\begin{itemize}

\item symbols, digits

\item identifiers

\item numbers (non-leading zeros)

\item keywords

\item comments

\end{itemize}\bigskip

\mbox{}\hfill\bl{\url{http://www.regexper.com}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Last Week}

Last week I showed you a regular expression matcher 

that works provably correct in all cases (we only

started with the proving part though)

\begin{center}

\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}

\end{center}\bigskip\bigskip 

\small

\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{The Derivative of a Rexp}

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

  \bl{$der\, c\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\

  \bl{$der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\

  \bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\

  \bl{$der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\

  \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\

  & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ 

  & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\

  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\

  \bl{$\textit{ders}\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\

  \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\

  \end{tabular}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Example}

Given \bl{$r \dn ((a \cdot b) + b)^*$} what is

\begin{center}

\def\arraystretch{1.5}  

\begin{tabular}{@{}lcl}

  \bl{$\der\,a\,((a \cdot b) + b)^*$}

    & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\

    & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\

    & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\

    & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\

    & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\

    & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\

\end{tabular}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

Input: string \bl{$abc$} and regular expression \bl{$r$} 

\begin{enumerate}

\item \bl{$der\,a\,r$}

\item \bl{$der\,b\,(der\,a\,r)$}

\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause

\item finally check whether the last regular expression can match the empty string

\end{enumerate}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Simplification}

Given \bl{$r \dn ((a \cdot b) + b)^*$} what is

\begin{center}

\def\arraystretch{2}  

\begin{tabular}{@{}lcl}

  \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}

    & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\

    & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\

    & \bl{$=$} & \bl{$b \cdot r$}\\

\end{tabular}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

We proved

\begin{center}

\bl{$nullable(r)$} \;if and only if\;  \bl{$[] \in L(r)$}

\end{center}

by induction on the regular expression \bl{$r$}.\bigskip\pause

\begin{center}

{\huge\bf\alert{Any Questions?}}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

We need to prove

\begin{center}

\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}

\end{center}

also by induction on the regular expression \bl{$r$}.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Proofs about Rexps}

\begin{itemize}

\item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip

\item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already

holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip

\item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already

holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip

\item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already

holds for \bl{$r$}.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}

\begin{itemize}

\item \bl{$P$} holds for \bl{$0$} and

\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already

holds for \bl{$n$}

\end{itemize}\bigskip

\begin{itemize}

\item \bl{$P$} holds for \bl{$[]$} and

\item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already

holds for \bl{$s$}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Regular Expressions}

\begin{center}

   \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}

  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\

         & \bl{$\mid$} & \bl{$\ONE$}        & empty string / "" / $[]$\\

         & \bl{$\mid$} & \bl{$c$}                         & character\\

         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\

         & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\

         & \bl{$\mid$} & \bl{$r^*$}                   & star (zero or more)\\

  \end{tabular}

  \end{center}

How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the

set of languages we can recognise?

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Negation of Regular Expr's}

\begin{itemize}

\item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip

\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip

\item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip

\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}

\end{itemize}\bigskip\pause

Used often for recognising comments:

\[

\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}

\]

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Negation}

Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.

Find a (basic!) regular expression that matches all strings \emph{\alert{except}} 

\bl{$ab$} and \bl{$ac$}!

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\frametitle{Automata}

A \alert{\bf deterministic finite automaton}, DFA, consists of:

\begin{itemize}

\item an alphabet \bl{$\varSigma$}  

\item one of these states is the start state \bl{$\mbox{Q}_0$}

\item some states are accepting states \bl{$F$}, and

\item there is transition function \bl{$\delta$}\bigskip 

\small

which takes a state as argument and a character and produces a 

new state; this function might not be everywhere defined $\Rightarrow$ partial function

\end{itemize}

\begin{center}

\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\begin{center}

\begin{tikzpicture}[>=stealth',very thick,auto,

\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};

\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};

\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};

\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};

\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};

\path[->] (Q_0) edge node [above]  {\alert{$a$}} (Q_1);

\path[->] (Q_1) edge node [above]  {\alert{$a$}} (Q_4);

\path[->] (Q_4) edge [loop right] node  {\alert{$a, b$}} ();

\path[->] (Q_3) edge node [right]  {\alert{$a$}} (Q_4);

\path[->] (Q_2) edge node [above]  {\alert{$a$}} (Q_3);

\path[->] (Q_1) edge node [right]  {\alert{$b$}} (Q_2);

\path[->] (Q_0) edge node [above]  {\alert{$b$}} (Q_2);

\path[->] (Q_2) edge [loop left] node  {\alert{$b$}} ();

\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (Q_0);

\end{tikzpicture}

\end{center}

\begin{itemize}

\item the start state can be an accepting state

\item it is possible that there is no accepting state

\item all states might be accepting (but this does not necessarily mean all strings are accepted)

for this automaton \bl{$\delta$} is the function\\

\begin{center}

\begin{tabular}{lll}

  \bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$}

  & \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\

  \bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} &

  \bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\

\end{tabular}\ldots

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Accepting a String}

Given

\begin{center}

\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}

\end{center}

you can define

\begin{center}

\begin{tabular}{l}

\bl{$\widehat{\delta}(q, []) \dn q$}\\

\bl{$\widehat{\delta}(q, c::s) \dn \widehat{\delta}(\delta(q, c), s)$}\\

\end{tabular}

\end{center}\pause

Whether a string \bl{$s$} is accepted by \bl{$A$}?

\begin{center}

\hspace{5mm}\bl{$\widehat{\delta}(\mbox{Q}_0, s) \in F$}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Regular Languages}

A \alert{\bf language} is a set of strings.\bigskip

A \alert{\bf regular expression} specifies a language.\bigskip

A language is \alert{\bf regular} iff there exists

a regular expression that recognises all its strings.\bigskip\bigskip\pause

not all languages are regular, e.g.~\bl{$a^nb^n$} is not

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Regular Languages (2)}

A language is \alert{\bf regular} iff there exists a regular

expression that recognises all its strings.\bigskip\medskip

or {\bf equivalently}\bigskip\medskip

A language is \alert{\bf regular} iff there exists a

deterministic finite automaton that recognises all its

strings.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{\begin{tabular}{c}

              Non-Deterministic\\[-1mm] 

              Finite Automata\end{tabular}}

A non-deterministic finite automaton (NFA) consists again of:

\begin{itemize}

\item a finite set of states

\item \underline{some} these states are the start states

\item some states are accepting states, and

\item there is transition \alert{relation}\medskip 

\end{itemize}

\begin{center}

\begin{tabular}{c}

\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_2$}\\

\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_3$}\\

\end{tabular}

\bl{\ldots}

\hspace{10mm}\pause

\bl{$(\mbox{Q}_1, a) \rightarrow \{\mbox{Q}_2, \mbox{Q}_3\}$}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{An NFA Example}

% A NFA for (ab* + b)*a

\begin{center}

\begin{tikzpicture}[>=stealth',very thick, auto,

    every state/.style={minimum size=0pt,inner sep=3pt,

      draw=blue!50,very thick,fill=blue!20},scale=2]

\node[state,initial]  (Q_0)  {$\mbox{Q}_0$};

\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};

\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};

\path[->] (Q_0) edge [loop above] node  {\alert{$b$}} ();

\path[<-] (Q_0) edge node [below]  {\alert{$b$}} (Q_1);

\path[->] (Q_0) edge [bend left] node [above]  {\alert{$a$}} (Q_1);

\path[->] (Q_0) edge [bend right] node [below]  {\alert{$a$}} (Q_2);

\path[->] (Q_1) edge [loop above] node  {\alert{$a,b$}} ();

\path[->] (Q_1) edge node  [above] {\alert{$a$}} (Q_2);

\end{tikzpicture}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Two Epsilon NFA Examples}

\small

\begin{center}

\begin{tabular}[t]{c@{\hspace{9mm}}c}

\begin{tikzpicture}[scale=0.7,>=stealth',very thick,

                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

\node[state,initial]  (q_0)  {$q_0$};

\node[state] (q_1) [above=of q_0] {$q_1$};

\node[state, accepting] (q_2) [below=of q_0] {$q_2$};

\path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_1);