430 \small |
441 \small |
431 which takes a state as argument and a character and produces a new state\smallskip\\ |
442 which takes a state as argument and a character and produces a new state\smallskip\\ |
432 this function might not always be defined |
443 this function might not always be defined |
433 \end{itemize} |
444 \end{itemize} |
434 |
445 |
|
446 \begin{center} |
|
447 \bl{$A(Q, q_0, F, \delta)$} |
|
448 \end{center} |
|
449 |
|
450 \end{frame}} |
|
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
452 |
|
453 |
|
454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
455 \mode<presentation>{ |
|
456 \begin{frame}[c] |
|
457 |
|
458 \begin{center} |
|
459 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
460 \end{center}\pause |
|
461 |
|
462 \begin{itemize} |
|
463 \item start can be an accepting state |
|
464 \item it is possible that there is no accepting state |
|
465 \item all states might be accepting (but does not necessarily mean all strings are accepted) |
|
466 \end{itemize} |
|
467 |
|
468 \end{frame}} |
|
469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
470 |
|
471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
472 \mode<presentation>{ |
|
473 \begin{frame}[c] |
|
474 |
|
475 \begin{center} |
|
476 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
477 \end{center} |
|
478 |
|
479 for this automaton \bl{$\delta$} is the function\\ |
|
480 |
|
481 \begin{center} |
|
482 \begin{tabular}{lll} |
|
483 \bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\ |
|
484 \bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\ |
|
485 \end{tabular}\ldots |
|
486 \end{center} |
|
487 |
|
488 \end{frame}} |
|
489 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
490 |
|
491 |
|
492 |
|
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
494 \mode<presentation>{ |
|
495 \begin{frame}[t] |
|
496 \frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} |
|
497 |
|
498 Given |
|
499 |
|
500 \begin{center} |
|
501 \bl{$A(Q, q_0, F, \delta)$} |
|
502 \end{center} |
|
503 |
|
504 you can define |
|
505 |
|
506 \begin{center} |
|
507 \begin{tabular}{l} |
|
508 \bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ |
|
509 \bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\ |
|
510 \end{tabular} |
|
511 \end{center}\pause |
|
512 |
|
513 Whether a string \bl{$s$} is accepted by \bl{$A$}? |
|
514 |
|
515 \begin{center} |
|
516 \hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$} |
|
517 \end{center} |
|
518 \end{frame}} |
|
519 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
520 |
|
521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
522 \mode<presentation>{ |
|
523 \begin{frame}[c] |
|
524 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
|
525 |
|
526 A non-deterministic finite automaton consists again of: |
|
527 |
|
528 \begin{itemize} |
|
529 \item a finite set of states |
|
530 \item one of these states is the start state |
|
531 \item some states are accepting states, and |
|
532 \item there is transition \alert{relation}\medskip |
|
533 \end{itemize} |
|
534 |
|
535 |
|
536 \begin{center} |
|
537 \begin{tabular}{c} |
|
538 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\ |
|
539 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\ |
|
540 \end{tabular} |
|
541 \hspace{10mm} |
|
542 \begin{tabular}{c} |
|
543 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\ |
|
544 \end{tabular} |
|
545 \end{center} |
|
546 |
|
547 \end{frame}} |
|
548 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
549 |
|
550 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
551 \mode<presentation>{ |
|
552 \begin{frame}[c] |
|
553 |
|
554 \begin{center} |
|
555 \includegraphics[scale=0.7]{pics/ch5.jpg} |
|
556 \end{center} |
|
557 |
|
558 |
|
559 \end{frame}} |
|
560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
561 |
|
562 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
563 \mode<presentation>{ |
|
564 \begin{frame}[c] |
|
565 |
|
566 \begin{center} |
|
567 \begin{tabular}[b]{ll} |
|
568 \bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\ |
|
569 \bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\ |
|
570 \bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\ |
|
571 \end{tabular} |
|
572 \end{center} |
|
573 |
|
574 \end{frame}} |
|
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
576 |
|
577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
578 \mode<presentation>{ |
|
579 \begin{frame}[c] |
|
580 |
|
581 \begin{center} |
|
582 \begin{tabular}[t]{ll} |
|
583 \bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\ |
|
584 \end{tabular} |
|
585 \end{center} |
|
586 |
|
587 \end{frame}} |
|
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
589 |
|
590 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
591 \mode<presentation>{ |
|
592 \begin{frame}[c] |
|
593 |
|
594 \begin{center} |
|
595 \begin{tabular}[t]{ll} |
|
596 \bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\ |
|
597 \end{tabular} |
|
598 \end{center} |
|
599 |
|
600 \end{frame}} |
|
601 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
602 |
|
603 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
604 \mode<presentation>{ |
|
605 \begin{frame}[c] |
|
606 |
|
607 \begin{center} |
|
608 \begin{tabular}[b]{ll} |
|
609 \bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\ |
|
610 \end{tabular} |
|
611 \end{center}\pause\bigskip |
|
612 |
|
613 Why can't we just have an epsilon transition from the accepting states to the starting state? |
|
614 |
|
615 \end{frame}} |
|
616 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
617 |
|
618 |
|
619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
620 \mode<presentation>{ |
|
621 \begin{frame}[c] |
|
622 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}} |
|
623 |
|
624 |
|
625 \begin{textblock}{5}(1,2.5) |
|
626 \includegraphics[scale=0.5]{pics/ch5.jpg} |
|
627 \end{textblock} |
|
628 |
|
629 \begin{textblock}{11}(6.5,4.5) |
|
630 \begin{tabular}{r|cl} |
|
631 & a & b\\ |
|
632 \hline |
|
633 $\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\ |
|
634 $\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\ |
|
635 $\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\ |
|
636 $\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\ |
|
637 $\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\ |
|
638 $\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
|
639 $\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\ |
|
640 \onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
|
641 \end{tabular} |
|
642 \end{textblock} |
|
643 |
|
644 |
|
645 \end{frame}} |
|
646 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
647 |
|
648 |
|
649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
650 \mode<presentation>{ |
|
651 \begin{frame}[c] |
|
652 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
|
653 |
|
654 A language is \alert{regular} iff there exists |
|
655 a regular expression that recognises all its strings.\bigskip\medskip |
|
656 |
|
657 or equivalently\bigskip\medskip |
|
658 |
|
659 A language is \alert{regular} iff there exists |
|
660 a deterministic finite automaton that recognises all its strings.\bigskip\pause |
|
661 |
|
662 Why is every finite set of strings a regular language? |
|
663 \end{frame}} |
|
664 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
665 |
|
666 |
|
667 |
|
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
669 \mode<presentation>{ |
|
670 \begin{frame}[c] |
|
671 |
|
672 \begin{center} |
|
673 \includegraphics[scale=0.5]{pics/ch3.jpg} |
|
674 \end{center} |
|
675 |
|
676 \begin{center} |
|
677 \includegraphics[scale=0.5]{pics/ch4.jpg}\\ |
|
678 minimal automaton |
|
679 \end{center} |
|
680 |
|
681 \end{frame}} |
|
682 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
683 |
|
684 |
|
685 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
686 \mode<presentation>{ |
|
687 \begin{frame}[c] |
|
688 |
|
689 \begin{enumerate} |
|
690 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
691 \item Mark all pairs that accepting and non-accepting states |
|
692 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
693 \begin{center} |
|
694 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
695 \end{center} |
|
696 are marked. If yes, then also mark \bl{(q, p)} |
|
697 \item Repeat last step until no chance. |
|
698 \item All unmarked pairs can be merged. |
|
699 \end{enumerate} |
|
700 |
|
701 \end{frame}} |
|
702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
703 |
|
704 |
|
705 |
|
706 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
707 \mode<presentation>{ |
|
708 \begin{frame}[c] |
|
709 |
|
710 Given the function |
|
711 |
|
712 \begin{center} |
|
713 \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
714 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
|
715 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
|
716 $rev(c)$ & $\dn$ & $c$\\ |
|
717 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
|
718 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
|
719 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
|
720 \end{tabular}} |
|
721 \end{center} |
|
722 |
|
723 |
|
724 and the set |
|
725 |
|
726 \begin{center} |
|
727 \bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$} |
|
728 \end{center} |
|
729 |
|
730 prove whether |
|
731 |
|
732 \begin{center} |
|
733 \bl{$L(rev(r)) = Rev (L(r))$} |
|
734 \end{center} |
|
735 |
435 \end{frame}} |
736 \end{frame}} |
436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
437 |
738 |
438 |
739 |
439 \end{document} |
740 \end{document} |