diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides03.tex --- a/slides/slides03.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/slides/slides03.tex Sat Aug 15 14:18:37 2020 +0100 @@ -1,5 +1,5 @@ % !TEX program = xelatex -\documentclass[dvipsnames,14pt,t]{beamer} +\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} \usepackage{../graphics} \usepackage{../langs} @@ -22,17 +22,33 @@ \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Compilers and \\[-2mm] - \LARGE Formal Languages (3)\\[3mm] + \LARGE Formal Languages\\[3mm] \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)\\ + %Office Hours: & Thursdays 12 -- 14\\ + %Location: & N7.07 (North Wing, Bush House)\\ Slides \& Progs: & KEATS (also homework is there)\\ \end{tabular} +\end{center} + + \begin{center} + \begin{tikzpicture} + \node[drop shadow,fill=white,inner sep=0pt] + {\footnotesize\rowcolors{1}{capri!10}{white} + \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline + 1 Introduction, Languages & 6 While-Language \\ + 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ + \cellcolor{blue!50} + 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ + 4 Lexing, Tokenising & 9 Optimisations \\ + 5 Grammars, Parsing & 10 LLVM \\ \hline + \end{tabular}% + }; + \end{tikzpicture} \end{center} \end{frame} @@ -55,206 +71,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\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}[t] -\frametitle{Simplification} - -Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows - -\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] - \frametitle{Proofs about Rexp} - - \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] - -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] -\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}[c] - \frametitle{Correctness Proof \\[-1mm] - for our Matcher} - - \begin{itemize} - \item We started from - - \begin{center} - \begin{tabular}{rp{4cm}} - & \bl{$s \in L(r)$}\medskip\\ - \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause - \end{tabular} - \end{center}\bigskip - - \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we - have\bigskip - - \begin{center} - \begin{tabular}{rp{4cm}} - \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ - \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ - \bl{$\dn$} & \bl{$matches\,s\,r$} - \end{tabular} - \end{center} - - \end{itemize} - - \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}[t] \frametitle{(Basic) Regular Expressions} @@ -1329,6 +1145,360 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{center} +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] + \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} + \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} + \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} + \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} + \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; + \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$b$}} () + ; +\end{tikzpicture} +\end{center}\bigskip + +\begin{center} +\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ +\end{tabular} +\end{center} + + +Arden's Lemma: +\begin{center} +If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} +\end{center} + +\only<2-6>{\small +\begin{textblock}{6}(1,0.8) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} +\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<3-6>{\small +\begin{textblock}{6}(2,4.15) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} +\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<4-6>{\small +\begin{textblock}{6}(3,7.55) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} + \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<5-6>{\small +\begin{textblock}{6}(4,10.9) +\begin{bubble}[7.5cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} + \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<6>{\small +\begin{textblock}{6}(5,13.4) +\begin{bubble}[7.5cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} + \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + + +\only<7->{\small +\begin{textblock}{6}(6,11.5) +\begin{bubble}[6.7cm] +\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} +\multicolumn{3}{@{}l}{Finally:}\\ +\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ +\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ +\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Regexps and Automata} + +\begin{center} +\begin{tikzpicture} +\node (rexp) {\bl{\bf Regexps}}; +\node (nfa) [right=of rexp] {\bl{\bf NFAs}}; +\node (dfa) [right=of nfa] {\bl{\bf DFAs}}; +\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; +\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] + {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); +\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] + {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); +\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); +%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); +\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); + +\end{tikzpicture}\\ +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} + +\begin{tikzpicture} +\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=30, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=10cm, + height=7cm, + legend entries={Python,Ruby,my NFA}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; +\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; +\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; +\end{axis} +\end{tikzpicture} + +The punchline is that many existing libraries do depth-first search +in NFAs (backtracking). + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{DFA to Rexp} + +% \begin{center} +% \begin{tikzpicture}[scale=2,>=stealth',very thick, +% every state/.style={minimum size=0pt, +% draw=blue!50,very thick,fill=blue!20},] +% \node[state, initial] (q0) at ( 0,1) {$q_0$}; +% \node[state] (q1) at ( 1,1) {$q_1$}; +% \node[state, accepting] (q2) at ( 2,1) {$q_2$}; +% \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) +% (q1) edge[bend left] node[above] {\alert{$b$}} (q0) +% (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) +% (q1) edge node[above] {\alert{$a$}} (q2) +% (q2) edge [loop right] node {\alert{$a$}} () +% (q0) edge [loop below] node {\alert{$b$}} (); +% \end{tikzpicture} +% \end{center}\bigskip + +% \begin{center} +% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} +% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ +% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ +% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ + +% \end{tabular} +% \end{center} + +% Arden's Lemma: +% \begin{center} +% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} +% \end{center} + + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{DFA Minimisation} + +% \begin{enumerate} +% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} +% \item Mark all pairs that accepting and non-accepting states +% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether +% \begin{center} +% \bl{$(\delta(q, c), \delta(p,c))$} +% \end{center} +% are marked. If yes, then also mark \bl{$(q, p)$}. +% \item Repeat last step until no change. +% \item All unmarked pairs can be merged. +% \end{enumerate} + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] + +% \begin{center} +% \begin{tabular}{@{\hspace{-8mm}}cc@{}} +% \begin{tikzpicture}[>=stealth',very thick,auto, +% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] +% \node[state,initial] (q_0) {$q_0$}; +% \node[state] (q_1) [right=of q_0] {$q_1$}; +% \node[state] (q_2) [below right=of q_0] {$q_2$}; +% \node[state] (q_3) [right=of q_2] {$q_3$}; +% \node[state, accepting] (q_4) [right=of q_1] {$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} +% & +% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] +% \draw (0,0) -- (4,0); +% \draw (0,1) -- (4,1); +% \draw (0,2) -- (3,2); +% \draw (0,3) -- (2,3); +% \draw (0,4) -- (1,4); + +% \draw (0,0) -- (0, 4); +% \draw (1,0) -- (1, 4); +% \draw (2,0) -- (2, 3); +% \draw (3,0) -- (3, 2); +% \draw (4,0) -- (4, 1); + +% \draw (0.5,-0.5) node {$q_0$}; +% \draw (1.5,-0.5) node {$q_1$}; +% \draw (2.5,-0.5) node {$q_2$}; +% \draw (3.5,-0.5) node {$q_3$}; + +% \draw (-0.5, 3.5) node {$q_1$}; +% \draw (-0.5, 2.5) node {$q_2$}; +% \draw (-0.5, 1.5) node {$q_3$}; +% \draw (-0.5, 0.5) node {$q_4$}; + +% \draw (0.5,0.5) node {\large$\star$}; +% \draw (1.5,0.5) node {\large$\star$}; +% \draw (2.5,0.5) node {\large$\star$}; +% \draw (3.5,0.5) node {\large$\star$}; +% \draw (0.5,1.5) node {\large$\star$}; +% \draw (2.5,1.5) node {\large$\star$}; +% \draw (0.5,3.5) node {\large$\star$}; +% \draw (1.5,2.5) node {\large$\star$}; +% \end{tikzpicture}} +% \end{tabular} +% \end{center} + + +% \mbox{}\\[-20mm]\mbox{} + +% \begin{center} +% \begin{tikzpicture}[>=stealth',very thick,auto, +% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] +% \node[state,initial] (q_02) {$q_{0, 2}$}; +% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; +% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; +% \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); +% \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); +% \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); +% \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); +% \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); +% \end{tikzpicture}\\ +% minimal automaton +% \end{center} + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Regular Languages} + +Two equivalent definitions:\bigskip + +\begin{quote}\rm A language is \alert{regular} iff there exists a +regular expression that recognises all its strings. +\end{quote} + +\begin{quote}\rm A language is \alert{regular} iff there exists an +automaton that recognises all its strings. +\end{quote}\bigskip\bigskip + + +\small +for example \bl{$a^nb^n$} is not regular +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Negation} + +Regular languages are closed under negation:\bigskip + +\begin{center} +\begin{tikzpicture}[scale=2,>=stealth',very thick, + every state/.style={minimum size=0pt, + draw=blue!50,very thick,fill=blue!20}] + \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} + \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} + \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} + \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} + \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} + \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} + \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) + (q1) edge[bend left] node[above] {\alert{$b$}} (q0) + (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) + (q1) edge node[above] {\alert{$a$}} (q2) + (q2) edge [loop right] node {\alert{$a$}} () + (q0) edge [loop below] node {\alert{$b$}} (); +\end{tikzpicture} +\end{center}\bigskip\bigskip + +But requires that the automaton is \alert{completed}! + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \end{document} %%% Local Variables: