slides08.tex
changeset 65 ade6af51402c
child 66 9215b9fb8852
equal deleted inserted replaced
64:2d625418c011 65:ade6af51402c
       
     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