58 \end{tikzpicture} |
58 \end{tikzpicture} |
59 \end{center} |
59 \end{center} |
60 |
60 |
61 \end{frame} |
61 \end{frame} |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
63 |
|
64 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
65 { |
|
66 \setbeamercolor{background canvas}{bg=cream} |
|
67 \begin{frame}[c] |
|
68 \frametitle{For Installation Problems} |
|
69 |
|
70 \begin{itemize} |
|
71 \item Harry Dilnot (harry.dilnot@kcl.ac.uk) \\ |
|
72 \;\;Windows expert |
|
73 \item Oliver Iliffe (oliver.iliffe@kcl.ac.uk) |
|
74 \end{itemize} |
|
75 |
|
76 \end{frame} |
|
77 } |
|
78 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
79 |
|
80 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
81 \begin{frame}[c] |
|
82 |
|
83 \begin{mybox3}{From Pollev last week}\it |
|
84 Is the equivalence of two regexes belong in the P or NP class of problems? |
|
85 \end{mybox3} |
|
86 |
|
87 \end{frame} |
|
88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
89 |
|
90 |
|
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
92 \begin{frame}[c] |
|
93 |
|
94 \begin{mybox3}{From Pollev last week}\it |
|
95 If state machines are not efficient, then how/why do many lexer |
|
96 packages like the logos crate in rust compile down a lexer |
|
97 definition down to a jump table driven state machine? |
|
98 \textcolor{gray}{Could we |
|
99 achieve quicker lexing with things like SIMD instructions?} |
|
100 \end{mybox3} |
|
101 \end{frame} |
|
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
103 |
|
104 |
|
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
106 \begin{frame}[c] |
|
107 \frametitle{\boldmath$(abcdef)^{\{n\}}$ in Rust and Scala} |
|
108 |
|
109 \begin{textblock}{14}(1,3) |
|
110 \begin{tikzpicture} |
|
111 \begin{axis}[ |
|
112 xlabel={copies of $[abcdef]$}, |
|
113 x label style={at={(0.45,-0.16)}}, |
|
114 ylabel={time in secs}, |
|
115 enlargelimits=false, |
|
116 ytick={0,10,...,60}, |
|
117 ymax=65, |
|
118 xmax=50000, |
|
119 xtick={0,10000,...,40000}, |
|
120 scaled ticks=false, |
|
121 axis lines=left, |
|
122 width=10cm, |
|
123 height=6cm, |
|
124 legend entries={Rust, Scala V3}, |
|
125 legend style={font=\small,at={(1.15,0.48)},anchor=north}, |
|
126 legend cell align=left] |
|
127 \addplot[blue,mark=*, mark options={fill=white}] table {re-rust2.data}; |
|
128 \only<2>{\addplot[red,mark=*, mark options={fill=white}] table {re-scala2.data};} |
|
129 \end{axis} |
|
130 \end{tikzpicture} |
|
131 \end{textblock} |
|
132 |
|
133 \end{frame} |
|
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
135 |
|
136 |
|
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
138 \begin{frame}[c] |
|
139 |
|
140 \begin{mybox3}{From Pollev last week}\it |
|
141 For a regular expression $r = r_1 \cdot r_2$, to prove that |
|
142 $der\;c\;r = (der\;c\;r) \cdot r^{\{n-1\}}$, is there a |
|
143 way to prove it in the general case instead |
|
144 of how you do the calculations for each $n$ in the videos? |
|
145 \end{mybox3} |
|
146 |
|
147 \end{frame} |
|
148 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
149 |
|
150 |
63 |
151 |
64 { |
152 { |
65 \setbeamercolor{background canvas}{bg=cream} |
153 \setbeamercolor{background canvas}{bg=cream} |
66 \begin{frame}<1-10>[c] |
154 \begin{frame}<1-10>[c] |
67 \end{frame} |
155 \end{frame} |
1793 \end{frame} |
1885 \end{frame} |
1794 } |
1886 } |
1795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1887 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1796 |
1888 |
1797 |
1889 |
|
1890 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1891 \begin{frame}[c] |
|
1892 \frametitle{\mbox{CW1: Regexes and \boldmath$L$-function}} |
|
1893 |
|
1894 Given |
|
1895 \begin{center} |
|
1896 \begin{tabular}{@ {}l@ {\hspace{20mm}}l@ {\hspace{2mm}}l@ {\hspace{2mm}}l} |
|
1897 \bl{$r^+$} & \bl{$L(r^+)$} & \bl{$\dn$} & \bl{$\bigcup_{1\le i}.\;L(r)^i$}\\ |
|
1898 \bl{$r^?$} & \bl{$L(r^?)$} & \bl{$\dn$} & \bl{$L(r) \cup \{[]\}$}\\ |
|
1899 \bl{$r_1 \,\&\, r_2$} & \bl{$L(r_1 \& r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cap L(r_2)$} \\ |
|
1900 \bl{$r^{\{n\}}$} & \bl{$L(r^{\{n\}})$} & \bl{$\dn$} & \bl{$L(r)^n$}\\ |
|
1901 \bl{$r^{\{..m\}}$} & \bl{$L(r^{\{..m\}})$} & \bl{$\dn$} & \bl{$\bigcup_{0\le i \le m}.\;L(r)^i$}\\ |
|
1902 \bl{$r^{\{n..\}}$} & \bl{$L(r^{\{n..\}})$} & \bl{$\dn$} & \bl{$\bigcup_{n\le i}.\;L(r)^i$}\\ |
|
1903 \bl{$r^{\{n..m\}}$} & \bl{$L(r^{\{n..m\}})$} & \bl{$\dn$} & \bl{$\bigcup_{n\le i \le m}.\;L(r)^i$}\\ |
|
1904 \bl{$\sim{}r$} & \bl{$L(\sim{}r)$} & \bl{$\dn$} & \bl{$\Sigma^* - L(r)$}\\ |
|
1905 \end{tabular} |
|
1906 \end{center} |
|
1907 |
|
1908 \end{frame} |
|
1909 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1910 |
|
1911 |
|
1912 |
|
1913 |
|
1914 |
|
1915 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1916 \begin{frame}[c] |
|
1917 \frametitle{Nullable} |
|
1918 |
|
1919 \begin{center} |
|
1920 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
1921 \bl{$nullable(r^+)$} & \bl{$\dn$} & \bl{$nullable(r)$}\\ |
|
1922 \bl{$nullable(r^?)$} & \bl{$\dn$} & \bl{\textit{true}}\\ |
|
1923 \bl{$nullable(r_1 \,\&\, r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$}\\ |
|
1924 \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$} \\ |
|
1925 \bl{$nullable(r^{\{..m\}})$} & \bl{$\dn$} & \bl{\textit{true}} \\ |
|
1926 \bl{$nullable (r^{\{n..\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$}\\ |
|
1927 \bl{$nullable (r^{\{n..m\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$}\\ |
|
1928 \bl{$nullable (\sim{}r)$} & \bl{$\dn$} & \bl{$!\,nullable(r)$}\\ |
|
1929 \end{tabular} |
|
1930 \end{center} |
|
1931 |
|
1932 \end{frame} |
|
1933 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1934 |
|
1935 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1936 \begin{frame}[c] |
|
1937 \frametitle{Derivative} |
|
1938 |
|
1939 \begin{center} |
|
1940 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
1941 \bl{$der\,c\,(r^+)$} & \bl{$\dn$} & \bl{$(der\,c\,r)\cdot r^*$}\\ |
|
1942 \bl{$der\,c\,(r^?)$} & \bl{$\dn$} & \bl{$der\,c\,r$}\\ |
|
1943 \bl{$der\,c\,(r_1 \,\&\, r_2)$} & \bl{$\dn$} & \bl{$(der\,c\,r_1) \;\&\; (der\,c\,r_2)$}\\ |
|
1944 \bl{$der\,c\,(r^{\{n\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} $\ZERO$ \textit{else} $(der\,c\,r)\cdot r^{\{n - 1\}}$} \\ |
|
1945 \bl{$der\,c\,(r^{\{..m\}})$} & \bl{$\dn$} & \bl{\textit{if} $m = 0$ \textit{then} $\ZERO$ \textit{else} $(der\,c\,r)\cdot r^{\{..m - 1\}}$}\\ |
|
1946 \bl{$der\,c\,(r^{\{n..\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} $(der\,c\,r)\cdot r^*$ \textit{else} $(der\,c\,r)\cdot r^{\{n - 1..\}}$}\\ |
|
1947 \bl{$der\,c\,(r^{\{n..m\}})$} & \bl{$\dn$} & \bl{\textit{if} $n = 0 \wedge m = 0$ \textit{then} $\ZERO$ \textit{else}}\\ |
|
1948 & & \bl{\textit{if} $ n = 0$ \textit{then} $(der\,c\,r)\cdot r^{\{..m-1\}}$ |
|
1949 \textit{else} $(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}\\ |
|
1950 \bl{$der\,c\,(\sim{}r)$} & \bl{$\dn$} & \bl{$\sim\,(der\,c\,r)$}\\ |
|
1951 \end{tabular} |
|
1952 \end{center} |
|
1953 |
|
1954 \end{frame} |
|
1955 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1956 |
|
1957 |
1798 |
1958 |
1799 \begin{frame}<1-15>[c] |
1959 \begin{frame}<1-15>[c] |
1800 |
1960 |
1801 \end{frame} |
1961 \end{frame} |
1802 |
1962 |
1803 \begin{frame}[t] |
1963 % \begin{frame}[t] |
1804 \begin{mybox3}{} |
1964 % \begin{mybox3}{} |
1805 I always thought dfa's needed a transition for each state for each |
1965 % I always thought dfa's needed a transition for each state for each |
1806 character, and if not it would be an nfa not a dfa. Is there an |
1966 % character, and if not it would be an nfa not a dfa. Is there an |
1807 example that disproves this? |
1967 % example that disproves this? |
1808 \end{mybox3} |
1968 % \end{mybox3} |
1809 \end{frame} |
1969 % \end{frame} |
1810 |
1970 |
1811 \begin{frame}<1-12>[c] |
1971 % \begin{frame}<1-12>[c] |
1812 \end{frame} |
1972 % \end{frame} |
1813 |
1973 |
1814 \begin{frame}[t] |
1974 % \begin{frame}[t] |
1815 \begin{mybox3}{} |
1975 % \begin{mybox3}{} |
1816 Do the regular expression matchers in Python and Java 8 have more |
1976 % Do the regular expression matchers in Python and Java 8 have more |
1817 features than the one implemented in this module? Or is there |
1977 % features than the one implemented in this module? Or is there |
1818 another reason for their inefficiency? |
1978 % another reason for their inefficiency? |
1819 \end{mybox3} |
1979 % \end{mybox3} |
1820 \end{frame} |
1980 % \end{frame} |
1821 |
1981 |
1822 |
1982 |
1823 \begin{frame}[c] |
1983 % \begin{frame}[c] |
1824 \begin{itemize} |
1984 % \begin{itemize} |
1825 \item CW / censored some msgs |
1985 % \item CW / censored some msgs |
1826 \item power law / proof |
1986 % \item power law / proof |
1827 \item CW feedback |
1987 % \item CW feedback |
1828 \item too polished CW submissions |
1988 % \item too polished CW submissions |
1829 \item no open book |
1989 % \item no open book |
1830 \end{itemize} |
1990 % \end{itemize} |
1831 \end{frame} |
1991 % \end{frame} |
1832 |
1992 |
1833 |
1993 |
1834 \end{document} |
1994 \end{document} |
1835 |
1995 |
1836 %%% Local Variables: |
1996 %%% Local Variables: |