41 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}

    41 \frametitle{Regular Expressions}

    63 which works provably correct in all cases (we did not

    63 that works provably correct in all cases (we only

    64 do the proving part though)

    64 started with the proving part though)

    65 

    65 

    66 \begin{center}

    66 \begin{center}

    67 \bl{$matches\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$}

    67 \bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}

   126 If we want to recognise the string \bl{$abc$} with regular expression \bl{$r$}

   126 If we want to recognise the string \bl{$abc$} with regular

   127 then\medskip

   127 expression \bl{$r$} then\medskip

   316 A \alert{deterministic finite automaton} consists of:

   298 A \alert{\bf deterministic finite automaton}, DFA, consists of:

   319 \item a set of states

   301 \item a set of states \bl{$Q$}

   320 \item one of these states is the start state

   302 \item one of these states is the start state \bl{$q_0$}

   321 \item some states are accepting states, and

   303 \item some states are accepting states \bl{$F$}, and

   322 \item there is transition function\medskip 

   304 \item there is transition function \bl{$\delta$}\bigskip 

   326 new state\smallskip\\

   308 new state; this function might not be everywhere defined

   327 this function might not be everywhere defined

   359 \end{center}\pause

   340 \end{center}

   655 \end{frame}}

   668 \end{frame}

   656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   669 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   657 

   670 

   658 

   671 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   659 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   672 \begin{frame}[c]

   660 \mode<presentation>{

   673 \frametitle{Subset Construction}

   661 \begin{frame}[c]

   662 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}

   685 $\varnothing$ \textcolor{white}{*} & \onslide<2->{$\varnothing$} & \onslide<2->{$\varnothing$}\\

   696 $\{\}$ \textcolor{white}{*} & \onslide<2->{$\{\}$} & \onslide<2->{$\{\}$}\\

   687 $\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{1\}$} & \onslide<3->{$\varnothing$}\\

   698 $\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{1\}$} & \onslide<3->{$\{\}$}\\

   688 $\{2\}$ \onslide<5->{*} & \onslide<3->{$\varnothing$} & \onslide<3->{$\{2\}$}\\

   699 $\{2\}$ \onslide<5->{*} & \onslide<3->{$\{\}$} & \onslide<3->{$\{2\}$}\\

   696 

   707 \end{frame}

   697 \end{frame}}

   708 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   698 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   709 

   710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   711 \begin{frame}[c]

   712 \frametitle{The Result}

   713 

   714 \footnotesize

   715 \begin{center}

   716 \begin{tikzpicture}[scale=0.5,>=stealth',very thick,

   717                     every state/.style={minimum size=0pt,

   718                     draw=blue!50,very thick,fill=blue!20},

   719                     baseline=0mm]

   720 \node[state,initial,accepting]  (q012)  {$\{0,1,2\}$};

   721 \node[state,accepting] (q02) [right=of q012] {$\{0,2\}$};

   722 \node[state] (q01) [above=of q02] {$\{0,1\}$};

   723 \node[state,accepting] (q12) [below=of q02] {$\{1,2\}$};

   724 \node[state] (q0) [right=2cm of q01] {$\{0\}$};

   725 \node[state] (q1) [right=2.5cm of q02] {$\{1\}$};

   726 \node[state,accepting] (q2) [right=1.5cm of q12] {$\{2\}$};

   727 \node[state] (qn) [right=of q1] {$\{\}$};

   728 

   729 \path[->] (q012) edge [loop below] node  {$a$} ();

   730 \path[->] (q012) edge node [above]  {$b$} (q2);

   731 \path[->] (q12) edge [bend left] node [below,pos=0.4]  {$a$} (q1);

   732 \path[->] (q12) edge node [below]  {$b$} (q2);

   733 \path[->] (q02) edge node [above]  {$a$} (q012);

   734 \path[->] (q02) edge [bend left] node [above, pos=0.8]  {$b$} (q2);

   735 \path[->] (q01) edge node [below]  {$a$} (q012);

   736 \path[->] (q01) edge [bend left] node [above]  {$b$} (q2);

   737 \path[->] (q0) edge node [below]  {$a$} (q012);

   738 \path[->] (q0) edge node [right, pos=0.2]  {$b$} (q2);

   739 \path[->] (q1) edge [loop above] node  {$a$} ();

   740 \path[->] (q1) edge node [above]  {$b$} (qn);

   741 \path[->] (q2) edge [loop right] node  {$b$} ();

   742 \path[->] (q2) edge node [below]  {$a$} (qn);

   743 \path[->] (qn) edge [loop above] node  {$a,b$} ();

   744 \end{tikzpicture}

   745 \end{center}

   746 

   747 

   748 \end{frame}

   749 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   750 

   751 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   752 \begin{frame}[c]

   753 \frametitle{Removing Dead States}

   754 

   755 \footnotesize

   756 \begin{center}

   757 \begin{tabular}{ll}

   758 DFA: & NFA:\\

   759 \raisebox{10mm}{%

   760 \begin{tikzpicture}[scale=0.7,>=stealth',very thick,

   761                     every state/.style={minimum size=0pt,

   762                     draw=blue!50,very thick,fill=blue!20}]

   763 \node[state,initial,accepting]  (q012)  {$\{0,1,2\}$};

   764 \node[state,accepting] (q2) [right=of q012] {$\{2\}$};

   765 \node[state] (qn) [right=of q2] {$\{\}$};

   766 

   767 \path[->] (q012) edge [loop below] node  {\alert{$a$}} ();

   768 \path[->] (q012) edge node [above]  {\alert{$b$}} (q2);

   769 \path[->] (q2) edge [loop below] node  {\alert{$b$}} ();

   770 \path[->] (q2) edge node [below]  {\alert{$a$}} (qn);

   771 \path[->] (qn) edge [loop above] node 

   772    {$\alert{a},\alert{b}$} ();

   773 \end{tikzpicture}}

   774 &

   775 \begin{tikzpicture}[scale=0.7,>=stealth',very thick,

   776                     every state/.style={minimum size=0pt,

   777                     draw=blue!50,very thick,fill=blue!20},]

   778 \node[state,initial]  (q_0)  {$q_0$};

   779 \node[state] (q_1) [above=of q_0] {$q_1$};

   780 \node[state, accepting] (q_2) [below=of q_0] {$q_2$};

   781 \path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_1);

   782 \path[->] (q_0) edge node [left]  {\alert{$\epsilon$}} (q_2);

   783 \path[->] (q_0) edge [loop right] node  {\alert{$a$}} ();

   784 \path[->] (q_1) edge [loop above] node  {\alert{$a$}} ();

   785 \path[->] (q_2) edge [loop below] node  {\alert{$b$}} ();

   786 \end{tikzpicture}

   787 \end{tabular}

   788 \end{center}

   789 

   790 \end{frame}

   791 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   792 

   793 

   709 \onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}

   804 \onslide<2->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}

   712 \onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}

   807 \onslide<2->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}

   808 \end{tikzpicture}\\

   809 \end{center}

   810 

   811 \end{frame}

   812 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   813 

   814 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   815 \begin{frame}[c]

   816 \frametitle{DFA Minimisation}

   817 

   818 \begin{enumerate}

   819 \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}

   820 \item Mark all pairs that accepting and non-accepting states

   821 \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether

   822 \begin{center}

   823 \bl{$(\delta(q, c), \delta(p,c))$}

   824 \end{center} 

   825 are marked. If yes, then also mark \bl{$(q, p)$}.

   826 \item Repeat last step until no change.

   827 \item All unmarked pairs can be merged.

   828 \end{enumerate}

   829 

   830 \end{frame}

   831 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   832 

   833 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   834 \begin{frame}[c]

   835 

   836 \begin{center}

   837 \begin{tikzpicture}[>=stealth',very thick,auto,

   838                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   839 \node[state,initial]  (q_0)  {$q_0$};

   840 \node[state] (q_1) [right=of q_0] {$q_1$};

   841 \node[state] (q_2) [below right=of q_0] {$q_2$};

   842 \node[state] (q_3) [right=of q_2] {$q_3$};

   843 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   844 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   845 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

   846 \path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();

   847 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   848 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   849 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   850 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

   851 \path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();

   852 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);

   853 \end{tikzpicture}

   854 \end{center}

   855 

   856 \mbox{}\\[-20mm]\mbox{}

   857 

   858 \begin{center}

   859 \begin{tikzpicture}[scale=0.8,line width=0.8mm]

   860 \draw (0,0) -- (4,0);

   861 \draw (0,1) -- (4,1);

   862 \draw (0,2) -- (3,2);

   863 \draw (0,3) -- (2,3);

   864 \draw (0,4) -- (1,4);

   865 

   866 \draw (0,0) -- (0, 4);

   867 \draw (1,0) -- (1, 4);

   868 \draw (2,0) -- (2, 3);

   869 \draw (3,0) -- (3, 2);

   870 \draw (4,0) -- (4, 1);

   871 

   872 \draw (0.5,-0.5) node {$q_0$}; 

   873 \draw (1.5,-0.5) node {$q_1$}; 

   874 \draw (2.5,-0.5) node {$q_2$}; 

   875 \draw (3.5,-0.5) node {$q_3$};

   876  

   877 \draw (-0.5, 3.5) node {$q_1$}; 

   878 \draw (-0.5, 2.5) node {$q_2$}; 

   879 \draw (-0.5, 1.5) node {$q_3$}; 

   880 \draw (-0.5, 0.5) node {$q_4$}; 

   881 

   882 \draw (0.5,0.5) node {\large$\star$}; 

   883 \draw (1.5,0.5) node {\large$\star$}; 

   884 \draw (2.5,0.5) node {\large$\star$}; 

   885 \draw (3.5,0.5) node {\large$\star$};

   886 \end{tikzpicture}

   887 \end{center}

   888 

   889 \end{frame}

   890 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   891 

   892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   893 \begin{frame}[c]

   894 

   895 \begin{center}

   896 \begin{tabular}{@{\hspace{-8mm}}cc@{}}

   897 \begin{tikzpicture}[>=stealth',very thick,auto,

   898                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   899 \node[state,initial]  (q_0)  {$q_0$};

   900 \node[state] (q_1) [right=of q_0] {$q_1$};

   901 \node[state] (q_2) [below right=of q_0] {$q_2$};

   902 \node[state] (q_3) [right=of q_2] {$q_3$};

   903 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   904 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   905 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

   906 \path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();

   907 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   908 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   909 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   910 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

   911 \path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();

   912 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);

   913 \end{tikzpicture}

   914 &

   915 \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]

   916 \draw (0,0) -- (4,0);

   917 \draw (0,1) -- (4,1);

   918 \draw (0,2) -- (3,2);

   919 \draw (0,3) -- (2,3);

   920 \draw (0,4) -- (1,4);

   921 

   922 \draw (0,0) -- (0, 4);

   923 \draw (1,0) -- (1, 4);

   924 \draw (2,0) -- (2, 3);

   925 \draw (3,0) -- (3, 2);

   926 \draw (4,0) -- (4, 1);

   927 

   928 \draw (0.5,-0.5) node {$q_0$}; 

   929 \draw (1.5,-0.5) node {$q_1$}; 

   930 \draw (2.5,-0.5) node {$q_2$}; 

   931 \draw (3.5,-0.5) node {$q_3$};

   932  

   933 \draw (-0.5, 3.5) node {$q_1$}; 

   934 \draw (-0.5, 2.5) node {$q_2$}; 

   935 \draw (-0.5, 1.5) node {$q_3$}; 

   936 \draw (-0.5, 0.5) node {$q_4$}; 

   937 

   938 \draw (0.5,0.5) node {\large$\star$}; 

   939 \draw (1.5,0.5) node {\large$\star$}; 

   940 \draw (2.5,0.5) node {\large$\star$}; 

   941 \draw (3.5,0.5) node {\large$\star$};

   942 \draw (0.5,1.5) node {\large$\star$}; 

   943 \draw (2.5,1.5) node {\large$\star$}; 

   944 \draw (0.5,3.5) node {\large$\star$}; 

   945 \draw (1.5,2.5) node {\large$\star$}; 

   946 \end{tikzpicture}}

   947 \end{tabular}

   948 \end{center}

   949 

   950 

   951 \mbox{}\\[-20mm]\mbox{}

   952 

   953 \begin{center}

   954 \begin{tikzpicture}[>=stealth',very thick,auto,

   955                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   956 \node[state,initial]  (q_02)  {$q_{0, 2}$};

   957 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

   958 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

   959 \path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

   960 \path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

   961 \path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();

   962 \path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);

   963 \path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

   964 \end{tikzpicture}\\

   965 minimal automaton

   966 \end{center}

   967 

   968 \end{frame}

   969 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   970 

   971 

   972 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   973 \begin{frame}[c]

   974 \frametitle{Alternatives}

   975 \mbox{}\\[-17mm]\mbox{}

   976 

   977 \begin{center}

   978 \begin{tikzpicture}[>=stealth',very thick,auto,

   979                     every state/.style={minimum size=0pt,

   980                     inner sep=2pt,draw=blue!50,very thick,fill=blue!20}]

   981 \only<1>{\node[state,initial]  (q_0)  {$q_0$};}

   982 \only<2->{\node[state,accepting]  (q_0)  {$q_0$};}

   983 \node[state] (q_1) [right=of q_0] {$q_1$};

   984 \node[state] (q_2) [below right=of q_0] {$q_2$};

   985 \node[state] (q_3) [right=of q_2] {$q_3$};

   986 \only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}

   987 \only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};}

   988 \only<1-2>{

   989 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   990 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

   991 \path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

   992 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   993 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   994 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   995 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

   996 \path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();

   997 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}

   998 \only<3->{

   999 \path[<-] (q_0) edge node [above]  {\alert{$a$}} (q_1);

  1000 \path[<-] (q_1) edge node [above]  {\alert{$a$}} (q_4);

  1001 \path[<-] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

  1002 \path[<-] (q_3) edge node [right]  {\alert{$a$}} (q_4);

  1003 \path[<-] (q_2) edge node [above]  {\alert{$a$}} (q_3);

  1004 \path[<-] (q_1) edge node [right]  {\alert{$b$}} (q_2);

  1005 \path[<-] (q_0) edge node [above]  {\alert{$b$}} (q_2);

  1006 \path[<-] (q_2) edge [loop left] node  {\alert{$b$}} ();

  1007 \path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}

  1008 \end{tikzpicture}

  1009 \end{center}

  1010 \mbox{}\\[-18mm]

  1011 

  1012 \small

  1013 \begin{itemize}

  1014 \item<2-> exchange initial / accepting states\\[-2mm]

  1015 \item<3-> reverse all edges\\[-2mm]

  1016 \item<4-> subset construction $\Rightarrow$ DFA\\[-2mm]

  1017 \item<5-> remove dead states\\[-2mm]

  1018 \item<6-> repeat once more 

  1019           \onslide<6->{$\Rightarrow$ minimal DFA}

  1020 \end{itemize}

  1021 

  1022 \end{frame}

  1023 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

  1024 

  1025 

  1026 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1027 \begin{frame}[c]

  1028 \frametitle{Regexps and Automata}

  1029 

  1030 \begin{center}

  1031 \begin{tikzpicture}

  1032 \node (rexp)  {\bl{\bf Regexps}};

  1033 \node (nfa) [right=of rexp] {\bl{\bf NFAs}};

  1034 \node (dfa) [right=of nfa] {\bl{\bf DFAs}};

  1035 \onslide<1->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}

  1036 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);

  1037 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);

  1038 \onslide<1->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}

   721 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1047 

   722 \mode<presentation>{

  1048 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   723 \begin{frame}[c]

   724 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}

   725 

   726 A language is \alert{regular} iff there exists

   727 a regular expression that recognises all its strings.\bigskip\medskip

   728 

   729 or {\bf equivalently}\bigskip\medskip

   730 

   731 A language is \alert{regular} iff there exists

   732 a deterministic finite automaton that recognises all its strings.\bigskip\medskip\pause

   733 

   734 Why is every finite set of strings a regular language?

   735 \end{frame}}

   736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   737 

   738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   739 \mode<presentation>{

   764 \end{frame}}

  1073 \end{frame}

   765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1074 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   766 

  1075 

   767 

  1076 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   768 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   769 \mode<presentation>{

   799 \end{frame}}

  1106 \end{frame}

   800 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   801 

  1108 

   802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   803 \mode<presentation>{

   840 \end{frame}}

  1146 \end{frame}

   841 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   842 

  1148 

   843 

  1149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   844 

  1150 \begin{frame}[c]

   845 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1151 \frametitle{Regexps and Automata}

   846 \mode<presentation>{

  1152 

  1153 \begin{center}

  1154 \begin{tikzpicture}

  1155 \node (rexp)  {\bl{\bf Regexps}};

  1156 \node (nfa) [right=of rexp] {\bl{\bf NFAs}};

  1157 \node (dfa) [right=of nfa] {\bl{\bf DFAs}};

  1158 \onslide<1->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}

  1159 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);

  1160 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);

  1161 \onslide<1->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}

  1162 \onslide<1->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);}

  1163 \end{tikzpicture}\\

  1164 \end{center}

  1165 

  1166 \end{frame}

  1167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1168 

  1169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1170 \begin{frame}[c]

  1171 \frametitle{Regular Languages (3)}

  1172 

  1173 A language is \alert{\bf regular} iff there exists a regular

  1174 expression that recognises all its strings.\bigskip\medskip

  1175 

  1176 or {\bf equivalently}\bigskip\medskip

  1177 

  1178 A language is \alert{\bf regular} iff there exists a

  1179 deterministic finite automaton that recognises all its

  1180 strings.\bigskip\medskip\pause

  1181 

  1182 Why is every finite set of strings a regular language?

  1183 \end{frame}

  1184 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1185 

  1186 

  1187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   875 \end{frame}}

  1216 \end{frame}