84 \noindent |
84 \noindent |
85 According to 1.~above we need to prove $P(\ZERO)$, $P(\ONE)$ and $P(d)$. Lets do this in turn. |
85 According to 1.~above we need to prove $P(\ZERO)$, $P(\ONE)$ and $P(d)$. Lets do this in turn. |
86 |
86 |
87 \begin{itemize} |
87 \begin{itemize} |
88 \item First Case: $P(\ZERO)$ is $L(der\,c\,\ZERO) = Der\,c\,(L(\ZERO))$ (a). We have $der\,c\,\ZERO = \ZERO$ |
88 \item First Case: $P(\ZERO)$ is $L(der\,c\,\ZERO) = Der\,c\,(L(\ZERO))$ (a). We have $der\,c\,\ZERO = \ZERO$ |
89 and $L(\ZERO) = \ZERO$. We also have $Der\,c\,\ZERO = \ZERO$. Hence we have $\ZERO = \ZERO$ in (a). |
89 and $L(\ZERO) = \emptyset$. We also have $Der\,c\,L(\ZERO) = L(\ZERO$). Hence we have $\emptyset = \emptyset$ in (a). |
90 |
90 |
91 \item Second Case: $P(\ONE)$ is $L(der\,c\,\ONE) = Der\,c\,(L(\ONE))$ (b). We have $der\,c\,\ONE = \ZERO$, |
91 \item Second Case: $P(\ONE)$ is $L(der\,c\,\ONE) = Der\,c\,(L(\ONE))$ (b). We have $der\,c\,\ONE = \ZERO$, |
92 $L(\ZERO) = \ZERO$ and $L(\ONE) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \ZERO$. Hence we have |
92 $L(\ZERO) = \ZERO$ and $L(\ONE) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \emptyset$. Hence we have |
93 $\ZERO = \ZERO$ in (b). |
93 $\emptyset = \emptyset$ in (b). |
94 |
94 |
95 \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$. |
95 \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$. |
96 |
96 |
97 $d = c$: We have $der\,c\,c = \ONE$ and $L(\ONE) = \{\texttt{""}\}$. |
97 $d = c$: We have $der\,c\,c = \ONE$ and $L(\ONE) = \{\texttt{""}\}$. |
98 We also have $L(c) = \{\texttt{"}c\texttt{"}\}$ and $Der\,c\,\{\texttt{"}c\texttt{"}\} = \{\texttt{""}\}$. Hence we have |
98 We also have $L(c) = \{\texttt{"}c\texttt{"}\}$ and $Der\,c\,\{\texttt{"}c\texttt{"}\} = \{\texttt{""}\}$. Hence we have |
99 $\{\texttt{""}\} = \{\texttt{""}\}$ in (c). |
99 $\{\texttt{""}\} = \{\texttt{""}\}$ in (c). |
100 |
100 |
101 $d \not=c$: We have $der\,c\,d = \ZERO$. |
101 $d \not=c$: We have $der\,c\,d = \ZERO$. |
102 We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \ZERO$. Hence we have |
102 We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \emptyset$. Hence we have |
103 $\ZERO = \ZERO$ in (c). |
103 $\emptyset = \emptyset$ in (c). |
104 \end{itemize} |
104 \end{itemize} |
105 |
105 |
106 \noindent |
106 \noindent |
107 These were the easy base cases. Now come the inductive cases. |
107 These were the easy base cases. Now come the inductive cases. |
108 |
108 |
190 |
190 |
191 \begin{center} |
191 \begin{center} |
192 $Der\,c\,(L(r^*)) = Der\,c\,(L(r)^0 \cup \bigcup_{n \ge 1} L(r)^n) = (Der\,c\,L(r)^0) \cup Der\,c\,(\bigcup_{n \ge 1} L(r)^n)$ |
192 $Der\,c\,(L(r^*)) = Der\,c\,(L(r)^0 \cup \bigcup_{n \ge 1} L(r)^n) = (Der\,c\,L(r)^0) \cup Der\,c\,(\bigcup_{n \ge 1} L(r)^n)$ |
193 \end{center} |
193 \end{center} |
194 |
194 |
195 The first union ``disappears'' since $Der\,c\,(L(r)^0) = \ZERO$. |
195 The first union ``disappears'' since $Der\,c\,(L(r)^0) = \emptyset$. |
196 |
196 |
197 |
197 |
198 \end{document} |
198 \end{document} |
199 |
199 |
200 %%% Local Variables: |
200 %%% Local Variables: |