306 The good things about $\mathit{DFA}$s is that once |
306 The good things about $\mathit{DFA}$s is that once |
307 generated, they are fast and stable, unlike |
307 generated, they are fast and stable, unlike |
308 backtracking algorithms. |
308 backtracking algorithms. |
309 However, they do not scale well with bounded repetitions.\\ |
309 However, they do not scale well with bounded repetitions.\\ |
310 |
310 |
|
311 |
|
312 \begin{center} |
|
313 \begin{tabular}{@{}c@{\hspace{0mm}}c@{\hspace{0mm}}c@{}} |
|
314 \begin{tikzpicture} |
|
315 \begin{axis}[ |
|
316 ymode=log, |
|
317 xlabel={$n$}, |
|
318 x label style={at={(1.05,-0.05)}}, |
|
319 ylabel={time in secs}, |
|
320 enlargelimits=false, |
|
321 xtick={1,2,...,8}, |
|
322 xmax=9, |
|
323 ymax=16000000, |
|
324 ytick={0,500,...,3500}, |
|
325 scaled ticks=false, |
|
326 axis lines=left, |
|
327 width=5cm, |
|
328 height=4cm, |
|
329 legend entries={JavaScript}, |
|
330 legend pos=north west, |
|
331 legend cell align=left] |
|
332 \addplot[red,mark=*, mark options={fill=white}] table {re-chengsong.data}; |
|
333 \end{axis} |
|
334 \end{tikzpicture} |
|
335 \end{tabular} |
|
336 \end{center} |
|
337 |
|
338 Another graph: |
|
339 \begin{center} |
|
340 \begin{tikzpicture} |
|
341 \begin{axis}[ |
|
342 height=0.5\textwidth, |
|
343 width=\textwidth, |
|
344 xlabel=number of a's, |
|
345 xtick={0,...,9}, |
|
346 ylabel=maximum size, |
|
347 ymode=log, |
|
348 log basis y={2} |
|
349 ] |
|
350 \addplot[mark=*,blue] table {re-chengsong.data}; |
|
351 \end{axis} |
|
352 \end{tikzpicture} |
|
353 \end{center} |
|
354 |
|
355 |
|
356 |
|
357 |
311 Bounded repetitions, usually written in the form |
358 Bounded repetitions, usually written in the form |
312 $r^{\{c\}}$ (where $c$ is a constant natural number), |
359 $r^{\{c\}}$ (where $c$ is a constant natural number), |
313 denotes a regular expression accepting strings |
360 denotes a regular expression accepting strings |
314 that can be divided into $c$ substrings, where each |
361 that can be divided into $c$ substrings, where each |
315 substring is in $r$. |
362 substring is in $r$. |