\documentclass[dvipsnames,14pt,t]{beamer}\usepackage{beamerthemeplainculight}\usepackage[T1]{fontenc}\usepackage[latin1]{inputenc}\usepackage{mathpartir}\usepackage[absolute,overlay]{textpos}\usepackage{ifthen}\usepackage{tikz}\usepackage{pgf}\usepackage{calc} \usepackage{ulem}\usepackage{courier}\usepackage{listings}\renewcommand{\uline}[1]{#1}\usetikzlibrary{arrows}\usetikzlibrary{automata}\usetikzlibrary{shapes}\usetikzlibrary{shadows}\usetikzlibrary{positioning}\usetikzlibrary{calc}\usepackage{graphicx} \definecolor{javared}{rgb}{0.6,0,0} % for strings\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc\lstset{language=Java, basicstyle=\ttfamily, keywordstyle=\color{javapurple}\bfseries, stringstyle=\color{javagreen}, commentstyle=\color{javagreen}, morecomment=[s][\color{javadocblue}]{/**}{*/}, numbers=left, numberstyle=\tiny\color{black}, stepnumber=1, numbersep=10pt, tabsize=2, showspaces=false, showstringspaces=false}\lstdefinelanguage{scala}{ morekeywords={abstract,case,catch,class,def,% do,else,extends,false,final,finally,% for,if,implicit,import,match,mixin,% new,null,object,override,package,% private,protected,requires,return,sealed,% super,this,throw,trait,true,try,% type,val,var,while,with,yield}, otherkeywords={=>,<-,<\%,<:,>:,\#,@}, sensitive=true, morecomment=[l]{//}, morecomment=[n]{/*}{*/}, morestring=[b]", morestring=[b]', morestring=[b]"""}\lstset{language=Scala, basicstyle=\ttfamily, keywordstyle=\color{javapurple}\bfseries, stringstyle=\color{javagreen}, commentstyle=\color{javagreen}, morecomment=[s][\color{javadocblue}]{/**}{*/}, numbers=left, numberstyle=\tiny\color{black}, stepnumber=1, numbersep=10pt, tabsize=2, showspaces=false, showstringspaces=false}% beamer stuff \renewcommand{\slidecaption}{AFL 04, King's College London, 17.~October 2012}\newcommand{\bl}[1]{\textcolor{blue}{#1}} \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions\begin{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}<1>[t]\frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Automata and \\[-2mm] \LARGE Formal Languages (4)\\[3mm] \end{tabular}} \normalsize \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ Of$\!$fice: & S1.27 (1st floor Strand Building)\\ Slides: & KEATS (also home work is there)\\ \end{tabular} \end{center}\end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Last Week\end{tabular}}Last week I showed you\bigskip\begin{itemize}\item a tokenizer taking a list of regular expressions\bigskip\item tokenization identifies lexeme in an input stream of characters (or string)and cathegorizes them into tokens\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Two Rules\end{tabular}}\begin{itemize}\item Longest match rule (maximal munch rule): The longest initial substring matched by any regular expression is takenas next token.\bigskip\item Rule priority:For a particular longest initial substring, the first regularexpression that can match determines the token.\end{itemize}%\url{http://www.technologyreview.com/tr10/?year=2011}%finite deterministic automata/ nondeterministic automaton%\item problem with infix operations, for example i-12\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[t]\begin{center}\texttt{"if true then then 42 else +"}\end{center}\begin{tabular}{@{}l}KEYWORD: \\\hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\ WHITESPACE:\\\hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\ IDENT:\\\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\ NUM:\\\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\OP:\\\hspace{5mm}\texttt{"+"}\\COMMENT:\\\hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"}\end{tabular}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[t]\begin{center}\texttt{"if true then then 42 else +"}\end{center}\only<1>{\small\begin{tabular}{l}KEYWORD(if),\\ WHITESPACE,\\ IDENT(true),\\ WHITESPACE,\\ KEYWORD(then),\\ WHITESPACE,\\ KEYWORD(then),\\ WHITESPACE,\\ NUM(42),\\ WHITESPACE,\\ KEYWORD(else),\\ WHITESPACE,\\ OP(+)\end{tabular}}\only<2>{\small\begin{tabular}{l}KEYWORD(if),\\ IDENT(true),\\ KEYWORD(then),\\ KEYWORD(then),\\ NUM(42),\\ KEYWORD(else),\\ OP(+)\end{tabular}}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]There is one small problem with the tokenizer. How should we tokenize:\begin{center}\texttt{"x - 3"}\end{center}\begin{tabular}{@{}l}OP:\\\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\NUM:\\\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\NUMBER:\\\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\\end{tabular}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Negation\end{tabular}}Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only.Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}.\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}}A deterministic finite automaton consists of:\begin{itemize}\item a finite set of states\item one of these states is the start state\item some states are accepting states, and\item there is transition function\medskip \smallwhich takes a state and a character as arguments and produces a new state\smallskip\\this function might not always be defined everywhere\end{itemize}\begin{center}\bl{$A(Q, q_0, F, \delta)$}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\includegraphics[scale=0.7]{pics/ch3.jpg}\end{center}\pause\begin{itemize}\item start can be an accepting state\item it is possible that there is no accepting state\item all states might be accepting (but does not necessarily mean all strings are accepted)\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\includegraphics[scale=0.7]{pics/ch3.jpg}\end{center}for this automaton \bl{$\delta$} is the function\\\begin{center}\begin{tabular}{lll}\bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\\bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\\end{tabular}\ldots\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[t]\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}}Given\begin{center}\bl{$A(Q, q_0, F, \delta)$}\end{center}you can define\begin{center}\begin{tabular}{l}\bl{$\hat{\delta}(q, \texttt{""}) = q$}\\\bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\\end{tabular}\end{center}\pauseWhether a string \bl{$s$} is accepted by \bl{$A$}?\begin{center}\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}}A non-deterministic finite automaton consists again of:\begin{itemize}\item a finite set of states\item one of these states is the start state\item some states are accepting states, and\item there is transition \alert{relation}\medskip \end{itemize}\begin{center}\begin{tabular}{c}\bl{(q$_1$, a) $\rightarrow$ q$_2$}\\\bl{(q$_1$, a) $\rightarrow$ q$_3$}\\\end{tabular}\hspace{10mm}\begin{tabular}{c}\bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\\end{tabular}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\includegraphics[scale=0.7]{pics/ch5.jpg}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\begin{tabular}[b]{ll}\bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\\bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\\bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\\end{tabular}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\begin{tabular}[t]{ll}\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\\end{tabular}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\begin{tabular}[t]{ll}\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\\end{tabular}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\begin{tabular}[b]{ll}\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\\end{tabular}\end{center}\pause\bigskipWhy can't we just have an epsilon transition from the accepting states to the starting state?\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}\begin{textblock}{5}(1,2.5)\includegraphics[scale=0.5]{pics/ch5.jpg}\end{textblock}\begin{textblock}{11}(6.5,4.5)\begin{tabular}{r|cl}& a & b\\\hline$\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\$\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\$\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\$\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\$\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\$\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\$\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\\onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\\end{tabular}\end{textblock}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}A language is \alert{regular} iff there existsa regular expression that recognises all its strings.\bigskip\medskipor equivalently\bigskip\medskipA language is \alert{regular} iff there existsa deterministic finite automaton that recognises all its strings.\bigskip\pauseWhy is every finite set of strings a regular language?\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{center}\includegraphics[scale=0.5]{pics/ch3.jpg}\end{center}\begin{center}\includegraphics[scale=0.5]{pics/ch4.jpg}\\minimal automaton\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\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} tests wether\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 chance.\item All unmarked pairs can be merged.\end{enumerate}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]Given the function \begin{center}\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}$rev(\varnothing)$ & $\dn$ & $\varnothing$\\$rev(\epsilon)$ & $\dn$ & $\epsilon$\\$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)$\\$rev(r^*)$ & $\dn$ & $rev(r)^*$\\\end{tabular}}\end{center}and the set\begin{center}\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}\end{center}prove whether\begin{center}\bl{$L(rev(r)) = Rev (L(r))$}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{itemize}\item The star-case in our proof about the matcher needs the following lemma\begin{center}\bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}\end{center}\end{itemize}\bigskip\bigskip\begin{itemize}\item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip\item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{itemize}\item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip\item Give a regular expression that can recognise all strings that have at least one \bl{b}.\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]``I hate coding. I do not want to look at code.''\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: