618 \frametitle{Case $r_1\cdot r_2$} |
618 \frametitle{Case $r_1\cdot r_2$} |
619 |
619 |
620 \mbox{}\bigskip |
620 \mbox{}\bigskip |
621 \onslide<1>{By recursion we are given two automata:\bigskip} |
621 \onslide<1>{By recursion we are given two automata:\bigskip} |
622 |
622 |
623 \begin{tikzpicture}[node distance=3mm, |
623 {\centering\begin{tikzpicture}[node distance=3mm, |
624 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
624 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
625 \node[state, initial] (q_0) {$\mbox{}$}; |
625 \node[state, initial] (q_0) {$\mbox{}$}; |
626 \node (r_1) [right=of q_0] {$\ldots$}; |
626 \node (r_1) [right=of q_0] {$\ldots$}; |
627 \only<1>{ |
627 \only<1>{ |
628 \node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$}; |
628 \node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$}; |
649 \only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};} |
649 \only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};} |
650 \only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};} |
650 \only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};} |
651 \only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};} |
651 \only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};} |
652 \only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};} |
652 \only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};} |
653 \end{pgfonlayer} |
653 \end{pgfonlayer} |
654 \end{tikzpicture}\bigskip\bigskip |
654 \end{tikzpicture}}\bigskip\bigskip |
655 |
655 |
656 \small |
656 \small |
657 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them |
657 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them |
658 via $\epsilon$-transitions to the starting state of the second automaton. |
658 via $\epsilon$-transitions to the starting state of the second automaton. |
659 |
659 |
665 \begin{frame}[t] |
665 \begin{frame}[t] |
666 \frametitle{Case $r_1+ r_2$} |
666 \frametitle{Case $r_1+ r_2$} |
667 |
667 |
668 \onslide<1>{By recursion we are given two automata:\smallskip} |
668 \onslide<1>{By recursion we are given two automata:\smallskip} |
669 |
669 |
670 \begin{tikzpicture}[node distance=3mm, |
670 \hspace{2cm}\begin{tikzpicture}[node distance=3mm, |
671 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
671 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
672 \onslide<1>{\node at (0,0) (1) {$\mbox{}$};} |
672 \onslide<1>{\node at (0,0) (1) {$\mbox{}$};} |
673 \onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};} |
673 \onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};} |
674 \only<1>{ |
674 \only<1>{ |
675 \node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$}; |
675 \node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$}; |
711 \begin{frame}[c] |
711 \begin{frame}[c] |
712 \frametitle{Case $r^*$} |
712 \frametitle{Case $r^*$} |
713 |
713 |
714 \onslide<1>{By recursion we are given an automaton for $r$:\smallskip} |
714 \onslide<1>{By recursion we are given an automaton for $r$:\smallskip} |
715 |
715 |
716 \begin{tikzpicture}[node distance=3mm, |
716 \hspace{2cm}\begin{tikzpicture}[node distance=3mm, |
717 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
717 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
718 \onslide<1>{\node at (0,0) (1) {$\mbox{}$};} |
718 \onslide<1>{\node at (0,0) (1) {$\mbox{}$};} |
719 \onslide<2>{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};} |
719 \onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};} |
720 \only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};} |
720 \only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};} |
721 \only<2>{\node[state] (2) [right=16mm of 1] {$\mbox{}$};} |
721 \only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};} |
722 \node (a) [right=of 2] {$\ldots$}; |
722 \node (a) [right=of 2] {$\ldots$}; |
723 \only<1>{ |
723 \only<1>{ |
724 \node[state, accepting] (a1) [right=of a] {$\mbox{}$}; |
724 \node[state, accepting] (a1) [right=of a] {$\mbox{}$}; |
725 \node[state, accepting] (a2) [above=of a1] {$\mbox{}$}; |
725 \node[state, accepting] (a2) [above=of a1] {$\mbox{}$}; |
726 \node[state, accepting] (a3) [below=of a1] {$\mbox{}$};} |
726 \node[state, accepting] (a3) [below=of a1] {$\mbox{}$};} |
727 \only<2>{ |
727 \only<2->{ |
728 \node[state] (a1) [right=of a] {$\mbox{}$}; |
728 \node[state] (a1) [right=of a] {$\mbox{}$}; |
729 \node[state] (a2) [above=of a1] {$\mbox{}$}; |
729 \node[state] (a2) [above=of a1] {$\mbox{}$}; |
730 \node[state] (a3) [below=of a1] {$\mbox{}$};} |
730 \node[state] (a3) [below=of a1] {$\mbox{}$};} |
731 \only<2>{ |
731 \only<2->{ |
732 \path[->] (1) edge node [above] {\alert{$\epsilon$}} (2); |
732 \path[->] (1) edge node [above] {\alert{$\epsilon$}} (2); |
733 \path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1); |
733 \path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1); |
734 \path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1); |
734 \path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1); |
735 \path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1); |
735 \path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1); |
736 |
736 |
737 } |
737 } |
738 \begin{pgfonlayer}{background} |
738 \begin{pgfonlayer}{background} |
739 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};} |
739 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};} |
740 \only<2>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};} |
740 \only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};} |
741 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};} |
741 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};} |
742 \only<2>{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};} |
742 \only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};} |
743 \end{pgfonlayer} |
743 \end{pgfonlayer} |
744 \end{tikzpicture} |
744 \end{tikzpicture}\bigskip |
745 |
745 |
746 |
746 \onslide<3->{ |
747 Why can't we just have an epsilon transition from the accepting states to the starting state? |
747 Why can't we just have an epsilon transition from the accepting states to the starting state?} |
748 |
748 |
749 \end{frame}} |
749 \end{frame}} |
750 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
750 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
751 |
751 |
752 |
752 |
772 \end{center} |
772 \end{center} |
773 \end{textblock} |
773 \end{textblock} |
774 |
774 |
775 \begin{textblock}{11}(6.5,4.5) |
775 \begin{textblock}{11}(6.5,4.5) |
776 \begin{tabular}{r|cl} |
776 \begin{tabular}{r|cl} |
777 & a & b\\ |
777 nodes \textcolor{white}{*} & $a$ & $b$\\ |
778 \hline |
778 \hline |
779 $\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\ |
779 $\varnothing$ \textcolor{white}{*} & \onslide<2->{$\varnothing$} & \onslide<2->{$\varnothing$}\\ |
780 $\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\ |
780 $\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0,1,2\}$} & \onslide<3->{$\{2\}$}\\ |
781 $\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\ |
781 $\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{1\}$} & \onslide<3->{$\varnothing$}\\ |
782 $\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\ |
782 $\{2\}$ \onslide<5->{*} & \onslide<3->{$\varnothing$} & \onslide<3->{$\{2\}$}\\ |
783 $\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\ |
783 $\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\ |
784 $\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
784 $\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\ |
785 $\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\ |
785 $\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{1\}$} & \onslide<4->{$\{2\}$}\\ |
786 \onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
786 \onslide<5->{s:} $\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\ |
787 \end{tabular} |
787 \end{tabular} |
788 \end{textblock} |
788 \end{textblock} |
789 |
789 |
790 |
790 |
791 \end{frame}} |
791 \end{frame}} |
798 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
798 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
799 |
799 |
800 A language is \alert{regular} iff there exists |
800 A language is \alert{regular} iff there exists |
801 a regular expression that recognises all its strings.\bigskip\medskip |
801 a regular expression that recognises all its strings.\bigskip\medskip |
802 |
802 |
803 or equivalently\bigskip\medskip |
803 or {\bf equivalently}\bigskip\medskip |
804 |
804 |
805 A language is \alert{regular} iff there exists |
805 A language is \alert{regular} iff there exists |
806 a deterministic finite automaton that recognises all its strings.\bigskip\pause |
806 a deterministic finite automaton that recognises all its strings.\bigskip\medskip\pause |
807 |
807 |
808 Why is every finite set of strings a regular language? |
808 Why is every finite set of strings a regular language? |
809 \end{frame}} |
809 \end{frame}} |
810 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
810 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
811 |
811 |
812 |
812 |
813 |
813 |
814 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
814 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
815 \mode<presentation>{ |
815 \mode<presentation>{ |
816 \begin{frame}[c] |
816 \begin{frame}<1-2>[c] |
817 |
817 |
818 \begin{center} |
818 \begin{center} |
819 \includegraphics[scale=0.5]{pics/ch3.jpg} |
819 \begin{tikzpicture}[>=stealth',very thick,auto, |
820 \end{center} |
820 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
821 |
821 \node[state,initial] (q_0) {$q_0$}; |
822 \begin{center} |
822 \node[state] (q_1) [right=of q_0] {$q_1$}; |
823 \includegraphics[scale=0.5]{pics/ch4.jpg}\\ |
823 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
824 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
825 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
826 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
827 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
828 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
829 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
830 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
831 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
832 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
833 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
834 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
|
835 \end{tikzpicture} |
|
836 \end{center} |
|
837 |
|
838 \mbox{}\\[-20mm]\mbox{} |
|
839 |
|
840 \begin{center} |
|
841 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
842 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
843 \node[state,initial] (q_02) {$q_{0, 2}$}; |
|
844 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
|
845 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
|
846 \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
|
847 \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
|
848 \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
|
849 \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
|
850 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
851 \end{tikzpicture}\\ |
824 minimal automaton |
852 minimal automaton |
825 \end{center} |
853 \end{center} |
826 |
854 |
827 \end{frame}} |
855 \end{frame}} |
828 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
829 |
|
830 |
|
831 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
832 \mode<presentation>{ |
|
833 \begin{frame}[c] |
|
834 |
|
835 \begin{enumerate} |
|
836 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
837 \item Mark all pairs that are accepting and non-accepting states |
|
838 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
839 \begin{center} |
|
840 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
841 \end{center} |
|
842 are marked. If yes, then also mark \bl{(q, p)} |
|
843 \item Repeat last step until no chance. |
|
844 \item All unmarked pairs can be merged. |
|
845 \end{enumerate} |
|
846 |
|
847 \end{frame}} |
|
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
849 |
|
850 |
|
851 |
857 |
852 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
858 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
853 \mode<presentation>{ |
859 \mode<presentation>{ |
854 \begin{frame}[c] |
860 \begin{frame}[c] |
855 |
861 |