\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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<presentation>{
\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: