1 \documentclass{article} |
|
2 \usepackage{charter} |
|
3 \usepackage{hyperref} |
|
4 \usepackage{amssymb} |
|
5 \usepackage{amsmath} |
|
6 |
|
7 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
8 \begin{document} |
|
9 |
|
10 \section*{Proof} |
|
11 |
|
12 Recall the definitions for regular expressions and the language associated with a regular expression: |
|
13 |
|
14 \begin{center} |
|
15 \begin{tabular}{c} |
|
16 \begin{tabular}[t]{rcl} |
|
17 $r$ & $::=$ & $\varnothing$ \\ |
|
18 & $\mid$ & $\epsilon$ \\ |
|
19 & $\mid$ & $c$ \\ |
|
20 & $\mid$ & $r_1 \cdot r_2$ \\ |
|
21 & $\mid$ & $r_1 + r_2$ \\ |
|
22 & $\mid$ & $r^*$ \\ |
|
23 \end{tabular}\hspace{10mm} |
|
24 \begin{tabular}[t]{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
25 $L(\varnothing)$ & $\dn$ & $\varnothing$ \\ |
|
26 $L(\epsilon)$ & $\dn$ & $\{\texttt{""}\}$ \\ |
|
27 $L(c)$ & $\dn$ & $\{\texttt{"}c\texttt{"}\}$ \\ |
|
28 $L(r_1 \cdot r_2)$ & $\dn$ & $L(r_1) \,@\, L(r_2)$ \\ |
|
29 $L(r_1 + r_2)$ & $\dn$ & $L(r_1) \cup L(r_2)$ \\ |
|
30 $L(r^*)$ & $\dn$ & $\bigcup_{n\ge 0} L(r)^n$ \\ |
|
31 \end{tabular} |
|
32 \end{tabular} |
|
33 \end{center} |
|
34 |
|
35 \noindent |
|
36 We also defined the notion of a derivative of a regular expression (the derivative with respect to a character): |
|
37 |
|
38 \begin{center} |
|
39 \begin{tabular}{lcl} |
|
40 $der\, c\, (\varnothing)$ & $\dn$ & $\varnothing$ \\ |
|
41 $der\, c\, (\epsilon)$ & $\dn$ & $\varnothing$ \\ |
|
42 $der\, c\, (d)$ & $\dn$ & if $c = d$ then $\epsilon$ else $\varnothing$\\ |
|
43 $der\, c\, (r_1 + r_2)$ & $\dn$ & $(der\, c\, r_1) + (der\, c\, r_2)$ \\ |
|
44 $der\, c\, (r_1 \cdot r_2)$ & $\dn$ & if $nullable(r_1)$\\ |
|
45 & & then $((der\, c\, r_1) \cdot r_2) + (der\, c\, r_2)$\\ |
|
46 & & else $(der\, c\, r_1) \cdot r_2$\\ |
|
47 $der\, c\, (r^*)$ & $\dn$ & $(der\, c\, r) \cdot (r^*)$\\ |
|
48 \end{tabular} |
|
49 \end{center} |
|
50 |
|
51 \noindent |
|
52 With our definition of regular expressions comes an induction principle. Given a property $P$ over |
|
53 regular expressions. We can establish that $\forall r.\; P(r)$ holds, provided we can show the following: |
|
54 |
|
55 \begin{enumerate} |
|
56 \item $P(\varnothing)$, $P(\epsilon)$ and $P(c)$ all hold, |
|
57 \item $P(r_1 + r_2)$ holds under the induction hypotheses that |
|
58 $P(r_1)$ and $P(r_2)$ hold, |
|
59 \item $P(r_1 \cdot r_2)$ holds under the induction hypotheses that |
|
60 $P(r_1)$ and $P(r_2)$ hold, and |
|
61 \item $P(r^*)$ holds under the induction hypothesis that $P(r)$ holds. |
|
62 \end{enumerate} |
|
63 |
|
64 \noindent |
|
65 Let us try out an induction proof. Recall the definition |
|
66 |
|
67 \begin{center} |
|
68 $Der\, c\, A \dn \{ s\;\mid\; c\!::\!s \in A\}$ |
|
69 \end{center} |
|
70 |
|
71 \noindent |
|
72 whereby $A$ is a set of strings. We like to prove |
|
73 |
|
74 \begin{center} |
|
75 \begin{tabular}{l} |
|
76 $P(r) \dn $ \hspace{4mm} $L(der\,c\,r) = Der\,c\,(L(r))$ |
|
77 \end{tabular} |
|
78 \end{center} |
|
79 |
|
80 \noindent |
|
81 by induction over the regular expression $r$. |
|
82 |
|
83 |
|
84 \newpage |
|
85 \noindent |
|
86 {\bf Proof} |
|
87 |
|
88 \noindent |
|
89 According to 1.~above we need to prove $P(\varnothing)$, $P(\epsilon)$ and $P(d)$. Lets do this in turn. |
|
90 |
|
91 \begin{itemize} |
|
92 \item First Case: $P(\varnothing)$ is $L(der\,c\,\varnothing) = Der\,c\,(L(\varnothing))$ (a). We have $der\,c\,\varnothing = \varnothing$ |
|
93 and $L(\varnothing) = \varnothing$. We also have $Der\,c\,\varnothing = \varnothing$. Hence we have $\varnothing = \varnothing$ in (a). |
|
94 |
|
95 \item Second Case: $P(\epsilon)$ is $L(der\,c\,\epsilon) = Der\,c\,(L(\epsilon))$ (b). We have $der\,c\,\epsilon = \varnothing$, |
|
96 $L(\varnothing) = \varnothing$ and $L(\epsilon) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \varnothing$. Hence we have |
|
97 $\varnothing = \varnothing$ in (b). |
|
98 |
|
99 \item Third Case: $P(d)$ is $L(der\,c\,d) = Der\,c\,(L(d))$ (c). We need to treat the cases $d = c$ and $d \not= c$. |
|
100 |
|
101 $d = c$: We have $der\,c\,c = \epsilon$ and $L(\epsilon) = \{\texttt{""}\}$. |
|
102 We also have $L(c) = \{\texttt{"}c\texttt{"}\}$ and $Der\,c\,\{\texttt{"}c\texttt{"}\} = \{\texttt{""}\}$. Hence we have |
|
103 $\{\texttt{""}\} = \{\texttt{""}\}$ in (c). |
|
104 |
|
105 $d \not=c$: We have $der\,c\,d = \varnothing$. |
|
106 We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \varnothing$. Hence we have |
|
107 $\varnothing = \varnothing$ in (c). |
|
108 \end{itemize} |
|
109 |
|
110 \noindent |
|
111 These were the easy base cases. Now come the inductive cases. |
|
112 |
|
113 \begin{itemize} |
|
114 \item Fourth Case: $P(r_1 + r_2)$ is $L(der\,c\,(r_1 + r_2)) = Der\,c\,(L(r_1 + r_2))$ (d). This is what we have to show. |
|
115 We can assume already: |
|
116 |
|
117 \begin{center} |
|
118 \begin{tabular}{ll} |
|
119 $P(r_1)$: & $L(der\,c\,r_1) = Der\,c\,(L(r_1))$ (I)\\ |
|
120 $P(r_2)$: & $L(der\,c\,r_2) = Der\,c\,(L(r_2))$ (II) |
|
121 \end{tabular} |
|
122 \end{center} |
|
123 |
|
124 We have that $der\,c\,(r_1 + r_2) = (der\,c\,r_1) + (der\,c\,r_2)$ and also $L((der\,c\,r_1) + (der\,c\,r_2)) = L(der\,c\,r_1) \cup L(der\,c\,r_2)$. |
|
125 By (I) and (II) we know that the left-hand side is $Der\,c\,(L(r_1)) \cup Der\,c\,(L(r_2))$. You need to ponder a bit, but you should see |
|
126 that |
|
127 |
|
128 \begin{center} |
|
129 $Der\,c(A \cup B) = (Der\,c\,A) \cup (Der\,c\,B)$ |
|
130 \end{center} |
|
131 |
|
132 holds for every set of strings $A$ and $B$. That means the right-hand side of (d) is also $Der\,c\,(L(r_1)) \cup Der\,c\,(L(r_2))$, |
|
133 because $L(r_1 + r_2) = L(r_1) \cup L(r_2)$. And we are done with the fourth case. |
|
134 |
|
135 \item Fifth Case: $P(r_1 \cdot r_2)$ is $L(der\,c\,(r_1 \cdot r_2)) = Der\,c\,(L(r_1 \cdot r_2))$ (e). We can assume already: |
|
136 |
|
137 \begin{center} |
|
138 \begin{tabular}{ll} |
|
139 $P(r_1)$: & $L(der\,c\,r_1) = Der\,c\,(L(r_1))$ (I)\\ |
|
140 $P(r_2)$: & $L(der\,c\,r_2) = Der\,c\,(L(r_2))$ (II) |
|
141 \end{tabular} |
|
142 \end{center} |
|
143 |
|
144 Let us first consider the case where $nullable(r_1)$ holds. Then |
|
145 |
|
146 \[ |
|
147 der\,c\,(r_1 \cdot r_2) = ((der\,c\,r_1) \cdot r_2) + (der\,c\,r_2). |
|
148 \] |
|
149 |
|
150 The corresponding language of the right-hand side is |
|
151 |
|
152 \[ |
|
153 (L(der\,c\,r_1) \,@\, L(r_2)) \cup L(der\,c\,r_2). |
|
154 \] |
|
155 |
|
156 By the induction hypotheses (I) and (II), this is equal to |
|
157 |
|
158 \[ |
|
159 (Der\,c\,(L(r_1)) \,@\, L(r_2)) \cup (Der\,c\,(L(r_2)).\;\;(**) |
|
160 \] |
|
161 |
|
162 We also know that $L(r_1 \cdot r_2) = L(r_1) \,@\,L(r_2)$. We have to know what |
|
163 $Der\,c\,(L(r_1) \,@\,L(r_2))$ is. |
|
164 |
|
165 Let us analyse what |
|
166 $Der\,c\,(A \,@\, B)$ is for arbitrary sets of strings $A$ and $B$. If $A$ does \emph{not} |
|
167 contain the empty string, then every string in $A\,@\,B$ is of the form $s_1 \,@\, s_2$ where |
|
168 $s_1 \in A$ and $s_2 \in B$. So if $s_1$ starts with $c$ then we just have to remove it. Consequently, |
|
169 $Der\,c\,(A \,@\, B) = (Der\,c\,(A)) \,@\, B$. This case does not apply here though, because we already |
|
170 proved that if $r_1$ is nullable, then $L(r_1)$ contains the empty string. In this case, every string |
|
171 in $A\,@\,B$ is either of the form $s_1 \,@\, s_2$, with $s_1 \in A$ and $s_2 \in B$, or |
|
172 $s_3$ with $s_3 \in B$. This means $Der\,c\,(A \,@\, B) = ((Der\,c\,(A)) \,@\, B) \cup Der\,c\,B$. |
|
173 But this proves that (**) is $Der\,c\,(L(r_1) \,@\, L(r_2))$. |
|
174 |
|
175 Similarly in the case where $r_1$ is \emph{not} nullable. |
|
176 |
|
177 \item Sixth Case: $P(r^*)$ is $L(der\,c\,(r^*)) = Der\,c\,L(r^*)$. We can assume already: |
|
178 |
|
179 \begin{center} |
|
180 \begin{tabular}{ll} |
|
181 $P(r)$: & $L(der\,c\,r) = Der\,c\,(L(r))$ (I) |
|
182 \end{tabular} |
|
183 \end{center} |
|
184 |
|
185 We have $der\,c\,(r^*) = der\,c\,r\cdot r^*$. Which means $L(der\,c\,(r^*)) = L(der\,c\,r\cdot r^*)$ and |
|
186 further $L(der\,c\,r) \,@\, L(r^*)$. By induction hypothesis (I) we know that is equal to |
|
187 $(Der\,c\,L(r)) \,@\, L(r^*)$. (*) |
|
188 |
|
189 \end{itemize} |
|
190 |
|
191 |
|
192 |
|
193 |
|
194 Let us now analyse $Der\,c\,L(r^*)$, which is equal to $Der\,c\,((L(r))^*)$. Now $(L(r))^*$ is defined |
|
195 as $\bigcup_{n \ge 0} L(r)$. We can write this as $L(r)^0 \cup \bigcup_{n \ge 1} L(r)$, where we just |
|
196 separated the first union and then let the ``big-union'' start from $1$. Form this we can already infer |
|
197 |
|
198 \begin{center} |
|
199 $Der\,c\,(L(r^*)) = Der\,c\,(L(r)^0 \cup \bigcup_{n \ge 1} L(r)) = (Der\,c\,L(r)^0) \cup Der\,c\,(\bigcup_{n \ge 1} L(r))$ |
|
200 \end{center} |
|
201 |
|
202 The first union ``disappears'' since $Der\,c\,(L(r)^0) = \varnothing$. |
|
203 |
|
204 |
|
205 \end{document} |
|
206 |
|
207 %%% Local Variables: |
|
208 %%% mode: latex |
|
209 %%% TeX-master: t |
|
210 %%% End: |
|