equal
deleted
inserted
replaced
812 case STAR(r1) => NFA_STAR(thompson(r1)) |
812 case STAR(r1) => NFA_STAR(thompson(r1)) |
813 } |
813 } |
814 \end{lstlisting}} |
814 \end{lstlisting}} |
815 |
815 |
816 \noindent |
816 \noindent |
817 It calculates a NFA from a regular expressions. At last we can run |
817 It calculates a NFA from a regular expression. At last we can run |
818 NFAs for the our evil regular expression examples. The graph on the |
818 NFAs for our evil regular expression examples. The graph on the |
819 left shows that when translating a regular expression such as |
819 left shows that when translating a regular expression such as |
820 $a^{?\{n\}} \cdot a^{\{n\}}$ into a NFA, the size can blow up and then |
820 $a^{?\{n\}} \cdot a^{\{n\}}$ into a NFA, the size can blow up and then |
821 even the relative fast (on small examples) breadth-first search can be |
821 even the relative fast (on small examples) breadth-first search can be |
822 slow\ldots the red line maxes out at about 15 $n$s. |
822 slow\ldots the red line maxes out at about 15 $n$s. |
823 |
823 |