diff -r ddd357703b6c -r d2c6852ca8da slides06.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides06.tex Mon Oct 29 12:31:31 2012 +0000 @@ -0,0 +1,676 @@ +\documentclass[dvipsnames,14pt,t]{beamer} +\usepackage{beamerthemeplainculight} +\usepackage[T1]{fontenc} +\usepackage[latin1]{inputenc} +\usepackage{mathpartir} +\usepackage[absolute,overlay]{textpos} +\usepackage{ifthen} +\usepackage{tikz} +\usepackage{pgf} +\usepackage{calc} +\usepackage{ulem} +\usepackage{courier} +\usepackage{listings} +\renewcommand{\uline}[1]{#1} +\usetikzlibrary{arrows} +\usetikzlibrary{automata} +\usetikzlibrary{shapes} +\usetikzlibrary{shadows} +\usetikzlibrary{positioning} +\usetikzlibrary{calc} +\usetikzlibrary{plotmarks} +\usepackage{graphicx} + +\definecolor{javared}{rgb}{0.6,0,0} % for strings +\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments +\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords +\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc + +\lstset{language=Java, + basicstyle=\ttfamily, + keywordstyle=\color{javapurple}\bfseries, + stringstyle=\color{javagreen}, + commentstyle=\color{javagreen}, + morecomment=[s][\color{javadocblue}]{/**}{*/}, + numbers=left, + numberstyle=\tiny\color{black}, + stepnumber=1, + numbersep=10pt, + tabsize=2, + showspaces=false, + showstringspaces=false} + +\lstdefinelanguage{scala}{ + morekeywords={abstract,case,catch,class,def,% + do,else,extends,false,final,finally,% + for,if,implicit,import,match,mixin,% + new,null,object,override,package,% + private,protected,requires,return,sealed,% + super,this,throw,trait,true,try,% + type,val,var,while,with,yield}, + otherkeywords={=>,<-,<\%,<:,>:,\#,@}, + sensitive=true, + morecomment=[l]{//}, + morecomment=[n]{/*}{*/}, + morestring=[b]", + morestring=[b]', + morestring=[b]""" +} + +\lstset{language=Scala, + basicstyle=\ttfamily, + keywordstyle=\color{javapurple}\bfseries, + stringstyle=\color{javagreen}, + commentstyle=\color{javagreen}, + morecomment=[s][\color{javadocblue}]{/**}{*/}, + numbers=left, + numberstyle=\tiny\color{black}, + stepnumber=1, + numbersep=10pt, + tabsize=2, + showspaces=false, + showstringspaces=false} + +% beamer stuff +\renewcommand{\slidecaption}{AFL 06, King's College London, 31.~October 2012} +\newcommand{\bl}[1]{\textcolor{blue}{#1}} +\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions + + +% The data files, written on the first run. +\begin{filecontents}{re-python.data} +1 0.029 +5 0.029 +10 0.029 +15 0.032 +16 0.042 +17 0.042 +18 0.055 +19 0.084 +20 0.136 +21 0.248 +22 0.464 +23 0.899 +24 1.773 +25 3.505 +26 6.993 +27 14.503 +28 29.307 +#29 58.886 +\end{filecontents} + +\begin{filecontents}{re1.data} +1 0.00179 +2 0.00011 +3 0.00014 +4 0.00026 +5 0.00050 +6 0.00095 +7 0.00190 +8 0.00287 +9 0.00779 +10 0.01399 +11 0.01894 +12 0.03666 +13 0.07994 +14 0.08944 +15 0.02377 +16 0.07392 +17 0.22798 +18 0.65310 +19 2.11360 +20 6.31606 +21 21.46013 +\end{filecontents} + +\begin{filecontents}{re2.data} +1 0.00240 +2 0.00013 +3 0.00020 +4 0.00030 +5 0.00049 +6 0.00083 +7 0.00146 +8 0.00228 +9 0.00351 +10 0.00640 +11 0.01217 +12 0.02565 +13 0.01382 +14 0.02423 +15 0.05065 +16 0.06522 +17 0.02140 +18 0.05176 +19 0.18254 +20 0.51898 +21 1.39631 +22 2.69501 +23 8.07952 +\end{filecontents} + +\begin{filecontents}{re-internal.data} +1 0.00069 +301 0.00700 +601 0.00297 +901 0.00470 +1201 0.01301 +1501 0.01175 +1801 0.01761 +2101 0.01787 +2401 0.02717 +2701 0.03932 +3001 0.03470 +3301 0.04349 +3601 0.05411 +3901 0.06181 +4201 0.07119 +4501 0.08578 +\end{filecontents} + +\begin{filecontents}{re3.data} +1 0.001605 +501 0.131066 +1001 0.057885 +1501 0.136875 +2001 0.176238 +2501 0.254363 +3001 0.37262 +3501 0.500946 +4001 0.638384 +4501 0.816605 +5001 1.00491 +5501 1.232505 +6001 1.525672 +6501 1.757502 +7001 2.092784 +7501 2.429224 +8001 2.803037 +8501 3.463045 +9001 3.609 +9501 4.081504 +10001 4.54569 +\end{filecontents} +\begin{document} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}<1>[t] +\frametitle{% + \begin{tabular}{@ {}c@ {}} + \\[-3mm] + \LARGE Automata and \\[-2mm] + \LARGE Formal Languages (6)\\[3mm] + \end{tabular}} + + \normalsize + \begin{center} + \begin{tabular}{ll} + Email: & christian.urban at kcl.ac.uk\\ + Of$\!$fice: & S1.27 (1st floor Strand Building)\\ + Slides: & KEATS (also home work is there)\\ + \end{tabular} + \end{center} + + +\end{frame}} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}ReDoS\end{tabular}} + +\begin{itemize} +\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice\bigskip +\item ``Regular Expressions Will Stab You in the Back''\bigskip +\item Evil regular expressions\medskip +\begin{itemize} +\item \bl{$(a?\{n\})a\{n\}$} +\item \bl{$(a^+)^+$} +\item \bl{$([a-zA-Z]^+)^*$} +\item \bl{$(a + aa)^+$} +\item \bl{$(a + a?)^+$} +\end{itemize} +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Regexp Matching\end{tabular}} + +Given a regular expression + +\begin{enumerate} +\item you might convert it into a DFA (subset construction) +\item you might try all possible paths in an NFA via backtracking +\item you might try all paths in an NFA in parallel +\item you might try to convert the DFA ``lazily'' +\end{enumerate}\bigskip + +Often No~2 is implemented (sometimes there are even good reasons for doing this). + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$} in Python\end{tabular}} + +\begin{tikzpicture}[y=.2cm, x=.3cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (30,0); + \draw (0,0) -- coordinate (y axis mid) (0,30); + %ticks + \foreach \x in {0,5,...,30} + \draw (\x,1pt) -- (\x,-3pt) + node[anchor=north] {\x}; + \foreach \y in {0,5,...,30} + \draw (1pt,\y) -- (-3pt,\y) + node[anchor=east] {\y}; + %labels + \node[below=0.6cm] at (x axis mid) {\bl{a}s}; + \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; + + %plots + \draw[color=blue] plot[mark=*, mark options={fill=white}] + file {re-python.data}; + \only<2->{ + \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] + file {re1.data};} + \only<3->{ + \draw[color=green] plot[mark=square*, mark options={fill=white} ] + file {re2.data};} + + %legend + \begin{scope}[shift={(4,20)}] + \draw[color=blue] (0,0) -- + plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Python}; + \only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- + plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Scala V1};} + \only<3->{ + \draw[yshift=2\baselineskip, color=green] (0,0) -- + plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Scala V2 with simplifications};} + \end{scope} +\end{tikzpicture} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + + +\begin{tikzpicture}[y=.7cm, x=.0009cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (10000,0); + \draw (0,0) -- coordinate (y axis mid) (0,6); + %ticks + \foreach \x in {0,2000,...,10000} + \draw (\x,1pt) -- (\x,-3pt) + node[anchor=north] {\x}; + \foreach \y in {0,1,...,6} + \draw (1pt,\y) -- (-3pt,\y) + node[anchor=east] {\y}; + %labels + \node[below=0.6cm] at (x axis mid) {\bl{a}s}; + \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; + + %plots + \draw[color=blue] plot[mark=*, mark options={fill=white}] + file {re-internal.data}; + \only<2->{ + \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] + file {re3.data};} + + %legend + \begin{scope}[shift={(2000,4)}] + \draw[color=blue] (0,0) -- + plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Scala Internal}; + \only<2->{ + \draw[yshift=\baselineskip, color=red] (0,0) -- + plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small Scala V3 with explicit $\_\{\_\}$};} + \end{scope} +\end{tikzpicture} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Last Week\end{tabular}} + +Last week I showed you\bigskip + +\begin{itemize} +\item an algorithm for automata minimisation + +\item an algorithm for transforming a regular expression into an NFA + +\item an algorithm for transforming an NFA into a DFA (subset construction) + +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}This Week\end{tabular}} + +Go over the algorithms again, but with two new things and \ldots\medskip + +\begin{itemize} +\item with the example: what is the regular expression that accepts every string, except those ending +in \bl{aa}?\medskip + +\item Go over the proof for \bl{$L(rev(r)) = Rev(L(r))$}.\medskip + +\item Anything else so far. +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Proofs By Induction\end{tabular}} + +\begin{itemize} +\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip +\item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already +holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip +\item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already +holds for \bl{r$_1$} and \bl{r$_2$}. +\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already +holds for \bl{r}. +\end{itemize} + +\begin{center} +\bl{$P(r):\;\;L(rev(r)) = Rev(L(r))$} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[t] + +What is the regular expression that accepts every string, except those ending +in \bl{aa}?\pause\bigskip + +\begin{center} +\begin{tabular}{l} +\bl{(a + b)$^*$ba}\\ +\bl{(a + b)$^*$ab}\\ +\bl{(a + b)$^*$bb}\\\pause +\bl{a}\\ +\bl{\texttt{""}} +\end{tabular} +\end{center}\pause + +What are the strings to be avoided?\pause\medskip + +\begin{center} +\bl{(a + b)$^*$aa} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[t] + +An NFA for \bl{(a + b)$^*$aa} + +\begin{center} +\begin{tikzpicture}[scale=2, line width=0.5mm] + \node[state, initial] (q0) at ( 0,1) {$q_0$}; + \node[state] (q1) at ( 1,1) {$q_1$}; + \node[state, accepting] (q2) at ( 2,1) {$q_2$}; + \path[->] (q0) edge node[above] {$a$} (q1) + (q1) edge node[above] {$a$} (q2) + (q0) edge [loop below] node {$a$} () + (q0) edge [loop above] node {$b$} () + ; +\end{tikzpicture} +\end{center}\pause + +Minimisation for DFAs\\ +Subset Construction for NFAs + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}DFA Minimisation\end{tabular}} + + +\begin{enumerate} +\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} +\item Mark all pairs that accepting and non-accepting states +\item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether +\begin{center} +\bl{($\delta$(q,c), $\delta$(p,c))} +\end{center} +are marked. If yes, then also mark \bl{(q, p)}. +\item Repeat last step until nothing changed. +\item All unmarked pairs can be merged. +\end{enumerate} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +Minimal DFA \only<1>{\bl{(a + b)$^*$aa}}\only<2->{\alert{not} \bl{(a + b)$^*$aa}} + +\begin{center} +\begin{tikzpicture}[scale=2, line width=0.5mm] + \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} + \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} + \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} + \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} + \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} + \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} + \path[->] (q0) edge[bend left] node[above] {$a$} (q1) + (q1) edge[bend left] node[above] {$b$} (q0) + (q2) edge[bend left=50] node[below] {$b$} (q0) + (q1) edge node[above] {$a$} (q2) + (q2) edge [loop right] node {$a$} () + (q0) edge [loop below] node {$b$} () + ; +\end{tikzpicture} +\end{center} + +\onslide<3>{How to get from a DFA to a regular expression?} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +\begin{center} +\begin{tikzpicture}[scale=2, line width=0.5mm] + \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} + \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} + \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} + \path[->] (q0) edge[bend left] node[above] {$a$} (q1) + (q1) edge[bend left] node[above] {$b$} (q0) + (q2) edge[bend left=50] node[below] {$b$} (q0) + (q1) edge node[above] {$a$} (q2) + (q2) edge [loop right] node {$a$} () + (q0) edge [loop below] node {$b$} () + ; +\end{tikzpicture} +\end{center}\pause\bigskip + +\onslide<2->{ +\begin{center} +\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} +\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ +\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ +\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ + +\end{tabular} +\end{center} +} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +\begin{center} +\begin{tikzpicture}[scale=2, line width=0.5mm] + \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} + \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} + \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} + \path[->] (q0) edge[bend left] node[above] {$a$} (q1) + (q1) edge[bend left] node[above] {$b$} (q0) + (q2) edge[bend left=50] node[below] {$b$} (q0) + (q1) edge node[above] {$a$} (q2) + (q2) edge [loop right] node {$a$} () + (q0) edge [loop below] node {$b$} () + ; +\end{tikzpicture} +\end{center}\bigskip + +\onslide<2->{ +\begin{center} +\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} +\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ +\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ +\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ + +\end{tabular} +\end{center} +} + +\onslide<3->{ +Arden's Lemma: +\begin{center} +If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} +\end{center} +} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Algorithms on Automata\end{tabular}} + + +\begin{itemize} +\item Reg $\rightarrow$ NFA: Thompson-McNaughton-Yamada method\medskip +\item NFA $\rightarrow$ DFA: Subset Construction\medskip +\item DFA $\rightarrow$ Reg: Brzozowski's Algebraic Method\medskip +\item DFA minimisation: Hopcrofts Algorithm\medskip +\item complement DFA +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\newcommand{\qq}{\mbox{\texttt{"}}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Grammars\end{tabular}} + +\begin{center} +\bl{\begin{tabular}{lcl} +$E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ +$F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ +$T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ +\end{tabular}} +\end{center} + +\bl{$E$}, \bl{$F$} and \bl{$T$} are non-terminals\\ +\bl{$E$} is start symbol\\ +\bl{$num$}, \bl{(}, \bl{)}, \bl{+} \ldots are terminals\bigskip\\ + + +\bl{\texttt{(2*3)+(3+4)}} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +\begin{center} +\bl{\begin{tabular}{lcl} +$E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ +$F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ +$T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ +\end{tabular}} +\end{center} + +\begin{center} +\begin{tikzpicture}[level distance=8mm, blue] + \node {E} + child {node {F} + child {node {T} + child {node {\qq(\qq\,E\,\qq)\qq} + child {node{F \qq*\qq{} F} + child {node {T} child {node {2}}} + child {node {T} child {node {3}}} + } + } + } + child {node {\qq+\qq}} + child {node {T} + child {node {\qq(\qq\,E\,\qq)\qq} + child {node {F} + child {node {T \qq+\qq{} T} + child {node {3}} + child {node {4}} + } + }} + }}; +\end{tikzpicture} +\end{center} + +\begin{textblock}{5}(1, 5) +\bl{\texttt{(2*3)+(3+4)}} +\end{textblock} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: +