93 \end{tabular} |
93 \end{tabular} |
94 \end{center} |
94 \end{center} |
95 |
95 |
96 \end{frame} |
96 \end{frame} |
97 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
97 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
98 |
|
99 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
100 \begin{frame}[c] |
|
101 |
|
102 To see what is going on, define |
|
103 |
|
104 \begin{center} |
|
105 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
|
106 \end{center}\bigskip\bigskip |
|
107 |
|
108 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
|
109 |
|
110 \begin{center} |
|
111 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
|
112 $Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ |
|
113 $Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ |
|
114 $Der\,a\,A$ & $=$ & $\varnothing$\\ |
|
115 \end{tabular}} |
|
116 \end{center} |
|
117 |
|
118 \end{frame} |
|
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
120 |
|
121 |
|
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
123 \begin{frame}[c] |
|
124 \frametitle{The Idea of the Algorithm} |
|
125 |
|
126 If we want to recognise the string \bl{$abc$} with regular |
|
127 expression \bl{$r$} then\medskip |
|
128 |
|
129 \begin{enumerate} |
|
130 \item \bl{$Der\,a\,(L(r))$}\pause |
|
131 \item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause |
|
132 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\bigskip\pause |
|
133 \item finally we test whether the empty string is in this set\pause\medskip |
|
134 \end{enumerate} |
|
135 |
|
136 The matching algorithm works similarly, just over regular expressions instead of sets. |
|
137 \end{frame} |
|
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
139 |
|
140 |
98 |
141 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
99 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
142 \begin{frame}[c] |
100 \begin{frame}[c] |
143 |
101 |
144 Input: string \bl{$abc$} and regular expression \bl{$r$} |
102 Input: string \bl{$abc$} and regular expression \bl{$r$} |
443 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
444 |
402 |
445 |
403 |
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
447 \begin{frame}[c] |
405 \begin{frame}[c] |
448 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
406 \frametitle{\begin{tabular}{c} |
|
407 Non-Deterministic\\[-1mm] |
|
408 Finite Automata\end{tabular}} |
449 |
409 |
450 A non-deterministic finite automaton consists again of: |
410 A non-deterministic finite automaton consists again of: |
451 |
411 |
452 \begin{itemize} |
412 \begin{itemize} |
453 \item a finite set of states |
413 \item a finite set of states |
724 \node[state] (q0) [right=2cm of q01] {$\{0\}$}; |
684 \node[state] (q0) [right=2cm of q01] {$\{0\}$}; |
725 \node[state] (q1) [right=2.5cm of q02] {$\{1\}$}; |
685 \node[state] (q1) [right=2.5cm of q02] {$\{1\}$}; |
726 \node[state,accepting] (q2) [right=1.5cm of q12] {$\{2\}$}; |
686 \node[state,accepting] (q2) [right=1.5cm of q12] {$\{2\}$}; |
727 \node[state] (qn) [right=of q1] {$\{\}$}; |
687 \node[state] (qn) [right=of q1] {$\{\}$}; |
728 |
688 |
729 \path[->] (q012) edge [loop below] node {$a$} (); |
689 \path[->] (q012) edge [loop below] node {\alert{$a$}} (); |
730 \path[->] (q012) edge node [above] {$b$} (q2); |
690 \path[->] (q012) edge node [above] {\alert{$b$}} (q2); |
731 \path[->] (q12) edge [bend left] node [below,pos=0.4] {$a$} (q1); |
691 \path[->] (q12) edge [bend left] node [below,pos=0.4] {\alert{$a$}} (q1); |
732 \path[->] (q12) edge node [below] {$b$} (q2); |
692 \path[->] (q12) edge node [below] {\alert{$b$}} (q2); |
733 \path[->] (q02) edge node [above] {$a$} (q012); |
693 \path[->] (q02) edge node [above] {\alert{$a$}} (q012); |
734 \path[->] (q02) edge [bend left] node [above, pos=0.8] {$b$} (q2); |
694 \path[->] (q02) edge [bend left] node [above, pos=0.8] {\alert{$b$}} (q2); |
735 \path[->] (q01) edge node [below] {$a$} (q012); |
695 \path[->] (q01) edge node [below] {\alert{$a$}} (q012); |
736 \path[->] (q01) edge [bend left] node [above] {$b$} (q2); |
696 \path[->] (q01) edge [bend left] node [above] {\alert{$b$}} (q2); |
737 \path[->] (q0) edge node [below] {$a$} (q012); |
697 \path[->] (q0) edge node [below] {\alert{$a$}} (q012); |
738 \path[->] (q0) edge node [right, pos=0.2] {$b$} (q2); |
698 \path[->] (q0) edge node [right, pos=0.2] {\alert{$b$}} (q2); |
739 \path[->] (q1) edge [loop above] node {$a$} (); |
699 \path[->] (q1) edge [loop above] node {\alert{$a$}} (); |
740 \path[->] (q1) edge node [above] {$b$} (qn); |
700 \path[->] (q1) edge node [above] {\alert{$b$}} (qn); |
741 \path[->] (q2) edge [loop right] node {$b$} (); |
701 \path[->] (q2) edge [loop right] node {\alert{$b$}} (); |
742 \path[->] (q2) edge node [below] {$a$} (qn); |
702 \path[->] (q2) edge node [below] {\alert{$a$}} (qn); |
743 \path[->] (qn) edge [loop above] node {$a,b$} (); |
703 \path[->] (qn) edge [loop above] node {$\alert{a},\alert{b}$} (); |
744 \end{tikzpicture} |
704 \end{tikzpicture} |
745 \end{center} |
705 \end{center} |
746 |
706 |
747 |
707 |
748 \end{frame} |
708 \end{frame} |
820 \item Mark all pairs that accepting and non-accepting states |
780 \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 |
781 \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether |
822 \begin{center} |
782 \begin{center} |
823 \bl{$(\delta(q, c), \delta(p,c))$} |
783 \bl{$(\delta(q, c), \delta(p,c))$} |
824 \end{center} |
784 \end{center} |
825 are marked. If yes, then also mark \bl{$(q, p)$}. |
785 are marked. If yes in at least one case, then also mark \bl{$(q, p)$}. |
826 \item Repeat last step until no change. |
786 \item Repeat last step until no change. |
827 \item All unmarked pairs can be merged. |
787 \item All unmarked pairs can be merged. |
828 \end{enumerate} |
788 \end{enumerate} |
829 |
789 |
830 \end{frame} |
790 \end{frame} |