474 \item \bl{$(a^*)^*$} |
474 \item \bl{$(a^*)^*$} |
475 \item \bl{$([a$\,-\,$z]^+)^*$} |
475 \item \bl{$([a$\,-\,$z]^+)^*$} |
476 \item \bl{$(a + a \cdot a)^*$} |
476 \item \bl{$(a + a \cdot a)^*$} |
477 \item \bl{$(a + a?)^*$} |
477 \item \bl{$(a + a?)^*$} |
478 \end{itemize} |
478 \end{itemize} |
|
479 |
|
480 \item sometimes also called \alert{catastrophic backtracking} |
479 \end{itemize} |
481 \end{itemize} |
480 |
482 |
481 \end{frame} |
483 \end{frame} |
482 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
484 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
483 |
485 |
705 xtick={0,200,...,1100}, |
707 xtick={0,200,...,1100}, |
706 xmax=1200, |
708 xmax=1200, |
707 ytick={0,5,...,30}, |
709 ytick={0,5,...,30}, |
708 scaled ticks=false, |
710 scaled ticks=false, |
709 axis lines=left, |
711 axis lines=left, |
710 width=9.5cm, |
712 width=8cm, |
711 height=7cm, |
713 height=6.5cm, |
712 legend entries={Python,Ruby,Scala V1,Scala V2}, |
714 legend entries={Python,Ruby,Scala V1,Scala V2}, |
713 legend pos=north west, |
715 legend pos=outer north east, |
714 legend cell align=left |
716 legend cell align=left |
715 ] |
717 ] |
716 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
718 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
717 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
719 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
718 \addplot[red,mark=triangle*,mark options={fill=white}] table {re1.data}; |
720 \addplot[red,mark=triangle*,mark options={fill=white}] table {re1.data}; |
738 \bl{$\der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$} |
740 \bl{$\der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$} |
739 \end{tabular} |
741 \end{tabular} |
740 \end{center} |
742 \end{center} |
741 |
743 |
742 What are these regular expressions equivalent to? |
744 What are these regular expressions equivalent to? |
|
745 |
|
746 \end{frame} |
|
747 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
748 |
|
749 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
750 \begin{frame}[c] |
|
751 \frametitle{Simplifiaction} |
|
752 |
|
753 \begin{center} |
|
754 \bl{\begin{tabular}{rcl} |
|
755 $r + \ZERO$ & $\Rightarrow$ & $r$\\ |
|
756 $\ZERO + r$ & $\Rightarrow$ & $r$\\ |
|
757 $r \cdot \ONE$ & $\Rightarrow$ & $r$\\ |
|
758 $\ONE \cdot r$ & $\Rightarrow$ & $r$\\ |
|
759 $r \cdot \ZERO$ & $\Rightarrow$ & $\ZERO$\\ |
|
760 $\ZERO \cdot r$ & $\Rightarrow$ & $\ZERO$\\ |
|
761 $r + r$ & $\Rightarrow$ & $r$ |
|
762 \end{tabular}} |
|
763 \end{center} |
|
764 |
|
765 \footnotesize |
|
766 \lstinputlisting{../progs/app60.scala} |
|
767 \end{frame} |
|
768 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
769 |
|
770 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
771 \begin{frame}[c] |
|
772 |
|
773 \footnotesize |
|
774 \lstinputlisting{../progs/app6.scala} |
743 |
775 |
744 \end{frame} |
776 \end{frame} |
745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
777 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
746 |
778 |
747 |
779 |
806 \end{center} |
838 \end{center} |
807 |
839 |
808 \end{frame} |
840 \end{frame} |
809 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
841 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
810 |
842 |
|
843 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
844 \begin{frame}[c] |
|
845 \frametitle{\bl{$(a^*)^* \cdot b$}} |
|
846 |
|
847 \begin{center} |
|
848 \begin{tikzpicture} |
|
849 \begin{axis}[ |
|
850 xlabel={$n$}, |
|
851 x label style={at={(1.09,0.0)}}, |
|
852 ylabel={time in secs}, |
|
853 enlargelimits=false, |
|
854 ytick={0,5,...,20}, |
|
855 ymax=25, |
|
856 axis lines=left, |
|
857 width=9cm, |
|
858 height=5cm, |
|
859 legend entries={Scala V3}, |
|
860 legend pos=north west, |
|
861 legend cell align=left] |
|
862 \addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; |
|
863 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
|
864 \end{axis} |
|
865 \end{tikzpicture} |
|
866 \end{center} |
|
867 |
|
868 \end{frame} |
|
869 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
870 |
811 |
871 |
812 |
872 |
813 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
873 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
814 \begin{frame}[t] |
874 \begin{frame}[t] |
815 \frametitle{What is good about this Alg.} |
875 \frametitle{What is good about this Alg.} |