slides/slides02.tex
author Christian Urban <urbanc@in.tum.de>
Mon, 01 Oct 2018 01:11:42 +0100
changeset 566 b153c04834eb
parent 565 2be8c4c77418
child 567 4573d36d0b2f
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\\
564
b5d57d7064bb updated
Christian Urban <urbanc@in.tum.de>
parents: 514
diff changeset
    38
  Office: & N\liningnums{7.07} (North Wing, Bush House)\\
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
    39
  Slides: & KEATS (also homework is there)
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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
    47
\begin{frame}[t]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
    48
  \frametitle{\Large
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
    49
    Lets Implement an Efficient\\[-2mm] 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
    50
    Regular Expression Matcher}
263
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}
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
    54
  {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\medskip\\
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,
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
    72
    legend cell align=left]
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    73
\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
    74
\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
    75
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    76
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    77
&
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    78
\begin{tikzpicture}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    79
  \begin{axis}[
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    80
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    81
    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
    82
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    83
    enlargelimits=false,
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
    84
    xtick={0,5000,...,10000},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
    85
    xmax=11500,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    86
    ymax=35,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    87
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    88
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    89
    axis lines=left,
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    90
    width=5cm,
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
    91
    height=4.5cm,
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
    92
    legend entries={Scala V2,Scala V3},
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
    93
    legend pos=north east,
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
    94
    legend cell align=left]
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
    95
\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
    96
