|
1 % Chapter Template |
|
2 |
|
3 \chapter{Chapter Title Here} % Main chapter title |
|
4 |
|
5 \label{ChapterX} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX} |
|
6 |
|
7 %---------------------------------------------------------------------------------------- |
|
8 % SECTION 1 |
|
9 %---------------------------------------------------------------------------------------- |
|
10 |
|
11 \section{Properties of $\backslash c$} |
|
12 |
|
13 To have a clear idea of what we can and |
|
14 need to prove about the algorithms involving |
|
15 Brzozowski's derivatives, there are a few |
|
16 properties we need to be clear about |
|
17 it. |
|
18 \subsection{function $\backslash c$ is not 1-to-1} |
|
19 \begin{center} |
|
20 The derivative $w.r.t$ character $c$ is not one-to-one. |
|
21 Formally, |
|
22 $\exists r_1 \;r_2. r_1 \neq r_2 \mathit{and} r_1 \backslash c = r_2 \backslash c$ |
|
23 \end{center} |
|
24 This property is trivially true for the |
|
25 character regex example: |
|
26 \begin{center} |
|
27 $r_1 = e; \; r_2 = d;\; r_1 \backslash c = \ZERO = r_2 \backslash c$ |
|
28 \end{center} |
|
29 But apart from the cases where the derivative |
|
30 output is $\ZERO$, are there non-trivial results |
|
31 of derivatives which contain strings? |
|
32 The answer is yes. |
|
33 For example, |
|
34 \begin{center} |
|
35 Let $r_1 = a^*b\;\quad r_2 = (a\cdot a^*)\cdot b + b$.\\ |
|
36 where $a$ is not nullable.\\ |
|
37 $r_1 \backslash c = ((a \backslash c)\cdot a^*)\cdot c + b \backslash c$\\ |
|
38 $r_2 \backslash c = ((a \backslash c)\cdot a^*)\cdot c + b \backslash c$ |
|
39 \end{center} |
|
40 We start with two syntactically different regexes, |
|
41 and end up with the same derivative result, which is |
|
42 a "meaningful" regex because it contains strings. |
|
43 We have rediscovered Arden's lemma:\\ |
|
44 \begin{center} |
|
45 $A^*B = A\cdot A^* \cdot B + B$ |
|
46 \end{center} |
|
47 |
|
48 |
|
49 %----------------------------------- |
|
50 % SUBSECTION 1 |
|
51 %----------------------------------- |
|
52 \subsection{Subsection 1} |
|
53 |
|
54 Nunc posuere quam at lectus tristique eu ultrices augue venenatis. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Aliquam erat volutpat. Vivamus sodales tortor eget quam adipiscing in vulputate ante ullamcorper. Sed eros ante, lacinia et sollicitudin et, aliquam sit amet augue. In hac habitasse platea dictumst. |
|
55 |
|
56 %----------------------------------- |
|
57 % SUBSECTION 2 |
|
58 %----------------------------------- |
|
59 |
|
60 \subsection{Subsection 2} |
|
61 Morbi rutrum odio eget arcu adipiscing sodales. Aenean et purus a est pulvinar pellentesque. Cras in elit neque, quis varius elit. Phasellus fringilla, nibh eu tempus venenatis, dolor elit posuere quam, quis adipiscing urna leo nec orci. Sed nec nulla auctor odio aliquet consequat. Ut nec nulla in ante ullamcorper aliquam at sed dolor. Phasellus fermentum magna in augue gravida cursus. Cras sed pretium lorem. Pellentesque eget ornare odio. Proin accumsan, massa viverra cursus pharetra, ipsum nisi lobortis velit, a malesuada dolor lorem eu neque. |
|
62 |
|
63 %---------------------------------------------------------------------------------------- |
|
64 % SECTION 2 |
|
65 %---------------------------------------------------------------------------------------- |
|
66 |
|
67 \section{Main Section 2} |
|
68 |
|
69 Sed ullamcorper quam eu nisl interdum at interdum enim egestas. Aliquam placerat justo sed lectus lobortis ut porta nisl porttitor. Vestibulum mi dolor, lacinia molestie gravida at, tempus vitae ligula. Donec eget quam sapien, in viverra eros. Donec pellentesque justo a massa fringilla non vestibulum metus vestibulum. Vestibulum in orci quis felis tempor lacinia. Vivamus ornare ultrices facilisis. Ut hendrerit volutpat vulputate. Morbi condimentum venenatis augue, id porta ipsum vulputate in. Curabitur luctus tempus justo. Vestibulum risus lectus, adipiscing nec condimentum quis, condimentum nec nisl. Aliquam dictum sagittis velit sed iaculis. Morbi tristique augue sit amet nulla pulvinar id facilisis ligula mollis. Nam elit libero, tincidunt ut aliquam at, molestie in quam. Aenean rhoncus vehicula hendrerit. |