# HG changeset patch # User Christian Urban # Date 1571317379 -3600 # Node ID 8da26d4c2ca87abcabc78cc2af4e10869f29bf52 # Parent 135fc1eba66a731e77968f69f063ba9f3f090f42 updated diff -r 135fc1eba66a -r 8da26d4c2ca8 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 135fc1eba66a -r 8da26d4c2ca8 handouts/ho03.tex --- a/handouts/ho03.tex Thu Oct 17 13:41:30 2019 +0100 +++ b/handouts/ho03.tex Thu Oct 17 14:02:59 2019 +0100 @@ -1,3 +1,4 @@ +% !TEX program = xelatex \documentclass{article} \usepackage{../style} \usepackage{../langs} @@ -914,24 +915,23 @@ Page~\pageref{dfa}).\bigskip \noindent -To start remember that we did not bother with defining and -implementing $\epsilon$NFAs: we immediately translated them into -equivalent NFAs. Equivalent in the sense of accepting the same -language (though we only claimed this and did not prove it -rigorously). Remember also that NFAs have non-deterministic -transitions defined as a relation or implemented as function returning -sets of states. This non-determinism is crucial for the Thompson -Construction to work (recall the cases for $\cdot$, $+$ and -${}^*$). But this non-determinism makes it harder with NFAs to decide -when a string is accepted or not; whereas such a decision is rather -straightforward with DFAs: recall their transition function is a -\emph{function} that returns a single state. So with DFAs we do not -have to search at all. What is perhaps interesting is the fact that -for every NFA we can find a DFA that also recognises the same -language. This might sound a bit paradoxical: NFA $\rightarrow$ -decision of acceptance hard; DFA $\rightarrow$ decision easy. But this -\emph{is} true\ldots but of course there is always a caveat---nothing -ever is for free in life. +To start, remember that we did not bother with defining and implementing +$\epsilon$NFAs: we immediately translated them into equivalent NFAs. +Equivalent in the sense of accepting the same language (though we only +claimed this and did not prove it rigorously). Remember also that NFAs +have non-deterministic transitions defined as a relation, or +alternatively my Scala implementation used transition functions returning sets of +states. This non-determinism is crucial for the Thompson Construction +to work (recall the cases for $\cdot$, $+$ and ${}^*$). But this +non-determinism makes it harder with NFAs to decide when a string is +accepted or not; whereas such a decision is rather straightforward with +DFAs: recall their transition function is a ``real'' function that returns +a single state. So with DFAs we do not have to search at all. What is +perhaps interesting is the fact that for every NFA we can find a DFA +that also recognises the same language. This might sound a bit +paradoxical: NFA $\rightarrow$ decision of acceptance hard; DFA +$\rightarrow$ decision easy. But this \emph{is} true\ldots but of course +there is always a caveat---nothing ever is for free in life. There are actually a number of methods for transforming a NFA into an equivalent DFA, but the most famous one is the \emph{subset diff -r 135fc1eba66a -r 8da26d4c2ca8 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 135fc1eba66a -r 8da26d4c2ca8 slides/slides03.tex --- a/slides/slides03.tex Thu Oct 17 13:41:30 2019 +0100 +++ b/slides/slides03.tex Thu Oct 17 14:02:59 2019 +0100 @@ -784,7 +784,7 @@ \frametitle{Subset Construction} -\begin{textblock}{5}(1,1) +\begin{textblock}{5}(1,1.5) \begin{center} \begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick, every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] diff -r 135fc1eba66a -r 8da26d4c2ca8 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 135fc1eba66a -r 8da26d4c2ca8 slides/slides04.tex --- a/slides/slides04.tex Thu Oct 17 13:41:30 2019 +0100 +++ b/slides/slides04.tex Thu Oct 17 14:02:59 2019 +0100 @@ -487,7 +487,7 @@ In programming languages they are often used to recognise:\medskip \begin{itemize} -\item symbols, digits +\item operands, digits \item identifiers \item numbers (non-leading zeros) \item keywords @@ -616,9 +616,9 @@ \bl{(ab + a) \cdot (c + bc)} \]\medskip -and the string $\bl{abc}$.\pause\pause\bigskip +and the string $\bl{abc}$.\pause\bigskip -Or, keywords are \pcode{if} and identifiers are +Or, keywords are \code{if} etc and identifiers are letters followed by ``letters + numbers + \_''$^*$ \[ @@ -741,48 +741,6 @@ \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Mkeps} - -Finding a (posix) value for recognising the empty string: - -\begin{center} -\begin{tabular}{lcl} - \bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\ - \bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ - & & \bl{then $Left(mkeps(r_1))$}\\ - & & \bl{else $Right(mkeps(r_2))$}\\ - \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ - \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\ -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Inject} - -Injecting (``Adding'') a character to a value\\[-12mm]\mbox{} - -\begin{center} -\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} - \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\ - \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ - \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ - \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ - \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ - \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ - \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\ -\end{tabular} -\end{center}\bigskip - -\footnotesize -\bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -814,7 +772,7 @@ \end{tikzpicture} \end{textblock} -\only<2->{ +\only<1->{ \begin{textblock}{6}(1,0.8) \begin{bubble}[6cm] \small @@ -930,7 +888,53 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Mkeps} + + Finding a (posix) value for recognising the empty string: + + \begin{center} + \begin{tabular}{lcl} + \bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\ + \bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ + & & \bl{then $Left(mkeps(r_1))$}\\ + & & \bl{else $Right(mkeps(r_2))$}\\ + \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ + \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\ + \end{tabular} + \end{center} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \begin{frame}[c] + \frametitle{Inject} + + Injecting (``Adding'') a character to a value\\[-12mm]\mbox{} + + \begin{center} + \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} + \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\ + \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ + \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ + \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ + \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ + \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ + \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\ + \end{tabular} + \end{center}\bigskip + + \footnotesize + \begin{tabular}{l@{\hspace{2mm}}l} + \bl{$inj$}: & 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; + 3rd arg $\mapsto$ a value\\ + & result $\mapsto$ a value + \end{tabular} + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Lexing}