\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
    97
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    98
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
    99
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   100
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   101
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   102
\small
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   103
In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8.
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   104
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   105
\end{frame}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   106
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   107
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   108
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   109
\begin{frame}[c]
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   110
\frametitle{Evil Regular Expressions}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   111
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   112
\begin{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   113
\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
   114
\item Evil regular expressions\medskip
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   115
\begin{itemize}
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   116
\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   117
\item \bl{$(a^*)^*$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   118
\item \bl{$([a$\,-\,$z]^+)^*$}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   119
\item \bl{$(a + a \cdot a)^*$}
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   120
\item \bl{$(a + a^?)^*$}
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   121
\end{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   122
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   123
\item sometimes also called \alert{catastrophic backtracking}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   124
\end{itemize}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   125
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   126
\end{frame}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   127
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263
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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   130
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   131
\frametitle{Languages}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   132
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   133
\begin{itemize}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   134
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   135
\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
   136
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   137
\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
   138
\end{center}\bigskip
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   139
332
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   140
\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
   141
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   142
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   143
\begin{tabular}{rcl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   144
\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
   145
\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
   146
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   147
\end{center}
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   148
\bigskip
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   149
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   150
\small
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   151
\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
   152
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   153
\[
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   154
\bl{A \,@\, B = \{fooa, foob, bara, barb\}}
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
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   157
\end{itemize}  
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   158
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   159
\end{frame}
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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   163
\begin{frame}[c]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   164
\frametitle{The Power Operation}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   165
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   166
\begin{itemize}
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   167
\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
   168
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   169
\begin{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   170
\begin{tabular}{lcl}
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   171
\bl{$A^0$}    & \bl{$\dn$} & \bl{$\{[]\}$}\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   172
\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
   173
\end{tabular}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   174
\end{center}\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   175
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   176
\item[] For example
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   177
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   178
\begin{center}
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   179
\begin{tabular}{lcl@{\hspace{10mm}}l}
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   180
\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   181
\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   182
\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   183
\end{tabular}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   184
\end{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   185
261
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   186
\end{itemize}  
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   187
24531cfaa36a updated handouts
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 258
diff changeset
   188
\end{frame}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   189
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   190
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   191
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   192
\begin{frame}[c]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   193
\frametitle{Homework Question}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   194
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   195
\begin{itemize}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   196
\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
   197
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   198
\begin{center}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   199
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
   200
\end{center}\bigskip\medskip\pause
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
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   203
\begin{center}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   204
\begin{tabular}{l}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   205
What if \bl{$A = \{[a],[b],[c],[]\}$};\\ 
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   206
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
   207
\end{tabular}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   208
\end{center}
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   209
\end{itemize}  
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   210
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   211
\end{frame}
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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   215
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   216
\frametitle{The Star Operation}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   217
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   218
\begin{itemize}
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   219
\item The \alert{\bf Kleene Star} of a \underline{language}:
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   220
\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   221
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   222
\begin{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   223
\begin{tabular}{c}
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   224
\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
   225
\end{tabular}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   226
\end{center}\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   227
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   228
\item[] This expands to 
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
\[
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   231
\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
   232
\]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   233
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   234
or
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   235
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   236
\small
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
\bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   239
  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
   240
\]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   241
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   242
\end{itemize}  
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
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   245
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   246
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   247
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   248
\begin{frame}[c]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   249
\frametitle{
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   250
    The Meaning of a\\[-2mm] 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   251
    Regular Expression}
507
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   252
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   253
\begin{textblock}{15}(1,4)
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   254
 \begin{tabular}{rcl}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   255
 \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   256
 \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   257
 \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   258
 \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
   259
 \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
   260
 \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
   261
  \end{tabular}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   262
\end{textblock}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   263
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   264
\begin{textblock}{9}(6,12)\small
507
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   265
\bl{$L$} is a function from regular expressions to 
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   266
sets of strings (languages):\smallskip\\
507
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   267
\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   268
\end{textblock}
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
\end{frame}
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   271
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   272
566
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   273
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   274
\begin{frame}[c]
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   275
\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   276
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   277
\bigskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   278
homework (written exam 80\%)\\
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   279
coursework (20\%; first one today)\\
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   280
submission Fridays @ 18:00 -- accepted Mondays
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   281
\mbox{}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   282
\end{frame}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   283
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   284
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   285
507
fdbc7d0ec04f updated
Christian Urban <urbanc@in.tum.de>
parents: 500
diff changeset
   286
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   287
\begin{frame}[t]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   288
\frametitle{Semantic Derivative\\[5mm]}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   289
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   290
  
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   291
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   292
\begin{itemize}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   293
\item The \alert{\bf Semantic Derivative} of a 
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   294
\underline{language}\\ w.r.t.~to a character \bl{$c$}:
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   295
\bigskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   296
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   297
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   298
\bl{$\Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   299
\end{center}\bigskip
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   300
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   301
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
   302
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   303
\begin{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   304
\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
   305
$\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   306
$\Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\  
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   307
$\Der\,a\,A$ & $=$ & $\{\}$\pause
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   308
\end{tabular}}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   309
\end{center}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   310
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   311
\small
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   312
We can extend this definition to strings
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   313
\[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   314
\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
   315
\]
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   316
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   317
\end{itemize}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   318
 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   319
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   320
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   321
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   322
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   323
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   324
\begin{frame}[c]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   325
\frametitle{The Specification\\ for Matching}
512
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   326
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   327
\begin{bubble}[10cm]
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   328
\large
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   329
A regular expression \bl{$r$} matches a string~\bl{$s$} 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   330
provided
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   331
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   332
\begin{center}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   333
\bl{$s \in L(r)$}\\ 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   334
\end{center}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   335
\end{bubble}\bigskip\bigskip
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   336
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   337
\ldots and the point of the this lecture is 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   338
to decide this problem as fast as possible 
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   339
(unlike Python, Ruby, Java etc)
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   340
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   341
\end{frame}
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   342
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   343
a6aa52ecc1c5 updated
cu
parents: 510
diff changeset
   344
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   345
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   346
\begin{frame}[t]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   347
\frametitle{Regular Expressions}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   348
15
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
   349
Their inductive definition:
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
   350
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
   351
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   352
\begin{textblock}{6}(2,7.5)
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   353
  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   354
  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   355
         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   356
         & \bl{$\mid$} & \bl{$c$}              & single character\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   357
         & \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
   358
         & \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
   359
         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   360
  \end{tabular}
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   361
\end{textblock}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   362
  
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   363
\only<2->{\footnotesize
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   364
\begin{textblock}{9}(2,0.5)
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   365
\begin{bubble}[9.8cm]
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   366
\lstinputlisting{../progs/app01.scala}
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   367
\end{bubble}
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   368
\end{textblock}}  
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   369
  
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   370
\end{frame}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   371
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   372
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   373
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
332
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   374
\begin{frame}[c]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   375
\frametitle{
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   376
 When Are Two Regular\\[-1mm]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   377
 Expressions Equivalent?}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   378
332
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   379
\large
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   380
\begin{center}
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   381
\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
   382
\end{center}  
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   383
  
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   384
\end{frame}
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   385
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   386
4755ad4b457b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 325
diff changeset
   387
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   388
\begin{frame}[t]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   389
\frametitle{Concrete Equivalences}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   390
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   391
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   392
\bl{\begin{tabular}{rcl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   393
$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   394
$a + a$        & $\equiv$ & $a$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   395
$a + b$        & $\equiv$ & $b + a$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   396
$(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
   397
$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
   398
$a \cdot a$       & $\not\equiv$ & $a$\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   399
$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
   400
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   401
\end{center}
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
\end{frame}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   404
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   405
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{frame}[t]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   408
\frametitle{Corner Cases}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   409
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   410
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   411
\bl{\begin{tabular}{rcl}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   412
$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   413
$a + \ONE$ & $\not\equiv$ & $a$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   414
$\ONE$ & $\equiv$ & $\ZERO^*$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   415
$\ONE^*$ & $\equiv$ & $\ONE$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   416
$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   417
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   418
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   419
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   420
\end{frame}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   421
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   422
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   423
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   424
\begin{frame}[t]
336
7c80b9b6f713 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   425
\frametitle{Simplification Rules}
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   426
 
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   427
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   428
\bl{\begin{tabular}{rcl}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   429
$r + \ZERO$  & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   430
$\ZERO + r$  & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   431
$r \cdot \ONE$ & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   432
$\ONE \cdot r$     & $\equiv$ & $r$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   433
$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   434
$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   435
$r + r$ & $\equiv$ & $r$
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   436
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   437
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   438
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   439
\end{frame}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   440
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   441
118
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 117
diff changeset
   442
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 117
diff changeset
   443
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   444
\begin{frame}[t]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   445
\frametitle{A Matching Algorithm (1)}
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   446
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   447
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   448
\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
   449
\begin{center}
117
25999de692b2 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   450
\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
   451
\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
   452
\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
   453
\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
   454
\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
   455
\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
   456
\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
   457
\end{tabular}
16
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   458
\end{center}
Christian Urban <urbanc@in.tum.de>
parents: 15
diff changeset
   459
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   460
\end{frame}
11
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   461
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   462
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   463
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   464
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5353d405e4e6 added slides 2
Christian Urban <urbanc@in.tum.de>
parents: 7
diff changeset
   465
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   466
\frametitle{The Derivative of a Rexp}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   467
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   468
\large
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   469
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
   470
expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   471
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   472
\small
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   473
\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
   474
\end{frame}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   475
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   476
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   477
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   478
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   479
\frametitle{The Derivative of a Rexp}
7
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{center}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   482
\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
   483
  \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
   484
  \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
   485
  \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
   486
  \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
   487
  \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
   488
  & & \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
   489
  & & \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
   490
  \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
   491
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   492
  \bl{$\ders\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   493
  \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
   494
  \end{tabular}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   495
\end{center}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   496
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   497
\end{frame}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   498
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   499
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   500
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   501
\begin{frame}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   502
\frametitle{Examples}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   503
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   504
Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   505
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   506
\begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   507
\begin{tabular}{l}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   508
\bl{$\der\,a\,r =\;?$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   509
\bl{$\der\,b\,r =\;?$}\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   510
\bl{$\der\,c\,r =\;?$}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   511
\end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   512
\end{center}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   513
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   514
\end{frame}
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   515
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   516
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   517
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   518
\begin{frame}[c]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   519
\frametitle{\mbox{The Brzozowski Algorithm}}
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   520
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   521
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   522
\begin{tabular}{l} 
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   523
\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}  
431
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   524
\end{tabular}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   525
\end{center}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   526
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   527
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   528
\end{frame}
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   529
%%%%%%%%%%%%%%%%%
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   530
c7d4ee344451 updated
Christian Urban <urbanc@in.tum.de>
parents: 429
diff changeset
   531
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   532
\begin{frame}[t]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   533
\frametitle{Brzozowski: An Example}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   534
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   535
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
   536
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   537
\begin{tabular}{@{}rl@{}l@{}}
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   538
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
   539
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
   540
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
   541
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
   542
        & test whether \bl{$r_4$} can recognise\\
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   543
        & the empty string\medskip\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   544
Output: & result of the test\\
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   545
        & $\Rightarrow \bl{\textit{true}} \,\text{or}\, 
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   546
                       \bl{\textit{false}}$\\        
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   547
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   548
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   549
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   550
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   551
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   552
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   553
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   554
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   555
\begin{frame}[c]
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   556
\frametitle{The Idea of the Algorithm}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   557
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   558
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
   559
expression \bl{$r_1$} then\medskip
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   560
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   561
\begin{enumerate}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   562
\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
   563
\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
   564
\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
   565
\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
   566
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
   567
\end{enumerate}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   568
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   569
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
   570
\end{frame}
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   571
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   572
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   573
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   574
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   575
\begin{frame}[c]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   576
\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
   577
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   578
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   579
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   580
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   581
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   582
    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
   583
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   584
    enlargelimits=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   585
    xtick={0,5,...,30},
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   586
    xmax=31,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   587
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   588
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   589
    axis lines=left,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   590
    width=7cm,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   591
    height=7cm, 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   592
    legend entries={Python,Ruby,Scala V1},  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   593
    legend pos=outer north east,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   594
    legend cell align=left  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   595
]
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   596
\addplot[blue,mark=*, mark options={fill=white}] 
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   597
  table {re-python.data};
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   598
\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
   599
  table {re-ruby.data};  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   600
\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
   601
  table {re1.data};  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   602
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   603
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   604
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   605
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   606
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   607
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   608
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   609
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   610
\begin{frame}[t]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   611
\frametitle{A Problem\medskip}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   612
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   613
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
   614
sequence regular expression:
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   615
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   616
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   617
\begin{tabular}{rl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   618
1: & \bl{$a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   619
2: & \bl{$a\cdot a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   620
3: & \bl{$a\cdot a\cdot a$}\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   621
& \ldots\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   622
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
   623
& \ldots\\
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   624
20:
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   625
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   626
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   627
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   628
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
   629
as \bl{$a + \ONE$}.
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   630
\end{frame}
263
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}[c]
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   635
\frametitle{Solving the Problem}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   636
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   637
What happens if we extend our regular expressions with explicit 
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   638
constructors
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   639
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   640
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   641
\begin{tabular}{rcl}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   642
\bl{$r$} & \bl{$::=$} & \bl{\ldots}\\
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   643
             & \bl{$\mid$} & \bl{$r^{\{n\}}$}\\
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
   644
             & \bl{$\mid$} & \bl{$r^?$} 
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   645
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   646
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   647
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   648
What is their meaning?\\
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   649
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
   650
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   651
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   652
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   653
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   654
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   655
\begin{frame}[t]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   656
\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   657
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   658
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   659
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   660
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   661
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   662
    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
   663
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   664
    enlargelimits=false,
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   665
    xtick={0,200,...,1100},
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   666
    xmax=1200,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   667
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   668
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   669
    axis lines=left,
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   670
    width=8cm,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   671
    height=6.5cm, 
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   672
    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
   673
    legend pos=outer north east,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   674
    legend cell align=left  
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   675
]
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   676
\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
   677
\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
   678
\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
   679
\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
   680
\end{axis}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   681
\end{tikzpicture}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   682
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   683
335
2d112a7b29eb updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   684
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   685
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   686
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   687
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   688
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   689
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   690
\frametitle{Examples}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   691
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   692
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
   693
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   694
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   695
\begin{tabular}{l}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   696
\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
   697
\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
   698
\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
   699
\end{tabular}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   700
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   701
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   702
What are these regular expressions equivalent to?
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   703
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   704
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   705
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   706
435
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]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   709
\frametitle{Simplification Rules}
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   710
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   711
\begin{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   712
\bl{\begin{tabular}{rcl}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   713
$r + \ZERO$       & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   714
$\ZERO + r$       & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   715
$r \cdot \ONE$    & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   716
$\ONE \cdot r$    & $\Rightarrow$ & $r$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   717
$r \cdot \ZERO$   & $\Rightarrow$ & $\ZERO$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   718
$\ZERO \cdot r$   & $\Rightarrow$ & $\ZERO$\\
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   719
$r + r$           & $\Rightarrow$ & $r$
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   720
\end{tabular}}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   721
\end{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   722
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   723
\footnotesize
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   724
\lstinputlisting[firstline=22,lastline=26]{../progs/app6.scala}
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   725
\end{frame}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   726
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   727
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   728
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   729
\begin{frame}[c]
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   730
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   731
\footnotesize
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   732
\lstinputlisting[firstline=1,lastline=21]{../progs/app6.scala}
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   733
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   734
\end{frame}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   735
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   736
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   737
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   738
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   739
\begin{frame}[t]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   740
\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   741
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   742
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   743
\begin{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   744
\begin{axis}[
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   745
    xlabel={$n$},
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   746
    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
   747
    ylabel={time in secs},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   748
    enlargelimits=false,
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   749
    xtick={0,5000,...,10000},
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
   750
    xmax=11000,
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   751
    ymax=35,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   752
    ytick={0,5,...,30},
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   753
    scaled ticks=false,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   754
    axis lines=left,
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   755
    width=9cm,
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   756
    height=7cm,
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   757
    legend entries={Scala V2,Scala V3},  
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   758
    legend pos=north east
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   759
]
434
8664ff87cd77 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   760
\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
   761
\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
   762
\end{axis}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   763
\end{tikzpicture}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   764
\end{center}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   765
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   766
\end{frame}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   767
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   768
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   769
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   770
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   771
\begin{frame}[c]
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   772
  \frametitle{
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   773
    Another Example\\[-1mm]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   774
    in Java \liningnums{8} and Python}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   775
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   776
\begin{center}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   777
\begin{tikzpicture}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   778
  \begin{axis}[
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   779
    xlabel={$n$},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   780
    x label style={at={(1.05,0.0)}},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   781
    ylabel={time in secs},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   782
    enlargelimits=false,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   783
    xtick={0,5,...,30},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   784
    xmax=33,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   785
    ymax=35,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   786
    ytick={0,10,...,30},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   787
    scaled ticks=false,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   788
    axis lines=left,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   789
    width=9cm,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   790
    height=5cm, 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   791
    legend entries={Java 8, Python},  
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   792
    legend pos=north west,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   793
    legend cell align=left]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   794
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   795
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   796
\end{axis}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   797
\end{tikzpicture}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   798
\end{center}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   799
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   800
Regex: \bl{$(a^*)^* \cdot b$}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   801
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   802
Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   803
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   804
\end{frame}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   805
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   806
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   807
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   808
\begin{frame}[c]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   809
\frametitle{Same Example in Java \liningnums{9}+}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   810
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   811
\begin{center}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   812
\begin{tikzpicture}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   813
  \begin{axis}[
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   814
    xlabel={$n$},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   815
    x label style={at={(1.09,-0.15)}},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   816
    ylabel={time in secs},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   817
    scaled x ticks=false,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   818
    enlargelimits=false,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   819
    xtick distance=10000,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   820
    xmax=44000, 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   821
    ytick={0,10,...,30}, 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   822
    ymax=35, 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   823
    axis lines=left,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   824
    width=9cm,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   825
    height=5cm, 
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   826
    legend entries={Java \liningnums{9}+},
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   827
    legend pos=north west,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   828
    legend cell align=left]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   829
\addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data};
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   830
\end{axis}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   831
\end{tikzpicture}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   832
\end{center}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   833
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   834
Regex: \bl{$(a^*)^* \cdot b$}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   835
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   836
Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   837
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   838
\end{frame}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   839
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   840
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   841
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   842
\begin{frame}[c]
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   843
\frametitle{and with Brzozowski}
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   844
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   845
\begin{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   846
\begin{tikzpicture}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   847
  \begin{axis}[
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   848
    xlabel={$n$},
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   849
    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
   850
    ylabel={time in secs},
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   851
    scaled x ticks=false,
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   852
    xtick distance=2000000,
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   853
    enlargelimits=false,
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   854
    xmax=6400000, 
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   855
    ytick={0,10,...,30},
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   856
    ymax=35,
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   857
    axis lines=left,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   858
    width=9cm,
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   859
    height=5cm, 
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   860
    legend entries={Scala V3},
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   861
    legend pos=north west,
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   862
    legend cell align=left]
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   863
%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   864
\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
   865
\end{axis}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   866
\end{tikzpicture}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   867
\end{center}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   868
565
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   869
Regex: \bl{$(a^*)^* \cdot b$}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   870
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   871
Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
2be8c4c77418 updated
Christian Urban <urbanc@in.tum.de>
parents: 564
diff changeset
   872
435
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   873
\end{frame}
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   874
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
e08431a78f66 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 434
diff changeset
   875
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
   876
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   877
\begin{frame}[t]
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   878
\frametitle{What is good about this Alg.}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   879
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   880
\begin{itemize}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   881
\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
   882
\bl{$\sim r$}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   883
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   884
\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
   885
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   886
\item the algorithm is already quite old; there is still
514
bca9f8889a48 updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   887
  work to be done to use it as a tokenizer (that is relatively new work)
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   888
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   889
\item we can prove its correctness\ldots
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   890
\end{itemize}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   891
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   892
\end{frame}
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   893
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   894
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   895
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
566
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   896
\begin{frame}[c]
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   897
\frametitle{Negation of Regular Expr's}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   898
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   899
\begin{itemize}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   900
\item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   901
\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   902
\item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   903
\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   904
\end{itemize}\bigskip\pause
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   905
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   906
Used often for recognising comments:
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   907
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   908
\[
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   909
\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   910
\]
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   911
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   912
\end{frame}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   913
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   914
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   915
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   916
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   917
\begin{frame}[c]
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   918
\frametitle{Coursework}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   919
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   920
\underline{Strand 1:}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   921
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   922
\begin{itemize}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   923
\item Submission on Friday 12 October\\accepted until Monday 15 @ 18:00\medskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   924
\item source code needs to be submitted as well\medskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   925
\item you can re-use my Scala code from KEATS \\
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   926
  or use any programming language you like\medskip
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   927
\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   928
\end{itemize}  
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   929
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   930
\end{frame}
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   931
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   932
  
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   933
b153c04834eb updated
Christian Urban <urbanc@in.tum.de>
parents: 565
diff changeset
   934
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
342
c235e0aeb8df updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 338
diff changeset
   935
\begin{frame}[t]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   936
\frametitle{Proofs about Rexps}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   937
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   938
Remember their inductive definition:\\[5cm]
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   939
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   940
\begin{textblock}{6}(5,5)
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   941
  \begin{tabular}{@ {}rrl}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   942
  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   943
         & \bl{$\mid$} & \bl{$\ONE$}     \\
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   944
         & \bl{$\mid$} & \bl{$c$}            \\
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   945
         & \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
   946
         & \bl{$\mid$} & \bl{$r_1 + r_2$}    \\
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   947
         & \bl{$\mid$} & \bl{$r^*$}          \\
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   948
  \end{tabular}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   949
  \end{textblock}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   950
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
   951
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
   952
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   953
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   954
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   955
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   956
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   957
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   958
\frametitle{Proofs about Rexp (2)}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   959
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   960
\begin{itemize}
429
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   961
\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
   962
\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
   963
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
   964
\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
   965
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
   966
\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
   967
holds for \bl{$r$}.
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   968
\end{itemize}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   969
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   970
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   971
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   972
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   973
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   974
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   975
\frametitle{Proofs about Rexp (3)}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   976
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   977
Assume \bl{$P(r)$} is the property:
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   978
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   979
\begin{center}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   980
\bl{$nullable(r)$} if and only if \bl{$[] \in L(r)$}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   981
\end{center}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   982
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   983
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   984
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   985
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   986
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
   987
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
   988
\frametitle{Proofs about Rexp (4)}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   989
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   990
\begin{center}
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   991
\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
   992
$rev(\ZERO)$   & $\dn$ & $\ZERO$\\
7e71c947ec69 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 398
diff changeset
   993
$rev(\ONE)$      & $\dn$ & $\ONE$\\
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   994
$rev(c)$             & $\dn$ & $c$\\
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
   995
$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
   996
$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
   997
$rev(r^*)$           & $\dn$ & $rev(r)^*$\\
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   998
\end{tabular}}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
   999
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1000
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1001
We can prove
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1002
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1003
\begin{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1004
\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
  1005
\end{center}
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1006
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1007
by induction on \bl{$r$}.
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1008
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
  1009
\end{frame}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1010
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1011
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1012
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1013
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1014
\begin{frame}[c]
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1015
\frametitle{\begin{tabular}{c}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1016
  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
  1017
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1018
\begin{itemize}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1019
\item We started from
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1020
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1021
\begin{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1022
\begin{tabular}{rp{4cm}}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1023
  & \bl{$s \in L(r)$}\medskip\\
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
  1024
\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
  1025
\end{tabular}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1026
\end{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1027
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
  1028
\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
  1029
have
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1030
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1031
\begin{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1032
\begin{tabular}{rp{4cm}}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
  1033
\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
  1034
\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
  1035
\bl{$\dn$} & \bl{$matches\,s\,r$}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1036
\end{tabular}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1037
\end{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1038
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1039
\end{itemize}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1040
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1041
\end{frame}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1042
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1043
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1044
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1045
\begin{frame}[c]
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
  1046
\frametitle{Proofs about Rexp (5)}
263
92e6985018ae updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 261
diff changeset
  1047
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1048
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
  1049
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1050
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
  1051
\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
  1052
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1053
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1054
We can prove
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1055
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1056
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
  1057
\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
  1058
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1059
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1060
by induction on \bl{$r$}.
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1061
337
885ac2b6c27d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
  1062
\end{frame}
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1063
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1064
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1065
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1066
\begin{frame}[c]
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1067
\frametitle{Proofs about Strings}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1068
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1069
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
  1070
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1071
\begin{itemize}
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1072
\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
  1073
\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
  1074
already holds for \bl{$s$}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1075
\end{itemize}
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1076
\end{frame}
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1077
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1078
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1079
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1080
\begin{frame}[c]
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1081
\frametitle{Proofs about Strings (2)}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1082
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1083
We can then prove
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1084
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1085
\begin{center}
433
c08290ee4f1f updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 431
diff changeset
  1086
\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
  1087
\end{center}
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1088
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1089
119
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 118
diff changeset
  1090
We can finally prove
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1091
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1092
\begin{center}
345
0922b3e01289 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 342
diff changeset
  1093
\bl{$matches\,s\,r$}  if and only if  \bl{$s \in L(r)$} 
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1094
\end{center}
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1095
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1096
338
f16120cb4e19 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
  1097
\end{frame}
19
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
  1098
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
17
Christian Urban <urbanc@in.tum.de>
parents: 16
diff changeset
  1099
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1100
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1101
\begin{frame}[c]
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1102
\frametitle{Epilogue}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1103
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1104
\footnotesize
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1105
\begin{center}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1106
\begin{tabular}{cc}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1107
\begin{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1108
\begin{axis}[
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1109
    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
  1110
    xlabel={$n$},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1111
    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
  1112
    ylabel={time in secs},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1113
    enlargelimits=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1114
    xmax=7100000,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1115
    ytick={0,5,...,30},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1116
    ymax=33,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1117
    %scaled ticks=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1118
    axis lines=left,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1119
    width=5cm,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1120
    height=5cm, 
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1121
    legend entries={Scala V3, Scala V4},
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1122
    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
  1123
\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
  1124
\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
  1125
\end{axis}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1126
\end{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1127
&
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1128
\begin{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1129
\begin{axis}[
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1130
    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
  1131
    xlabel={$n$},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1132
    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
  1133
    ylabel={time in secs},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1134
    enlargelimits=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1135
    xmax=8100000,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1136
    ytick={0,5,...,30},
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1137
    ymax=33,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1138
    %scaled ticks=false,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1139
    axis lines=left,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1140
    width=5cm,
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1141
    height=5cm, 
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1142
    legend entries={Scala V3, Scala V4},
442
84d6714840c9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 436
diff changeset
  1143
    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
  1144
\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
  1145
\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
  1146
\end{axis}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1147
\end{tikzpicture}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1148
\end{tabular}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1149
\end{center}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1150
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1151
\only<2->{\footnotesize
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1152
\begin{textblock}{9}(0.5,8)
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1153
\begin{bubble}[11.8cm]
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1154
\lstinputlisting[numbers=none]{../progs/app52.scala}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1155
\end{bubble}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1156
\end{textblock}} 
510
cu
parents: 507
diff changeset
  1157
 
436
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1158
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1159
\end{frame}
9213b8298ca9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 435
diff changeset
  1160
7
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1161
\end{document}
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1162
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1163
%%% Local Variables:  
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1164
%%% mode: latex
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1165
%%% TeX-master: t
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1166
%%% End: 
73cf4406b773 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1167