734 in NFAs (with backtracking). |
734 in NFAs (with backtracking). |
735 |
735 |
736 \end{frame} |
736 \end{frame} |
737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
738 |
738 |
|
739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
740 \begin{frame}[c] |
|
741 \frametitle{Subset Construction} |
|
742 |
|
743 |
|
744 \begin{textblock}{5}(1,3.5) |
|
745 \begin{center} |
|
746 \begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick, |
|
747 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
748 \node[state,initial] (Q_0) {$\mbox{Q}_0$}; |
|
749 \node[state] (Q_1) [below=of Q_0] {$\mbox{Q}_1$}; |
|
750 \node[state, accepting] (Q_2) [below=of Q_1] {$\mbox{Q}_2$}; |
|
751 |
|
752 \path[->] (Q_0) edge node [left] {\alert{$1$}} (Q_1); |
|
753 \path[->] (Q_1) edge node [left] {\alert{$0,1$}} (Q_2); |
|
754 \path[->] (Q_0) edge [loop right] node {\alert{$0,1$}} (); |
|
755 %\path[->] (Q_1) edge [loop above] node {\alert{$a$}} (); |
|
756 %\path[->] (Q_2) edge [loop below] node {\alert{$b$}} (); |
|
757 \end{tikzpicture} |
|
758 \end{center} |
|
759 \end{textblock} |
|
760 |
|
761 \begin{textblock}{11}(6.5,4) |
|
762 \begin{tabular}{r|cl} |
|
763 nodes \textcolor{white}{*} & $0$ & $1$\\ |
|
764 \hline |
|
765 $\{\}$ \textcolor{white}{*} & \onslide<2->{$\{\}$} & \onslide<2->{$\{\}$}\\ |
|
766 \onslide<5->{s:} $\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0\}$} & \onslide<3->{$\{0,1\}$}\\ |
|
767 $\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{2\}$} & \onslide<3->{$\{2\}$}\\ |
|
768 $\{2\}$ \onslide<5->{*} & \onslide<3->{$\{\}$} & \onslide<3->{$\{\}$}\\ |
|
769 $\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,2\}$} & \onslide<4->{$\{0,1,2\}$}\\ |
|
770 $\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0\}$} & \onslide<4->{$\{0,1\}$}\\ |
|
771 $\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{2\}$} & \onslide<4->{$\{2\}$}\\ |
|
772 $\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,2\}$} & \onslide<4->{$\{0,1,2\}$}\\ |
|
773 \end{tabular} |
|
774 \end{textblock} |
|
775 |
|
776 \end{frame} |
|
777 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
739 |
778 |
740 |
779 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
741 |
780 \begin{frame}[c] |
742 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
781 \frametitle{The Result} |
743 \begin{frame}[c] |
782 |
744 \frametitle{Subset Construction} |
783 \footnotesize |
|
784 \begin{center} |
|
785 \begin{tikzpicture}[scale=0.5,>=stealth',very thick, |
|
786 every state/.style={minimum size=0pt, |
|
787 draw=blue!50,very thick,fill=blue!20}, |
|
788 baseline=0mm] |
|
789 \node[state,initial] (q0) {$\{0\}$}; |
|
790 \node[state] (q01) [right=of q0] {$\{0,1\}$}; |
|
791 \node[state,accepting] (q12) [above=of q01] {$\{1,2\}$}; |
|
792 \node[state,accepting] (q02) [below=of q01] {$\{0,2\}$}; |
|
793 \node[state] (q1) [right=2cm of q12] {$\{1\}$}; |
|
794 \node[state,accepting] (q2) [right=2.5cm of q01] {$\{2\}$}; |
|
795 \node[state,accepting] (q012) [right=1.5cm of q02] {$\{0,1,2\}$}; |
|
796 \node[state] (Qn) [right=of q2] {$\{\}$}; |
|
797 |
|
798 \path[->] (q0) edge [loop above] node {\alert{$0$}} (); |
|
799 \path[->] (q0) edge node [above] {\alert{$1$}} (q01); |
|
800 \path[->] (q02) edge [bend left] node [left] {\alert{$1$}} (q01); |
|
801 \path[->] (q02) edge node [below] {\alert{$0$}} (q0); |
|
802 \path[->] (q01) edge node [above] {\alert{$1$}} (q012); |
|
803 \path[->] (q01) edge [bend left] node [right] {\alert{$0$}} (q02); |
|
804 \path[->] (q12) edge node [below] {\alert{$0,1$}} (q2); |
|
805 \path[->] (q1) edge node [right] {\alert{$0,1$}} (q2); |
|
806 \path[->] (q2) edge node [above] {\alert{$0,1$}} (Qn); |
|
807 \path[->] (q012) edge [loop right] node {\alert{$1$}} (); |
|
808 \path[->] (q012) edge node [below] {\alert{$0$}} (q02); |
|
809 \path[->] (Qn) edge [loop above] node {$\alert{0},\alert{1}$} (); |
|
810 \end{tikzpicture} |
|
811 \end{center} |
|
812 |
|
813 |
|
814 \end{frame} |
|
815 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
816 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
817 \begin{frame}[c] |
|
818 \frametitle{Removing Dead States} |
|
819 |
|
820 \footnotesize |
|
821 \begin{center} |
|
822 \begin{tabular}{ll} |
|
823 \large DFA: & \large (original) NFA:\\ |
|
824 \raisebox{0mm}{% |
|
825 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
|
826 every state/.style={minimum size=0pt, |
|
827 draw=blue!50,very thick,fill=blue!20}] |
|
828 \node[state,initial] (q0) {$\{0\}$}; |
|
829 \node[state] (q01) [right=of q0] {$\{0,1\}$}; |
|
830 \node[state,accepting] (q02) [below=of q01] {$\{0,2\}$}; |
|
831 \node[state,accepting] (q012) [right=1.5cm of q02] {$\{0,1,2\}$}; |
|
832 |
|
833 \path[->] (q0) edge [loop above] node {\alert{$0$}} (); |
|
834 \path[->] (q0) edge node [above] {\alert{$1$}} (q01); |
|
835 \path[->] (q02) edge [bend left] node [left] {\alert{$1$}} (q01); |
|
836 \path[->] (q02) edge node [below] {\alert{$0$}} (q0); |
|
837 \path[->] (q01) edge node [above] {\alert{$1$}} (q012); |
|
838 \path[->] (q01) edge [bend left] node [right] {\alert{$0$}} (q02); |
|
839 \path[->] (q012) edge [loop right] node {\alert{$1$}} (); |
|
840 \path[->] (q012) edge node [below] {\alert{$0$}} (q02); |
|
841 \end{tikzpicture}} |
|
842 & |
|
843 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
|
844 every state/.style={minimum size=0pt, |
|
845 draw=blue!50,very thick,fill=blue!20},] |
|
846 \node[state,initial] (Q_0) {$\mbox{Q}_0$}; |
|
847 \node[state] (Q_1) [below=of Q_0] {$\mbox{Q}_1$}; |
|
848 \node[state, accepting] (Q_2) [below=of Q_1] {$\mbox{Q}_2$}; |
|
849 |
|
850 \path[->] (Q_0) edge node [left] {\alert{$1$}} (Q_1); |
|
851 \path[->] (Q_1) edge node [left] {\alert{$0,1$}} (Q_2); |
|
852 \path[->] (Q_0) edge [loop right] node {\alert{$0,1$}} (); |
|
853 \end{tikzpicture} |
|
854 \end{tabular} |
|
855 \end{center} |
|
856 |
|
857 \end{frame} |
|
858 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
859 |
|
860 |
|
861 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
862 \begin{frame}[c] |
|
863 \frametitle{Subset Construction ($\epsilon$NFA)} |
745 |
864 |
746 |
865 |
747 \begin{textblock}{5}(1,1.5) |
866 \begin{textblock}{5}(1,1.5) |
748 \begin{center} |
867 \begin{center} |
749 \begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick, |
868 \begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick, |