618 |
618 |
619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
620 \begin{frame}[c] |
620 \begin{frame}[c] |
621 \frametitle{Mkeps} |
621 \frametitle{Mkeps} |
622 |
622 |
623 Finding a (posix) value for recognising the empty string |
623 Finding a (posix) value for recognising the empty string: |
624 |
624 |
625 \begin{center} |
625 \begin{center} |
626 \begin{tabular}{lcl} |
626 \begin{tabular}{lcl} |
627 \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\ |
627 \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\ |
628 \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
628 \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
670 \end{tabular} |
670 \end{tabular} |
671 \end{center} |
671 \end{center} |
672 |
672 |
673 \footnotesize |
673 \footnotesize |
674 \bl{$lex$}: returns a value |
674 \bl{$lex$}: returns a value |
|
675 |
|
676 \begin{center} |
|
677 \begin{tikzpicture}[scale=2,node distance=1.0cm,every node/.style={minimum size=6mm}] |
|
678 \node (r1) {\bl{$r_1$}}; |
|
679 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
680 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
681 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
682 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
683 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
684 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
685 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
686 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
687 \draw[->,line width=1mm] (r4) -- (v4); |
|
688 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
689 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
690 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
691 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
692 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
693 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
694 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
695 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
696 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
697 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
698 \end{tikzpicture} |
|
699 \end{center} |
|
700 |
675 \end{frame} |
701 \end{frame} |
676 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
677 |
703 |
678 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
704 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
679 \begin{frame}[c] |
705 \begin{frame}[c] |
717 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
743 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
718 \begin{frame}[c] |
744 \begin{frame}[c] |
719 \frametitle{Simplification} |
745 \frametitle{Simplification} |
720 |
746 |
721 \begin{itemize} |
747 \begin{itemize} |
722 \item If we simplify after the derivative, then we ar builing the |
748 \item If we simplify after the derivative, then we are builing the |
723 value for the simplified regular expression, but \emph{not} for the original |
749 value for the simplified regular expression, but \emph{not} for the original |
724 regular expression. |
750 regular expression. |
725 \end{itemize} |
751 \end{itemize} |
726 |
752 |
727 \begin{center} |
753 \begin{center} |