|
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{beamerthemeplainculight} |
|
3 \usepackage[T1]{fontenc} |
|
4 \usepackage[latin1]{inputenc} |
|
5 \usepackage{mathpartir} |
|
6 \usepackage[absolute,overlay]{textpos} |
|
7 \usepackage{ifthen} |
|
8 \usepackage{tikz} |
|
9 \usepackage{pgf} |
|
10 \usepackage{calc} |
|
11 \usepackage{ulem} |
|
12 \usepackage{courier} |
|
13 \usepackage{listings} |
|
14 \renewcommand{\uline}[1]{#1} |
|
15 \usetikzlibrary{arrows} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{shapes} |
|
18 \usetikzlibrary{shadows} |
|
19 \usetikzlibrary{positioning} |
|
20 \usetikzlibrary{calc} |
|
21 \usetikzlibrary{plotmarks} |
|
22 \usepackage{graphicx} |
|
23 |
|
24 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
25 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
26 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
27 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
28 |
|
29 \lstset{language=Java, |
|
30 basicstyle=\ttfamily, |
|
31 keywordstyle=\color{javapurple}\bfseries, |
|
32 stringstyle=\color{javagreen}, |
|
33 commentstyle=\color{javagreen}, |
|
34 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
35 numbers=left, |
|
36 numberstyle=\tiny\color{black}, |
|
37 stepnumber=1, |
|
38 numbersep=10pt, |
|
39 tabsize=2, |
|
40 showspaces=false, |
|
41 showstringspaces=false} |
|
42 |
|
43 \lstdefinelanguage{scala}{ |
|
44 morekeywords={abstract,case,catch,class,def,% |
|
45 do,else,extends,false,final,finally,% |
|
46 for,if,implicit,import,match,mixin,% |
|
47 new,null,object,override,package,% |
|
48 private,protected,requires,return,sealed,% |
|
49 super,this,throw,trait,true,try,% |
|
50 type,val,var,while,with,yield}, |
|
51 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
52 sensitive=true, |
|
53 morecomment=[l]{//}, |
|
54 morecomment=[n]{/*}{*/}, |
|
55 morestring=[b]", |
|
56 morestring=[b]', |
|
57 morestring=[b]""" |
|
58 } |
|
59 |
|
60 \lstset{language=Scala, |
|
61 basicstyle=\ttfamily, |
|
62 keywordstyle=\color{javapurple}\bfseries, |
|
63 stringstyle=\color{javagreen}, |
|
64 commentstyle=\color{javagreen}, |
|
65 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
66 numbers=left, |
|
67 numberstyle=\tiny\color{black}, |
|
68 stepnumber=1, |
|
69 numbersep=10pt, |
|
70 tabsize=2, |
|
71 showspaces=false, |
|
72 showstringspaces=false} |
|
73 |
|
74 % beamer stuff |
|
75 \renewcommand{\slidecaption}{AFL 08, King's College London, 21.~November 2012} |
|
76 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
77 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
78 |
|
79 |
|
80 % The data files, written on the first run. |
|
81 \begin{filecontents}{s-grammar1.data} |
|
82 1 0.01152 |
|
83 51 0.07973 |
|
84 101 0.09726 |
|
85 151 0.09320 |
|
86 201 0.10010 |
|
87 251 0.16997 |
|
88 301 0.26662 |
|
89 351 0.46118 |
|
90 401 0.62516 |
|
91 451 0.87247 |
|
92 501 1.16334 |
|
93 551 1.71152 |
|
94 601 2.10958 |
|
95 651 2.44360 |
|
96 701 2.98488 |
|
97 751 3.50326 |
|
98 801 4.11036 |
|
99 851 4.93394 |
|
100 901 5.77465 |
|
101 951 7.39123 |
|
102 \end{filecontents} |
|
103 |
|
104 \begin{filecontents}{s-grammar2.data} |
|
105 1 0.01280 |
|
106 2 0.00064 |
|
107 3 0.00173 |
|
108 4 0.00355 |
|
109 5 0.00965 |
|
110 6 0.02674 |
|
111 7 0.06953 |
|
112 8 0.11166 |
|
113 9 0.18707 |
|
114 10 0.09189 |
|
115 11 0.12724 |
|
116 12 0.24337 |
|
117 13 0.59304 |
|
118 14 1.53594 |
|
119 15 4.01195 |
|
120 16 10.73582 |
|
121 17 29.51587 |
|
122 #18 73.14163 |
|
123 \end{filecontents} |
|
124 |
|
125 |
|
126 \begin{document} |
|
127 |
|
128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
129 \mode<presentation>{ |
|
130 \begin{frame}<1>[t] |
|
131 \frametitle{% |
|
132 \begin{tabular}{@ {}c@ {}} |
|
133 \\[-3mm] |
|
134 \LARGE Automata and \\[-2mm] |
|
135 \LARGE Formal Languages (8)\\[3mm] |
|
136 \end{tabular}} |
|
137 |
|
138 \normalsize |
|
139 \begin{center} |
|
140 \begin{tabular}{ll} |
|
141 Email: & christian.urban at kcl.ac.uk\\ |
|
142 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
143 Slides: & KEATS (also home work is there)\\ |
|
144 \end{tabular} |
|
145 \end{center} |
|
146 |
|
147 |
|
148 \end{frame}} |
|
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
150 |
|
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
152 \mode<presentation>{ |
|
153 \begin{frame}[c] |
|
154 \frametitle{\begin{tabular}{c}Two Grammars\end{tabular}} |
|
155 |
|
156 Which languages are recognised by the following two grammars? |
|
157 |
|
158 \begin{center} |
|
159 \bl{\begin{tabular}{lcl} |
|
160 $S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\ |
|
161 & $|$ & $\epsilon$ |
|
162 \end{tabular}} |
|
163 \end{center}\bigskip |
|
164 |
|
165 \begin{center} |
|
166 \bl{\begin{tabular}{lcl} |
|
167 $U$ & $\rightarrow$ & $1 \cdot U$\\ |
|
168 & $|$ & $\epsilon$ |
|
169 \end{tabular}} |
|
170 \end{center} |
|
171 |
|
172 \end{frame}} |
|
173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
174 |
|
175 |
|
176 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
177 \mode<presentation>{ |
|
178 \begin{frame}[t] |
|
179 \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} |
|
180 |
|
181 \mbox{}\\[-25mm]\mbox{} |
|
182 |
|
183 \begin{center} |
|
184 \begin{tikzpicture}[y=.2cm, x=.009cm] |
|
185 %axis |
|
186 \draw (0,0) -- coordinate (x axis mid) (1000,0); |
|
187 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
188 %ticks |
|
189 \foreach \x in {0, 20, 100, 200,...,1000} |
|
190 \draw (\x,1pt) -- (\x,-3pt) |
|
191 node[anchor=north] {\small \x}; |
|
192 \foreach \y in {0,5,...,30} |
|
193 \draw (1pt,\y) -- (-3pt,\y) |
|
194 node[anchor=east] {\small\y}; |
|
195 %labels |
|
196 \node[below=0.6cm] at (x axis mid) {\bl{1}s}; |
|
197 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
198 |
|
199 %plots |
|
200 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
201 file {s-grammar1.data}; |
|
202 \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
203 file {s-grammar2.data};} |
|
204 %legend |
|
205 \begin{scope}[shift={(400,20)}] |
|
206 \draw[color=blue] (0,0) -- |
|
207 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
208 node[right]{\small unambiguous}; |
|
209 \only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- |
|
210 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
211 node[right]{\small ambiguous};} |
|
212 \end{scope} |
|
213 \end{tikzpicture} |
|
214 \end{center} |
|
215 |
|
216 \end{frame}} |
|
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
218 |
|
219 |
|
220 |
|
221 \end{document} |
|
222 |
|
223 %%% Local Variables: |
|
224 %%% mode: latex |
|
225 %%% TeX-master: t |
|
226 %%% End: |
|
227 |