346 \end{tikzpicture} |
366 \end{tikzpicture} |
347 |
367 |
348 \end{frame}} |
368 \end{frame}} |
349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
369 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
350 |
370 |
351 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
371 |
352 \mode<presentation>{ |
372 |
353 \begin{frame}[c] |
373 \newcommand{\qq}{\mbox{\texttt{"}}} |
354 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
355 |
375 \mode<presentation>{ |
356 Last week I showed you\bigskip |
376 \begin{frame}[c] |
|
377 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
|
378 |
|
379 A (context-free) Grammar \bl{$G$} consists of |
357 |
380 |
358 \begin{itemize} |
381 \begin{itemize} |
359 \item an algorithm for automata minimisation |
382 \item a finite set of nonterminal symbols (upper case) |
360 |
383 \item a finite terminal symbols or tokens (lower case) |
361 \item an algorithm for transforming a regular expression into an NFA |
384 \item a start symbol (which must be a nonterminal) |
362 |
385 \item a set of rules |
363 \item an algorithm for transforming an NFA into a DFA (subset construction) |
386 \begin{center} |
364 |
387 \bl{$A \rightarrow \text{rhs}$} |
|
388 \end{center} |
|
389 |
|
390 where \bl{rhs} are sequences involving terminals and nonterminals.\medskip\pause |
|
391 |
|
392 We can also allow rules |
|
393 \begin{center} |
|
394 \bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$} |
|
395 \end{center} |
365 \end{itemize} |
396 \end{itemize} |
366 |
397 |
367 \end{frame}} |
398 |
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
399 \end{frame}} |
369 |
400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
401 |
371 \mode<presentation>{ |
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
372 \begin{frame}[c] |
403 \mode<presentation>{ |
373 \frametitle{\begin{tabular}{c}This Week\end{tabular}} |
404 \begin{frame}[c] |
374 |
405 \frametitle{\begin{tabular}{c}Palindromes\end{tabular}} |
375 Go over the algorithms again, but with two new things and \ldots\medskip |
406 |
376 |
407 \begin{center} |
377 \begin{itemize} |
408 \bl{\begin{tabular}{lcl} |
378 \item with the example: what is the regular expression that accepts every string, except those ending |
409 $S$ & $\rightarrow$ & $\epsilon$ \\ |
379 in \bl{aa}?\medskip |
410 $S$ & $\rightarrow$ & $aSa$ \\ |
380 |
411 $S$ & $\rightarrow$ & $bSb$ \\ |
381 \item Go over the proof for \bl{$L(rev(r)) = Rev(L(r))$}.\medskip |
412 \end{tabular}} |
382 |
|
383 \item Anything else so far. |
|
384 \end{itemize} |
|
385 |
|
386 \end{frame}} |
|
387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
388 |
|
389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
390 \mode<presentation>{ |
|
391 \begin{frame}[c] |
|
392 \frametitle{\begin{tabular}{c}Proofs By Induction\end{tabular}} |
|
393 |
|
394 \begin{itemize} |
|
395 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
|
396 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already |
|
397 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip |
|
398 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already |
|
399 holds for \bl{r$_1$} and \bl{r$_2$}. |
|
400 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
|
401 holds for \bl{r}. |
|
402 \end{itemize} |
|
403 |
|
404 \begin{center} |
|
405 \bl{$P(r):\;\;L(rev(r)) = Rev(L(r))$} |
|
406 \end{center} |
|
407 |
|
408 \end{frame}} |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 \mode<presentation>{ |
|
413 \begin{frame}[t] |
|
414 |
|
415 What is the regular expression that accepts every string, except those ending |
|
416 in \bl{aa}?\pause\bigskip |
|
417 |
|
418 \begin{center} |
|
419 \begin{tabular}{l} |
|
420 \bl{(a + b)$^*$ba}\\ |
|
421 \bl{(a + b)$^*$ab}\\ |
|
422 \bl{(a + b)$^*$bb}\\\pause |
|
423 \bl{a}\\ |
|
424 \bl{\texttt{""}} |
|
425 \end{tabular} |
|
426 \end{center}\pause |
413 \end{center}\pause |
427 |
414 |
428 What are the strings to be avoided?\pause\medskip |
415 or |
429 |
416 |
430 \begin{center} |
417 \begin{center} |
431 \bl{(a + b)$^*$aa} |
418 \bl{\begin{tabular}{lcl} |
432 \end{center} |
419 $S$ & $\rightarrow$ & $\epsilon \;|\; aSa \;|\;bSb$ \\ |
433 |
420 \end{tabular}} |
434 \end{frame}} |
421 \end{center} |
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
422 |
436 |
423 |
437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
424 \end{frame}} |
438 \mode<presentation>{ |
425 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
439 \begin{frame}[t] |
426 |
440 |
427 |
441 An NFA for \bl{(a + b)$^*$aa} |
428 |
442 |
429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
443 \begin{center} |
430 \mode<presentation>{ |
444 \begin{tikzpicture}[scale=2, line width=0.5mm] |
431 \begin{frame}[c] |
445 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
432 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}} |
446 \node[state] (q1) at ( 1,1) {$q_1$}; |
433 |
447 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
434 \begin{center} |
448 \path[->] (q0) edge node[above] {$a$} (q1) |
435 \bl{\begin{tabular}{lcl} |
449 (q1) edge node[above] {$a$} (q2) |
436 $E$ & $\rightarrow$ & $num\_token$ \\ |
450 (q0) edge [loop below] node {$a$} () |
437 $E$ & $\rightarrow$ & $E + E$ \\ |
451 (q0) edge [loop above] node {$b$} () |
438 $E$ & $\rightarrow$ & $E - E$ \\ |
452 ; |
439 $E$ & $\rightarrow$ & $E * E$ \\ |
453 \end{tikzpicture} |
440 $E$ & $\rightarrow$ & $( E )$ |
|
441 \end{tabular}} |
454 \end{center}\pause |
442 \end{center}\pause |
455 |
443 |
456 Minimisation for DFAs\\ |
444 \bl{\texttt{1 + 2 * 3 + 4}} |
457 Subset Construction for NFAs |
445 |
458 |
446 \end{frame}} |
459 \end{frame}} |
447 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
448 |
461 |
449 |
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
450 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
463 \mode<presentation>{ |
451 \mode<presentation>{ |
464 \begin{frame}[c] |
452 \begin{frame}[c] |
465 \frametitle{\begin{tabular}{c}DFA Minimisation\end{tabular}} |
453 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}} |
466 |
|
467 |
|
468 \begin{enumerate} |
|
469 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
470 \item Mark all pairs that accepting and non-accepting states |
|
471 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
472 \begin{center} |
|
473 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
474 \end{center} |
|
475 are marked. If yes, then also mark \bl{(q, p)}. |
|
476 \item Repeat last step until nothing changed. |
|
477 \item All unmarked pairs can be merged. |
|
478 \end{enumerate} |
|
479 |
|
480 \end{frame}} |
|
481 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
482 |
|
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
484 \mode<presentation>{ |
|
485 \begin{frame}[c] |
|
486 |
|
487 Minimal DFA \only<1>{\bl{(a + b)$^*$aa}}\only<2->{\alert{not} \bl{(a + b)$^*$aa}} |
|
488 |
|
489 \begin{center} |
|
490 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
491 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
492 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
493 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
494 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
495 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
496 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
497 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
498 (q1) edge[bend left] node[above] {$b$} (q0) |
|
499 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
500 (q1) edge node[above] {$a$} (q2) |
|
501 (q2) edge [loop right] node {$a$} () |
|
502 (q0) edge [loop below] node {$b$} () |
|
503 ; |
|
504 \end{tikzpicture} |
|
505 \end{center} |
|
506 |
|
507 \onslide<3>{How to get from a DFA to a regular expression?} |
|
508 |
|
509 \end{frame}} |
|
510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
511 |
|
512 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
513 \mode<presentation>{ |
|
514 \begin{frame}[c] |
|
515 |
|
516 \begin{center} |
|
517 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
518 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
519 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
520 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
521 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
522 (q1) edge[bend left] node[above] {$b$} (q0) |
|
523 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
524 (q1) edge node[above] {$a$} (q2) |
|
525 (q2) edge [loop right] node {$a$} () |
|
526 (q0) edge [loop below] node {$b$} () |
|
527 ; |
|
528 \end{tikzpicture} |
|
529 \end{center}\pause\bigskip |
|
530 |
|
531 \onslide<2->{ |
|
532 \begin{center} |
|
533 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
534 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
|
535 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
|
536 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
|
537 |
|
538 \end{tabular} |
|
539 \end{center} |
|
540 } |
|
541 |
|
542 \end{frame}} |
|
543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
544 |
|
545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
546 \mode<presentation>{ |
|
547 \begin{frame}[c] |
|
548 |
|
549 \begin{center} |
|
550 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
551 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
552 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
553 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
554 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
555 (q1) edge[bend left] node[above] {$b$} (q0) |
|
556 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
557 (q1) edge node[above] {$a$} (q2) |
|
558 (q2) edge [loop right] node {$a$} () |
|
559 (q0) edge [loop below] node {$b$} () |
|
560 ; |
|
561 \end{tikzpicture} |
|
562 \end{center}\bigskip |
|
563 |
|
564 \onslide<2->{ |
|
565 \begin{center} |
|
566 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
567 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
568 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
569 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
570 |
|
571 \end{tabular} |
|
572 \end{center} |
|
573 } |
|
574 |
|
575 \onslide<3->{ |
|
576 Arden's Lemma: |
|
577 \begin{center} |
|
578 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
579 \end{center} |
|
580 } |
|
581 |
|
582 \end{frame}} |
|
583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
584 |
|
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
586 \mode<presentation>{ |
|
587 \begin{frame}[c] |
|
588 \frametitle{\begin{tabular}{c}Algorithms on Automata\end{tabular}} |
|
589 |
|
590 |
|
591 \begin{itemize} |
|
592 \item Reg $\rightarrow$ NFA: Thompson-McNaughton-Yamada method\medskip |
|
593 \item NFA $\rightarrow$ DFA: Subset Construction\medskip |
|
594 \item DFA $\rightarrow$ Reg: Brzozowski's Algebraic Method\medskip |
|
595 \item DFA minimisation: Hopcrofts Algorithm\medskip |
|
596 \item complement DFA |
|
597 \end{itemize} |
|
598 |
|
599 \end{frame}} |
|
600 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
601 \newcommand{\qq}{\mbox{\texttt{"}}} |
|
602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
603 \mode<presentation>{ |
|
604 \begin{frame}[c] |
|
605 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
|
606 |
454 |
607 \begin{center} |
455 \begin{center} |
608 \bl{\begin{tabular}{lcl} |
456 \bl{\begin{tabular}{lcl} |
609 $E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ |
457 $E$ & $\rightarrow$ & $F \;|\; F * F$\\ |
610 $F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ |
458 $F$ & $\rightarrow$ & $T \;|\; T + T \;|\; T - T$\\ |
611 $T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ |
459 $T$ & $\rightarrow$ & $num\_token \;|\; ( E )$\\ |
612 \end{tabular}} |
460 \end{tabular}} |
613 \end{center} |
461 \end{center} |
614 |
462 |
615 \bl{$E$}, \bl{$F$} and \bl{$T$} are non-terminals\\ |
|
616 \bl{$E$} is start symbol\\ |
|
617 \bl{$num$}, \bl{(}, \bl{)}, \bl{+} \ldots are terminals\bigskip\\ |
|
618 |
|
619 |
|
620 \bl{\texttt{(2*3)+(3+4)}} |
|
621 |
|
622 \end{frame}} |
|
623 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
624 |
|
625 |
|
626 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
627 \mode<presentation>{ |
|
628 \begin{frame}[c] |
|
629 |
|
630 \begin{center} |
|
631 \bl{\begin{tabular}{lcl} |
|
632 $E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ |
|
633 $F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ |
|
634 $T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ |
|
635 \end{tabular}} |
|
636 \end{center} |
|
637 |
|
638 \begin{center} |
463 \begin{center} |
639 \begin{tikzpicture}[level distance=8mm, blue] |
464 \begin{tikzpicture}[level distance=8mm, blue] |
640 \node {E} |
465 \node {$E$} |
641 child {node {F} |
466 child {node {$F$} |
642 child {node {T} |
467 child {node {$T$} |
643 child {node {\qq(\qq\,E\,\qq)\qq} |
468 child {node {(\,$E$\,)} |
644 child {node{F \qq*\qq{} F} |
469 child {node{$F$ *{} $F$} |
645 child {node {T} child {node {2}}} |
470 child {node {$T$} child {node {2}}} |
646 child {node {T} child {node {3}}} |
471 child {node {$T$} child {node {3}}} |
647 } |
472 } |
648 } |
473 } |
649 } |
474 } |
650 child {node {\qq+\qq}} |
475 child {node {+}} |
651 child {node {T} |
476 child {node {$T$} |
652 child {node {\qq(\qq\,E\,\qq)\qq} |
477 child {node {(\,$E$\,)} |
653 child {node {F} |
478 child {node {$F$} |
654 child {node {T \qq+\qq{} T} |
479 child {node {$T$ +{} $T$} |
655 child {node {3}} |
480 child {node {3}} |
656 child {node {4}} |
481 child {node {4}} |
657 } |
482 } |
658 }} |
483 }} |
659 }}; |
484 }}; |
660 \end{tikzpicture} |
485 \end{tikzpicture} |
661 \end{center} |
486 \end{center} |
662 |
487 |
663 \begin{textblock}{5}(1, 5) |
488 \begin{textblock}{5}(1, 6.5) |
664 \bl{\texttt{(2*3)+(3+4)}} |
489 \bl{\texttt{(2*3)+(3+4)}} |
665 \end{textblock} |
490 \end{textblock} |
666 |
491 |
667 \end{frame}} |
492 \end{frame}} |
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
495 \mode<presentation>{ |
|
496 \begin{frame}[c] |
|
497 \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} |
|
498 |
|
499 A grammar is \alert{ambiguous} if there is a string that has at least parse trees. |
|
500 |
|
501 |
|
502 \begin{center} |
|
503 \bl{\begin{tabular}{lcl} |
|
504 $E$ & $\rightarrow$ & $num\_token$ \\ |
|
505 $E$ & $\rightarrow$ & $E + E$ \\ |
|
506 $E$ & $\rightarrow$ & $E - E$ \\ |
|
507 $E$ & $\rightarrow$ & $E * E$ \\ |
|
508 $E$ & $\rightarrow$ & $( E )$ |
|
509 \end{tabular}} |
|
510 \end{center} |
|
511 |
|
512 \bl{\texttt{1 + 2 * 3 + 4}} |
|
513 |
|
514 \end{frame}} |
|
515 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
516 |
|
517 |
|
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
519 \mode<presentation>{ |
|
520 \begin{frame}[c] |
|
521 \frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}} |
|
522 |
|
523 All rules must be of the form |
|
524 |
|
525 \begin{center} |
|
526 \bl{$A \rightarrow a$} |
|
527 \end{center} |
|
528 |
|
529 or |
|
530 |
|
531 \begin{center} |
|
532 \bl{$A \rightarrow BC$} |
|
533 \end{center} |
|
534 |
|
535 |
|
536 |
|
537 \end{frame}} |
|
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
539 |
|
540 |
669 |
541 |
670 \end{document} |
542 \end{document} |
671 |
543 |
672 %%% Local Variables: |
544 %%% Local Variables: |
673 %%% mode: latex |
545 %%% mode: latex |