|
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 \usepackage{graphicx} |
|
22 |
|
23 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
24 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
25 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
26 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
27 |
|
28 \lstset{language=Java, |
|
29 basicstyle=\ttfamily, |
|
30 keywordstyle=\color{javapurple}\bfseries, |
|
31 stringstyle=\color{javagreen}, |
|
32 commentstyle=\color{javagreen}, |
|
33 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
34 numbers=left, |
|
35 numberstyle=\tiny\color{black}, |
|
36 stepnumber=1, |
|
37 numbersep=10pt, |
|
38 tabsize=2, |
|
39 showspaces=false, |
|
40 showstringspaces=false} |
|
41 |
|
42 \lstdefinelanguage{scala}{ |
|
43 morekeywords={abstract,case,catch,class,def,% |
|
44 do,else,extends,false,final,finally,% |
|
45 for,if,implicit,import,match,mixin,% |
|
46 new,null,object,override,package,% |
|
47 private,protected,requires,return,sealed,% |
|
48 super,this,throw,trait,true,try,% |
|
49 type,val,var,while,with,yield}, |
|
50 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
51 sensitive=true, |
|
52 morecomment=[l]{//}, |
|
53 morecomment=[n]{/*}{*/}, |
|
54 morestring=[b]", |
|
55 morestring=[b]', |
|
56 morestring=[b]""" |
|
57 } |
|
58 |
|
59 \lstset{language=Scala, |
|
60 basicstyle=\ttfamily, |
|
61 keywordstyle=\color{javapurple}\bfseries, |
|
62 stringstyle=\color{javagreen}, |
|
63 commentstyle=\color{javagreen}, |
|
64 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
65 numbers=left, |
|
66 numberstyle=\tiny\color{black}, |
|
67 stepnumber=1, |
|
68 numbersep=10pt, |
|
69 tabsize=2, |
|
70 showspaces=false, |
|
71 showstringspaces=false} |
|
72 |
|
73 % beamer stuff |
|
74 \renewcommand{\slidecaption}{AFL 05, King's College London, 24.~October 2012} |
|
75 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
76 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
77 |
|
78 \begin{document} |
|
79 |
|
80 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
81 \mode<presentation>{ |
|
82 \begin{frame}<1>[t] |
|
83 \frametitle{% |
|
84 \begin{tabular}{@ {}c@ {}} |
|
85 \\[-3mm] |
|
86 \LARGE Automata and \\[-2mm] |
|
87 \LARGE Formal Languages (5)\\[3mm] |
|
88 \end{tabular}} |
|
89 |
|
90 \normalsize |
|
91 \begin{center} |
|
92 \begin{tabular}{ll} |
|
93 Email: & christian.urban at kcl.ac.uk\\ |
|
94 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
95 Slides: & KEATS (also home work is there)\\ |
|
96 \end{tabular} |
|
97 \end{center} |
|
98 |
|
99 |
|
100 \end{frame}} |
|
101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
102 |
|
103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
104 \mode<presentation>{ |
|
105 \begin{frame}[t] |
|
106 \frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}} |
|
107 |
|
108 A DFA \bl{$A(Q, q_0, F, \delta)$} consists of: |
|
109 |
|
110 \begin{itemize} |
|
111 \item a finite set of states \bl{$Q$} |
|
112 \item one of these states is the start state \bl{$q_0$} |
|
113 \item some states are accepting states \bl{$F$} |
|
114 \item a transition function \bl{$\delta$} |
|
115 \end{itemize}\pause |
|
116 |
|
117 \onslide<2->{ |
|
118 \begin{center} |
|
119 \begin{tabular}{l} |
|
120 \bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ |
|
121 \bl{$\hat{\delta}(q, c\!::\!s) = \hat{\delta}(\delta(q, c), s)$} |
|
122 \end{tabular} |
|
123 \end{center}} |
|
124 |
|
125 \only<3,4>{ |
|
126 \begin{center} |
|
127 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
128 \node[state, initial] (q02) at ( 0,1) {$q_{0}$}; |
|
129 \node[state] (q13) at ( 1,1) {$q_{1}$}; |
|
130 \node[state, accepting] (q4) at ( 2,1) {$q_2$}; |
|
131 \path[->] (q02) edge[bend left] node[above] {$a$} (q13) |
|
132 (q13) edge[bend left] node[below] {$b$} (q02) |
|
133 (q13) edge node[above] {$a$} (q4) |
|
134 (q02) edge [loop below] node {$b$} () |
|
135 (q4) edge [loop right] node {$a, b$} () |
|
136 ; |
|
137 \end{tikzpicture} |
|
138 \end{center}}% |
|
139 % |
|
140 \only<5>{ |
|
141 \begin{center} |
|
142 \bl{$L(A) \dn \{ s \;|\; \hat{\delta}(q_0, s) \in F\}$} |
|
143 \end{center}} |
|
144 |
|
145 \end{frame}} |
|
146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
147 |
|
148 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
149 \mode<presentation>{ |
|
150 \begin{frame}[t] |
|
151 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
|
152 |
|
153 An NFA \bl{$A(Q, q_0, F, \delta)$} consists again of: |
|
154 |
|
155 \begin{itemize} |
|
156 \item a finite set of states |
|
157 \item one of these states is the start state |
|
158 \item some states are accepting states |
|
159 \item a transition \alert{relation}\medskip |
|
160 \end{itemize} |
|
161 |
|
162 |
|
163 \begin{center} |
|
164 \begin{tabular}{c} |
|
165 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\ |
|
166 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\ |
|
167 \end{tabular} |
|
168 \hspace{10mm} |
|
169 \begin{tabular}{c} |
|
170 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\ |
|
171 \end{tabular} |
|
172 \end{center}\pause\medskip |
|
173 |
|
174 A string \bl{s} is accepted by an NFA, if there is a ``lucky'' sequence to an accepting state. |
|
175 |
|
176 \end{frame}} |
|
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
178 |
|
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
180 \mode<presentation>{ |
|
181 \begin{frame}[c] |
|
182 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
183 |
|
184 Last week I showed you\bigskip |
|
185 |
|
186 \begin{itemize} |
|
187 \item an algorithm for automata minimisation |
|
188 |
|
189 \item an algorithm for transforming a regular expression into an NFA |
|
190 |
|
191 \item an algorithm for transforming an NFA into a DFA (subset construction) |
|
192 |
|
193 \end{itemize} |
|
194 |
|
195 \end{frame}} |
|
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
197 |
|
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
199 \mode<presentation>{ |
|
200 \begin{frame}[c] |
|
201 \frametitle{\begin{tabular}{c}This Week\end{tabular}} |
|
202 |
|
203 Go over the algorithms again, but with two new things and \ldots\medskip |
|
204 |
|
205 \begin{itemize} |
|
206 \item with the example: what is the regular expression that accepts every string, except those ending |
|
207 in \bl{aa}?\medskip |
|
208 |
|
209 \item Go over the proof for \bl{$L(rev(r)) = Rev(L(r))$}.\medskip |
|
210 |
|
211 \item Anything else so far. |
|
212 \end{itemize} |
|
213 |
|
214 \end{frame}} |
|
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
216 |
|
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
218 \mode<presentation>{ |
|
219 \begin{frame}[c] |
|
220 \frametitle{\begin{tabular}{c}Proofs By Induction\end{tabular}} |
|
221 |
|
222 \begin{itemize} |
|
223 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
|
224 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already |
|
225 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip |
|
226 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already |
|
227 holds for \bl{r$_1$} and \bl{r$_2$}. |
|
228 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
|
229 holds for \bl{r}. |
|
230 \end{itemize} |
|
231 |
|
232 \begin{center} |
|
233 \bl{$P(r):\;\;L(rev(r)) = Rev(L(r))$} |
|
234 \end{center} |
|
235 |
|
236 \end{frame}} |
|
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
238 |
|
239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
240 \mode<presentation>{ |
|
241 \begin{frame}[t] |
|
242 |
|
243 What is the regular expression that accepts every string, except those ending |
|
244 in \bl{aa}?\pause\bigskip |
|
245 |
|
246 \begin{center} |
|
247 \begin{tabular}{l} |
|
248 \bl{(a + b)$^*$ba}\\ |
|
249 \bl{(a + b)$^*$ab}\\ |
|
250 \bl{(a + b)$^*$bb}\\\pause |
|
251 \bl{a}\\ |
|
252 \bl{\texttt{""}} |
|
253 \end{tabular} |
|
254 \end{center}\pause |
|
255 |
|
256 What are the strings to be avoided?\pause\medskip |
|
257 |
|
258 \begin{center} |
|
259 \bl{(a + b)$^*$aa} |
|
260 \end{center} |
|
261 |
|
262 \end{frame}} |
|
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
264 |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 \mode<presentation>{ |
|
267 \begin{frame}[t] |
|
268 |
|
269 An NFA for \bl{(a + b)$^*$aa} |
|
270 |
|
271 \begin{center} |
|
272 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
273 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
274 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
275 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
276 \path[->] (q0) edge node[above] {$a$} (q1) |
|
277 (q1) edge node[above] {$a$} (q2) |
|
278 (q0) edge [loop below] node {$a$} () |
|
279 (q0) edge [loop above] node {$b$} () |
|
280 ; |
|
281 \end{tikzpicture} |
|
282 \end{center}\pause |
|
283 |
|
284 Minimisation for DFAs\\ |
|
285 Subset Construction for NFAs |
|
286 |
|
287 \end{frame}} |
|
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
289 |
|
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
291 \mode<presentation>{ |
|
292 \begin{frame}[c] |
|
293 \frametitle{\begin{tabular}{c}DFA Minimisation\end{tabular}} |
|
294 |
|
295 |
|
296 \begin{enumerate} |
|
297 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
298 \item Mark all pairs that accepting and non-accepting states |
|
299 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
300 \begin{center} |
|
301 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
302 \end{center} |
|
303 are marked. If yes, then also mark \bl{(q, p)}. |
|
304 \item Repeat last step until nothing changed. |
|
305 \item All unmarked pairs can be merged. |
|
306 \end{enumerate} |
|
307 |
|
308 \end{frame}} |
|
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
310 |
|
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
312 \mode<presentation>{ |
|
313 \begin{frame}[c] |
|
314 |
|
315 Minimal DFA \only<1>{\bl{(a + b)$^*$aa}}\only<2->{\alert{not} \bl{(a + b)$^*$aa}} |
|
316 |
|
317 \begin{center} |
|
318 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
319 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
320 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
321 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
322 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
323 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
324 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
325 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
326 (q1) edge[bend left] node[above] {$b$} (q0) |
|
327 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
328 (q1) edge node[above] {$a$} (q2) |
|
329 (q2) edge [loop right] node {$a$} () |
|
330 (q0) edge [loop below] node {$b$} () |
|
331 ; |
|
332 \end{tikzpicture} |
|
333 \end{center} |
|
334 |
|
335 \onslide<3>{How to get from a DFA to a regular expression?} |
|
336 |
|
337 \end{frame}} |
|
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
339 |
|
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
341 \mode<presentation>{ |
|
342 \begin{frame}[c] |
|
343 |
|
344 \begin{center} |
|
345 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
346 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
347 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
348 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
349 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
350 (q1) edge[bend left] node[above] {$b$} (q0) |
|
351 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
352 (q1) edge node[above] {$a$} (q2) |
|
353 (q2) edge [loop right] node {$a$} () |
|
354 (q0) edge [loop below] node {$b$} () |
|
355 ; |
|
356 \end{tikzpicture} |
|
357 \end{center}\pause\bigskip |
|
358 |
|
359 \onslide<2->{ |
|
360 \begin{center} |
|
361 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
362 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
|
363 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
|
364 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
|
365 |
|
366 \end{tabular} |
|
367 \end{center} |
|
368 } |
|
369 |
|
370 \end{frame}} |
|
371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
372 |
|
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
374 \mode<presentation>{ |
|
375 \begin{frame}[c] |
|
376 |
|
377 \begin{center} |
|
378 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
379 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
380 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
381 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
382 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
383 (q1) edge[bend left] node[above] {$b$} (q0) |
|
384 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
385 (q1) edge node[above] {$a$} (q2) |
|
386 (q2) edge [loop right] node {$a$} () |
|
387 (q0) edge [loop below] node {$b$} () |
|
388 ; |
|
389 \end{tikzpicture} |
|
390 \end{center}\bigskip |
|
391 |
|
392 \onslide<2->{ |
|
393 \begin{center} |
|
394 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
395 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
396 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
397 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
398 |
|
399 \end{tabular} |
|
400 \end{center} |
|
401 } |
|
402 |
|
403 \onslide<3->{ |
|
404 Arden's Lemma: |
|
405 \begin{center} |
|
406 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
407 \end{center} |
|
408 } |
|
409 |
|
410 \end{frame}} |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 |
|
413 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
414 \mode<presentation>{ |
|
415 \begin{frame}[c] |
|
416 \frametitle{\begin{tabular}{c}Algorithms on Automata\end{tabular}} |
|
417 |
|
418 |
|
419 \begin{itemize} |
|
420 \item Reg $\rightarrow$ NFA: Thompson-McNaughton-Yamada method\medskip |
|
421 \item NFA $\rightarrow$ DFA: Subset Construction\medskip |
|
422 \item DFA $\rightarrow$ Reg: Brzozowski's Algebraic Method\medskip |
|
423 \item DFA minimisation: Hopcrofts Algorithm\medskip |
|
424 \item complement DFA |
|
425 \end{itemize} |
|
426 |
|
427 \end{frame}} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 \newcommand{\qq}{\mbox{\texttt{"}}} |
|
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
431 \mode<presentation>{ |
|
432 \begin{frame}[c] |
|
433 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
|
434 |
|
435 \begin{center} |
|
436 \bl{\begin{tabular}{lcl} |
|
437 $E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ |
|
438 $F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ |
|
439 $T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ |
|
440 \end{tabular}} |
|
441 \end{center} |
|
442 |
|
443 \bl{$E$}, \bl{$F$} and \bl{$T$} are non-terminals\\ |
|
444 \bl{$E$} is start symbol\\ |
|
445 \bl{$num$}, \bl{(}, \bl{)}, \bl{+} \ldots are terminals\bigskip\\ |
|
446 |
|
447 |
|
448 \bl{\texttt{(2*3)+(3+4)}} |
|
449 |
|
450 \end{frame}} |
|
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
452 |
|
453 |
|
454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
455 \mode<presentation>{ |
|
456 \begin{frame}[c] |
|
457 |
|
458 \begin{center} |
|
459 \bl{\begin{tabular}{lcl} |
|
460 $E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ |
|
461 $F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ |
|
462 $T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ |
|
463 \end{tabular}} |
|
464 \end{center} |
|
465 |
|
466 \begin{center} |
|
467 \begin{tikzpicture}[level distance=8mm, blue] |
|
468 \node {E} |
|
469 child {node {F} |
|
470 child {node {T} |
|
471 child {node {\qq(\qq\,E\,\qq)\qq} |
|
472 child {node{F \qq*\qq{} F} |
|
473 child {node {T} child {node {2}}} |
|
474 child {node {T} child {node {3}}} |
|
475 } |
|
476 } |
|
477 } |
|
478 child {node {\qq+\qq}} |
|
479 child {node {T} |
|
480 child {node {\qq(\qq\,E\,\qq)\qq} |
|
481 child {node {F} |
|
482 child {node {T \qq+\qq{} T} |
|
483 child {node {3}} |
|
484 child {node {4}} |
|
485 } |
|
486 }} |
|
487 }}; |
|
488 \end{tikzpicture} |
|
489 \end{center} |
|
490 |
|
491 \begin{textblock}{5}(1, 5) |
|
492 \bl{\texttt{(2*3)+(3+4)}} |
|
493 \end{textblock} |
|
494 |
|
495 \end{frame}} |
|
496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
497 |
|
498 \end{document} |
|
499 |
|
500 %%% Local Variables: |
|
501 %%% mode: latex |
|
502 %%% TeX-master: t |
|
503 %%% End: |
|
504 |