slides/slides02.tex
author cu
Tue, 03 Oct 2017 23:01:06 +0100
changeset 512 a6aa52ecc1c5
parent 510 25580bf89ac0
child 514 bca9f8889a48
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     1
\documentclass[dvipsnames,14pt,t]{beamer}
258
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     2
\usepackage{../slides}
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     3
\usepackage{../graphics}
215
828303e8e4af updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
     4
\usepackage{../langs}
828303e8e4af updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
     5
\usepackage{../data}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
258
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     7
\hfuzz=220pt 
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     8
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     9
\lstset{language=Scala,
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    10
        style=mystyle,
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    11
        numbersep=0pt,
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    12
        numbers=none,
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    13
        xleftmargin=0mm}
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    14
398
c8ce95067c1a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 345
diff changeset
    15
\pgfplotsset{compat=1.12}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    16
258
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    17
\newcommand{\bl}[1]{\textcolor{blue}{#1}}     
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
    18
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
% beamer stuff 
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
    20
\renewcommand{\slidecaption}{CFL 02, King's College London}
258
1e4da6d2490c updated programs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    21
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    23
\begin{document}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
    26
\begin{frame}[t]
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    27
\frametitle{%
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
  \begin{tabular}{@ {}c@ {}}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
  \\[-3mm]
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
    30
  \LARGE Compilers and \\[-1mm] 
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
    31
  \LARGE Formal Languages (2)\\[3mm] 
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
  \end{tabular}}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    33
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
    34
  \normalsize
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    35
  \begin{center}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    36
  \begin{tabular}{ll}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    37
  Email:  & christian.urban at kcl.ac.uk\\
500
c502933be072 updated
Christian Urban <urbanc@in.tum.de>
parents: 442
diff changeset
    38
  Office: & N7.07 (North Wing, Bush House)\\
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
    39
  Slides: & KEATS 
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    40
  \end{tabular}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    41
  \end{center}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    42
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
    43
\end{frame}
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
    44
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    45
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    46
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
    47
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
    48
\frametitle{\begin{tabular}{@ {}c@ {}}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
    49
    An Efficient Regular\\[-1mm] 
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    50
    Expression Matcher\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    51
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    52
\footnotesize
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    53
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    54
  {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    55
\begin{tabular}{@{}cc@{}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    56
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    57
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    58
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    59
    x label style={at={(1.05,0.0)}},
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    60
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    61
    enlargelimits=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    62
    xtick={0,5,...,30},
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    63
    xmax=33,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    64
    ymax=35,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    65
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    66
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    67
    axis lines=left,
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    68
    width=5cm,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    69
    height=4.5cm, 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    70
    legend entries={Python,Ruby},  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    71
    legend pos=north west,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    72
    legend cell align=left  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    73
]
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    74
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    75
\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};  
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    76
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    77
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    78
&
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    79
\begin{tikzpicture}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    80
  \begin{axis}[
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    81
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    82
    x label style={at={(1.1,0.05)}},
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    83
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    84
    enlargelimits=false,
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
    85
    xtick={0,5000,...,10000},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
    86
    xmax=11500,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    87
    ymax=35,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    88
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    89
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    90
    axis lines=left,
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    91
    width=5cm,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    92
    height=4.5cm
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    93
]
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    94
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    95
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    96
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    97
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    98
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    99
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   100
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   101
\small
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   102
In the handouts is a similar graph with \bl{$(a^*)^* \cdot b$} for Java.
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   103
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   104
\end{frame}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   105
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   106
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   107
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   108
\begin{frame}[c]
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   109
\frametitle{Evil Regular Expressions}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   110
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   111
\begin{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   112
\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   113
\item Evil regular expressions\medskip
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   114
\begin{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   115
\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   116
\item \bl{$(a^*)^*$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   117
\item \bl{$([a$\,-\,$z]^+)^*$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   118
\item \bl{$(a + a \cdot a)^*$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   119
\item \bl{$(a + a?)^*$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   120
\end{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   121
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   122
\item sometimes also called \alert{catastrophic backtracking}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   123
\end{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   124
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   125
\end{frame}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   126
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   127
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   128
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   129
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   130
\frametitle{Languages}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   131
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   132
\begin{itemize}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   133
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   134
\item A \alert{\bf Language} is a set of strings, for example\medskip
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   135
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   136
\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   137
\end{center}\bigskip
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   138
332
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   139
\item \alert{\bf Concatenation} of strings and languages
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   140
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   141
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   142
\begin{tabular}{rcl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   143
\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   144
\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   145
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   146
\end{center}
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   147
\bigskip
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   148
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   149
\small
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   150
\item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   151
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   152
\[
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   153
\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   154
\]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   155
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   156
\end{itemize}  
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   157
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   158
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   159
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   160
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   161
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   162
\begin{frame}[c]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   163
\frametitle{The Power Operation}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   164
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   165
\begin{itemize}
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   166
\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   167
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   168
\begin{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   169
\begin{tabular}{lcl}
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   170
\bl{$A^0$}    & \bl{$\dn$} & \bl{$\{[]\}$}\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   171
\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   172
\end{tabular}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   173
\end{center}\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   174
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   175
\item[] For example
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   176
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   177
\begin{center}
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   178
\begin{tabular}{lcll}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   179
\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(\{[]\})$}\\
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   180
\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(\{[]\})$}\\
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   181
\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   182
\end{tabular}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   183
\end{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   184
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   185
\end{itemize}  
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   186
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   187
\end{frame}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   188
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   189
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   190
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   191
\begin{frame}[c]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   192
\frametitle{Homework Question}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   193
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   194
\begin{itemize}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   195
\item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   196
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   197
\begin{center}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   198
How many strings are in \bl{$A^4$}?
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   199
\end{center}\bigskip\medskip\pause
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   200
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   201
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   202
\begin{center}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   203
\begin{tabular}{l}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   204
What if \bl{$A = \{[a],[b],[c],[]\}$};\\ 
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   205
how many strings are then in \bl{$A^4$}?
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   206
\end{tabular}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   207
\end{center}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   208
\end{itemize}  
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   209
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   210
\end{frame}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   211
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   212
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   213
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   214
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   215
\frametitle{The Star Operation}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   216
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   217
\begin{itemize}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   218
\item The \alert{\bf Star} of a \underline{language}:
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   219
\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   220
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   221
\begin{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   222
\begin{tabular}{c}
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   223
\bl{$A\star \dn \bigcup_{0\le n} A^n$}
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   224
\end{tabular}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   225
\end{center}\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   226
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   227
\item[] This expands to 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   228
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   229
\[
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   230
\bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   231
\]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   232
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   233
\small
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   234
\[
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   235
\bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   236
  A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   237
\]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   238
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   239
\end{itemize}  
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   240
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   241
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   242
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   243
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   244
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   245
\begin{frame}[c]
507
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   246
\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] 
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   247
  Regular Expression\end{tabular}}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   248
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   249
\begin{textblock}{15}(1,4)
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   250
 \begin{tabular}{rcl}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   251
 \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   252
 \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   253
 \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   254
 \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   255
 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   256
 \bl{$L(r^*)$}           & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   257
  \end{tabular}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   258
\end{textblock}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   259
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   260
\begin{textblock}{6}(9,12)\small
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   261
\bl{$L$} is a function from regular expressions to 
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   262
sets of strings\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   263
\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   264
\end{textblock}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   265
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   266
\end{frame}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   267
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   268
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   269
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   270
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   271
\frametitle{Semantic Derivative}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   272
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   273
\begin{itemize}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   274
\item The \alert{\bf Semantic Derivative} of a 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   275
\underline{language}\\ wrt to a character \bl{$c$}:
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   276
\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   277
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   278
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   279
\bl{$\Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   280
\end{center}\bigskip\bigskip\bigskip
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   281
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   282
For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   283
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   284
\begin{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   285
\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   286
$\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   287
$\Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\  
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   288
$\Der\,a\,A$ & $=$ & $\{\}$\\\pause
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   289
\end{tabular}}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   290
\end{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   291
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   292
\small
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   293
We can extend this definition to strings
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   294
\[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   295
\bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}}
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   296
\]
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   297
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   298
\end{itemize}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   299
 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   300
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   301
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   302
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   303
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   304
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   305
\begin{frame}[c]
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   306
\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   307
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   308
\begin{bubble}[10cm]
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   309
\large
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   310
A regular expression \bl{$r$} matches a string~\bl{$s$} 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   311
provided
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   312
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   313
\begin{center}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   314
\bl{$s \in L(r)$}\\ 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   315
\end{center}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   316
\end{bubble}\bigskip\bigskip
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   317
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   318
\ldots and the point of the this lecture is 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   319
to decide this problem as fast as possible 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   320
(unlike Python, Ruby, Java etc)
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   321
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   322
\end{frame}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   323
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   324
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   325
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   326
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   327
\begin{frame}[t]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   328
\frametitle{Regular Expressions}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   329
15
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
   330
Their inductive definition:
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
   331
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
   332
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   333
\begin{textblock}{6}(2,7.5)
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   334
  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   335
  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & null\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   336
         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   337
         & \bl{$\mid$} & \bl{$c$}              & character\\
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   338
         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}  & sequence\\
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   339
         & \bl{$\mid$} & \bl{$r_1 + r_2$}      & alternative / choice\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   340
         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   341
  \end{tabular}
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   342
\end{textblock}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   343
  
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   344
\only<2->{\footnotesize
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   345
\begin{textblock}{9}(2,0.5)
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   346
\begin{bubble}[9.8cm]
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   347
\lstinputlisting{../progs/app01.scala}
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   348
\end{bubble}
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   349
\end{textblock}}  
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   350
  
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   351
\end{frame}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   352
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   353
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   354
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
332
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   355
\begin{frame}[c]
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   356
\frametitle{\begin{tabular}{c}
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   357
 When Are Two Regular\\[-1mm]
332
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   358
 Expressions Equivalent?\end{tabular}}
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   359
\large
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   360
\begin{center}
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   361
\bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$}
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   362
\end{center}  
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   363
  
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   364
\end{frame}
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   365
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   366
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   367
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   368
\begin{frame}[t]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   369
\frametitle{Concrete Equivalences}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   370
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   371
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   372
\bl{\begin{tabular}{rcl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   373
$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   374
$a + a$        & $\equiv$ & $a$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   375
$a + b$        & $\equiv$ & $b + a$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   376
$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   377
$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   378
$a \cdot a$       & $\not\equiv$ & $a$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   379
$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   380
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   381
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   382
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   383
\end{frame}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   384
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   385
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   386
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   387
\begin{frame}[t]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   388
\frametitle{Corner Cases}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   389
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   390
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   391
\bl{\begin{tabular}{rcl}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   392
$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   393
$a + \ONE$ & $\not\equiv$ & $a$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   394
$\ONE$ & $\equiv$ & $\ZERO^*$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   395
$\ONE^*$ & $\equiv$ & $\ONE$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   396
$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   397
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   398
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   399
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   400
\end{frame}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   401
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   402
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   403
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   404
\begin{frame}[t]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   405
\frametitle{Simplification Rules}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   406
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   407
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   408
\bl{\begin{tabular}{rcl}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   409
$r + \ZERO$  & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   410
$\ZERO + r$  & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   411
$r \cdot \ONE$ & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   412
$\ONE \cdot r$     & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   413
$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   414
$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   415
$r + r$ & $\equiv$ & $r$
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   416
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   417
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   418
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   419
\end{frame}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   420
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   421
118
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 117
diff changeset
   422
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 117
diff changeset
   423
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   424
\begin{frame}[t]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   425
\frametitle{A Matching Algorithm}
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   426
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   427
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   428
\ldots{}whether a regular expression can match the empty string:
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   429
\begin{center}
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   430
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   431
\bl{$nullable(\ZERO)$}    & \bl{$\dn$} & \bl{\textit{false}}\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   432
\bl{$nullable(\ONE)$}       & \bl{$\dn$} & \bl{\textit{true}}\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   433
\bl{$nullable (c)$}             & \bl{$\dn$} & \bl{\textit{false}}\\
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   434
\bl{$nullable (r_1 + r_2)$}     & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\ 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   435
\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   436
\bl{$nullable (r^*)$}           & \bl{$\dn$} & \bl{\textit{true}}\\
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   437
\end{tabular}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   438
\end{center}
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   439
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   440
\end{frame}
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   441
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   442
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   443
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   444
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   445
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   446
\frametitle{The Derivative of a Rexp}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   447
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   448
\large
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   449
If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular 
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   450
expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   451
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   452
\small
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   453
\bl{$\der\,c\,r$} gives the answer, Brzozowski 1964
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   454
\end{frame}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   455
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   456
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   457
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   458
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   459
\frametitle{The Derivative of a Rexp}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   460
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   461
\begin{center}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   462
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   463
  \bl{$\der\, c\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   464
  \bl{$\der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   465
  \bl{$\der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   466
  \bl{$\der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   467
  \bl{$\der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   468
  & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\ 
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   469
  & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   470
  \bl{$\der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   471
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   472
  \bl{$\ders\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   473
  \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   474
  \end{tabular}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   475
\end{center}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   476
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   477
\end{frame}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   478
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   479
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   480
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   481
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   482
\frametitle{Examples}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   483
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   484
Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   485
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   486
\begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   487
\begin{tabular}{l}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   488
\bl{$\der\,a\,r =\;?$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   489
\bl{$\der\,b\,r =\;?$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   490
\bl{$\der\,c\,r =\;?$}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   491
\end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   492
\end{center}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   493
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   494
\end{frame}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   495
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   496
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   497
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   498
\begin{frame}[c]
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   499
\frametitle{The Algorithm}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   500
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   501
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   502
\begin{tabular}{l} 
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   503
\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\,r\,s)$}  
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   504
\end{tabular}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   505
\end{center}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   506
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   507
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   508
\end{frame}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   509
%%%%%%%%%%%%%%%%%
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   510
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   511
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   512
\begin{frame}[t]
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   513
\frametitle{An Example}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   514
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   515
Does \bl{$r_1$} match \bl{$abc$}?
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   516
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   517
\begin{tabular}{@{}rl@{}l@{}}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   518
Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = \der\,a\,r_1)$}\smallskip\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   519
Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = \der\,b\,r_2)$}\smallskip\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   520
Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = \der\,c\,r_3)$}\smallskip\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   521
Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   522
        & test whether \bl{$r_4$} can recognise\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   523
        & the empty string\smallskip\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   524
Output: & result of the test\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   525
        & $\Rightarrow \bl{\textit{true}} \,\text{or}\, 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   526
                       \bl{\textit{false}}$\\        
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   527
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   528
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   529
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   530
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   531
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   532
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   533
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   534
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   535
\begin{frame}[c]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   536
\frametitle{The Idea of the Algorithm}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   537
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   538
If we want to recognise the string \bl{$abc$} with regular 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   539
expression \bl{$r_1$} then\medskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   540
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   541
\begin{enumerate}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   542
\item \bl{$\Der\,a\,(L(r_1))$}\pause
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   543
\item \bl{$\Der\,b\,(\Der\,a\,(L(r_1)))$}\pause
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   544
\item \bl{$\Der\,c\,(\Der\,b\,(\Der\,a\,(L(r_1))))$}\bigskip
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   545
\item finally we test whether the empty string is in this 
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   546
set; same for  \bl{$\Ders\,abc\,(L(r_1))$}.\medskip
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   547
\end{enumerate}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   548
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   549
The matching algorithm works similarly, just over regular expressions instead of sets.
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   550
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   551
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   552
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   553
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   554
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   555
\begin{frame}[c]
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   556
\frametitle{Oops\ldots\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   557
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   558
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   559
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   560
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   561
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   562
    x label style={at={(1.05,0.0)}},
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   563
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   564
    enlargelimits=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   565
    xtick={0,5,...,30},
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   566
    xmax=31,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   567
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   568
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   569
    axis lines=left,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   570
    width=7cm,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   571
    height=7cm, 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   572
    legend entries={Python,Ruby,Scala V1},  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   573
    legend pos=outer north east,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   574
    legend cell align=left  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   575
]
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   576
\addplot[blue,mark=*, mark options={fill=white}] 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   577
  table {re-python.data};
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   578
\addplot[brown,mark=pentagon*, mark options={fill=white}] 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   579
  table {re-ruby.data};  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   580
\addplot[red,mark=triangle*,mark options={fill=white}] 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   581
  table {re1.data};  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   582
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   583
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   584
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   585
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   586
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   587
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   588
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   589
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   590
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   591
\frametitle{A Problem}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   592
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   593
We represented the ``n-times'' \bl{$a^{\{n\}}$} as a 
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   594
sequence regular expression:
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   595
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   596
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   597
\begin{tabular}{rl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   598
1: & \bl{$a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   599
2: & \bl{$a\cdot a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   600
3: & \bl{$a\cdot a\cdot a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   601
& \ldots\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   602
13: & \bl{$a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   603
& \ldots\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   604
20:
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   605
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   606
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   607
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   608
This problem is aggravated with \bl{$a^?$} being represented 
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   609
as \bl{$a + \ONE$}.
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   610
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   611
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   612
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   613
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   614
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   615
\frametitle{Solving the Problem}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   616
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   617
What happens if we extend our regular expressions
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   618
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   619
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   620
\begin{tabular}{rcl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   621
\bl{$r$} & \bl{$::=$} & \bl{\ldots}\\
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   622
             & \bl{$\mid$} & \bl{$r^{\{n\}}$}\\
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   623
             & \bl{$\mid$} & \bl{$r^?$} 
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   624
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   625
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   626
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   627
What is their meaning?\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   628
What are the cases for \bl{$nullable$} and \bl{$\der$}?
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   629
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   630
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   631
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   632
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   633
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   634
\begin{frame}[t]
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   635
\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   636
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   637
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   638
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   639
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   640
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   641
    x label style={at={(1.05,0.0)}},   
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   642
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   643
    enlargelimits=false,
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   644
    xtick={0,200,...,1100},
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   645
    xmax=1200,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   646
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   647
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   648
    axis lines=left,
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   649
    width=8cm,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   650
    height=6.5cm, 
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   651
    legend entries={Python,Ruby,Scala V1,Scala V2},  
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   652
    legend pos=outer north east,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   653
    legend cell align=left  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   654
]
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   655
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   656
\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};  
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   657
\addplot[red,mark=triangle*,mark options={fill=white}] table {re1.data};  
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   658
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   659
\end{axis}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   660
\end{tikzpicture}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   661
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   662
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   663
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   664
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   665
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   666
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   667
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   668
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   669
\frametitle{Examples}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   670
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   671
Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   672
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   673
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   674
\begin{tabular}{l}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   675
\bl{$\der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   676
\bl{$\der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   677
\bl{$\der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   678
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   679
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   680
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   681
What are these regular expressions equivalent to?
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   682
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   683
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   684
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   685
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   686
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   687
\begin{frame}[c]
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   688
\frametitle{Simplifiaction}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   689
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   690
\begin{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   691
\bl{\begin{tabular}{rcl}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   692
$r + \ZERO$       & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   693
$\ZERO + r$       & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   694
$r \cdot \ONE$    & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   695
$\ONE \cdot r$    & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   696
$r \cdot \ZERO$   & $\Rightarrow$ & $\ZERO$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   697
$\ZERO \cdot r$   & $\Rightarrow$ & $\ZERO$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   698
$r + r$           & $\Rightarrow$ & $r$
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   699
\end{tabular}}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   700
\end{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   701
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   702
\footnotesize
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   703
\lstinputlisting{../progs/app60.scala}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   704
\end{frame}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   705
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   706
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   707
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   708
\begin{frame}[c]
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   709
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   710
\footnotesize
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   711
\lstinputlisting{../progs/app6.scala}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   712
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   713
\end{frame}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   714
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   715
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   716
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   717
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   718
\begin{frame}[t]
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   719
\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   720
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   721
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   722
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   723
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   724
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   725
    x label style={at={(1.05,0.0)}},     
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   726
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   727
    enlargelimits=false,
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   728
    xtick={0,5000,...,10000},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   729
    xmax=11000,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   730
    ymax=35,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   731
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   732
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   733
    axis lines=left,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   734
    width=9cm,
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   735
    height=7cm,
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   736
    legend entries={Scala V2,Scala V3},  
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   737
    legend pos=north east
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   738
]
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   739
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   740
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   741
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   742
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   743
\end{center}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   744
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   745
\end{frame}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   746
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   747
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   748
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   749
\begin{frame}[c]
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   750
\frametitle{\bl{$(a^*)^* \cdot b$}}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   751
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   752
\begin{center}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   753
\begin{tikzpicture}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   754
  \begin{axis}[
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   755
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   756
    x label style={at={(1.09,0.0)}},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   757
    ylabel={time in secs},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   758
    enlargelimits=false,
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   759
    xmax=27,
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   760
    xtick={0,5,...,20},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   761
    ytick={0,5,...,25},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   762
    ymax=13,
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   763
    scaled ticks=false,
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   764
    axis lines=left,
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   765
    width=9cm,
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   766
    height=5cm, 
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   767
    legend entries={Scala V2},
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   768
    legend pos=north west,
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   769
    legend cell align=left]
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   770
\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   771
%% still needs to be done
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   772
%%\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   773
\end{axis}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   774
\end{tikzpicture}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   775
\end{center}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   776
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   777
\end{frame}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   778
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   779
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   780
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   781
\begin{frame}[c]
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   782
\frametitle{\bl{$(a^*)^* \cdot b$}}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   783
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   784
\begin{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   785
\begin{tikzpicture}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   786
  \begin{axis}[
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   787
    xlabel={$n$},
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   788
    x label style={at={(1.09,0.0)}},
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   789
    ylabel={time in secs},
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   790
    enlargelimits=false,
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   791
    ytick={0,10,...,60},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   792
    ymax=65,
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   793
    axis lines=left,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   794
    width=9cm,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   795
    height=5cm, 
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   796
    legend entries={Scala V3},
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   797
    legend pos=north west,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   798
    legend cell align=left]
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   799
\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   800
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   801
\end{axis}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   802
\end{tikzpicture}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   803
\end{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   804
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   805
\end{frame}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   806
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   807
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   808
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   809
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   810
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   811
\begin{frame}[t]
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   812
\frametitle{What is good about this Alg.}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   813
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   814
\begin{itemize}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   815
\item extends to most regular expressions, for example
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   816
\bl{$\sim r$}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   817
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   818
\item is easy to implement in a functional language
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   819
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   820
\item the algorithm is already quite old; there is still
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   821
  work to be done to use it as a tokenizer (that is brand new work)
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   822
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   823
\item we can prove its correctness\ldots
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   824
\end{itemize}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   825
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   826
\end{frame}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   827
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   828
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   829
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   830
\begin{frame}[t]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   831
\frametitle{Proofs about Rexps}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   832
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   833
Remember their inductive definition:\\[5cm]
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   834
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   835
\begin{textblock}{6}(5,5)
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   836
  \begin{tabular}{@ {}rrl}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   837
  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   838
         & \bl{$\mid$} & \bl{$\ONE$}     \\
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   839
         & \bl{$\mid$} & \bl{$c$}            \\
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   840
         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   841
         & \bl{$\mid$} & \bl{$r_1 + r_2$}    \\
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   842
         & \bl{$\mid$} & \bl{$r^*$}          \\
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   843
  \end{tabular}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   844
  \end{textblock}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   845
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   846
If we want to prove something, say a property \bl{$P(r)$}, for all regular expressions \bl{$r$} then \ldots
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   847
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   848
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   849
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   850
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   851
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   852
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   853
\frametitle{Proofs about Rexp (2)}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   854
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   855
\begin{itemize}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   856
\item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   857
\item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   858
holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   859
\item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   860
holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   861
\item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   862
holds for \bl{$r$}.
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   863
\end{itemize}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   864
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   865
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   866
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   867
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   868
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   869
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   870
\frametitle{Proofs about Rexp (3)}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   871
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   872
Assume \bl{$P(r)$} is the property:
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   873
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   874
\begin{center}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   875
\bl{$nullable(r)$} if and only if \bl{$[] \in L(r)$}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   876
\end{center}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   877
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   878
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   879
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   880
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   881
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   882
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   883
\frametitle{Proofs about Rexp (4)}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   884
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   885
\begin{center}
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   886
\bl{\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   887
$rev(\ZERO)$   & $\dn$ & $\ZERO$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   888
$rev(\ONE)$      & $\dn$ & $\ONE$\\
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   889
$rev(c)$             & $\dn$ & $c$\\
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   890
$rev(r_1 + r_2)$     & $\dn$ & $rev(r_1) + rev(r_2)$\\
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   891
$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   892
$rev(r^*)$           & $\dn$ & $rev(r)^*$\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   893
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   894
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   895
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   896
We can prove
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   897
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   898
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   899
\bl{$L(rev(r)) = \{s^{-1} \;|\; s \in L(r)\}$}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   900
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   901
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   902
by induction on \bl{$r$}.
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   903
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   904
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   905
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   906
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   907
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   908
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   909
\begin{frame}[c]
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   910
\frametitle{\begin{tabular}{c}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   911
  Correctness Proof\\[-1mm] for our Matcher\end{tabular}}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   912
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   913
\begin{itemize}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   914
\item We started from
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   915
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   916
\begin{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   917
\begin{tabular}{rp{4cm}}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   918
  & \bl{$s \in L(r)$}\medskip\\
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   919
\bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause  
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   920
\end{tabular}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   921
\end{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   922
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   923
\item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we 
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   924
have
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   925
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   926
\begin{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   927
\begin{tabular}{rp{4cm}}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   928
\bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   929
\bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   930
\bl{$\dn$} & \bl{$matches\,s\,r$}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   931
\end{tabular}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   932
\end{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   933
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   934
\end{itemize}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   935
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   936
\end{frame}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   937
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   938
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   939
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   940
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   941
\frametitle{Proofs about Rexp (5)}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   942
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   943
Let \bl{$Der\,c\,A$} be the set defined as
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   944
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   945
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   946
\bl{$\Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   947
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   948
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   949
We can prove
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   950
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   951
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   952
\bl{$L(\der\,c\,r) = \Der\,c\,(L(r))$}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   953
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   954
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   955
by induction on \bl{$r$}.
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   956
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   957
\end{frame}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   958
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   959
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   960
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   961
\begin{frame}[c]
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   962
\frametitle{Proofs about Strings}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   963
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   964
If we want to prove something, say a property \bl{$P(s)$}, for all strings \bl{$s$} then \ldots\bigskip
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   965
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   966
\begin{itemize}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   967
\item \bl{$P$} holds for the empty string, and\medskip
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   968
\item \bl{$P$} holds for the string \bl{$c\!::\!s$} under the assumption that \bl{$P$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   969
already holds for \bl{$s$}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   970
\end{itemize}
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   971
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   972
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   973
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   974
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   975
\begin{frame}[c]
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   976
\frametitle{Proofs about Strings (2)}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   977
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   978
We can then prove
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   979
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   980
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   981
\bl{$\Ders\,s\,(L(r)) = L(\ders\,s\,r)$}  
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   982
\end{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   983
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   984
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   985
We can finally prove
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   986
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   987
\begin{center}
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   988
\bl{$matches\,s\,r$}  if and only if  \bl{$s \in L(r)$} 
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   989
\end{center}
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   990
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   991
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   992
\end{frame}
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
   993
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   994
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
   995
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
   996
\begin{frame}[c]
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
   997
\frametitle{Epilogue}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
   998
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
   999
\footnotesize
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1000
\begin{center}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1001
\begin{tabular}{cc}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1002
\begin{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1003
\begin{axis}[
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1004
    title={\small{}Graph: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}},
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1005
    xlabel={$n$},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1006
    x label style={at={(1.04,0.0)}},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1007
    ylabel={time in secs},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1008
    enlargelimits=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1009
    xmax=7100000,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1010
    ytick={0,5,...,30},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1011
    ymax=33,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1012
    %scaled ticks=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1013
    axis lines=left,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1014
    width=5cm,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1015
    height=5cm, 
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1016
    legend entries={Scala V3, Scala V4},
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1017
    legend style={at={(0.1,-0.2)},anchor=north}]
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1018
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1019
\addplot[purple,mark=square*,mark options={fill=white}] table {re4.data};
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1020
\end{axis}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1021
\end{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1022
&
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1023
\begin{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1024
\begin{axis}[
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1025
    title={\small{}Graph: \bl{$(a^*)^* \cdot b$}},
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1026
    xlabel={$n$},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1027
    x label style={at={(1.09,0.0)}},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1028
    ylabel={time in secs},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1029
    enlargelimits=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1030
    xmax=8100000,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1031
    ytick={0,5,...,30},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1032
    ymax=33,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1033
    %scaled ticks=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1034
    axis lines=left,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1035
    width=5cm,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1036
    height=5cm, 
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1037
    legend entries={Scala V3, Scala V4},
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1038
    legend style={at={(0.1,-0.2)},anchor=north}]
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1039
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1040
\addplot[purple,mark=square*,mark options={fill=white}] table {re4a.data};
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1041
\end{axis}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1042
\end{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1043
\end{tabular}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1044
\end{center}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1045
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1046
\only<2->{\footnotesize
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1047
\begin{textblock}{9}(0.5,8)
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1048
\begin{bubble}[11.8cm]
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1049
\lstinputlisting[numbers=none]{../progs/app52.scala}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1050
\end{bubble}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1051
\end{textblock}} 
510
cu
parents: 507
diff changeset
  1052
 
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1053
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1054
\end{frame}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1055
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1056
\end{document}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1057
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1058
%%% Local Variables:  
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1059
%%% mode: latex
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1060
%%% TeX-master: t
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1061
%%% End: 
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1062