Proving formula for derivative of Kleene star

Question

Prove that for any symbol $a$ and regular expression $r$ it is true that:

$$\partial a(r^* ) = \partial .a(r)(r^* )$$

My attempt:

Induction on regular expression $r$

Base cases:

1) $\emptyset $

$\partial a(\emptyset^* ) = \partial a(\varepsilon) = \emptyset$

$\partial a(\emptyset) (\emptyset^* ) = \emptyset \emptyset^* = \emptyset \varepsilon = \emptyset$

2) $\varepsilon $

$\partial a(\varepsilon^* ) = \partial a(\varepsilon)$ = $\emptyset$

$\partial a(\varepsilon) (\varepsilon^* ) = \emptyset \varepsilon^* = \emptyset \varepsilon = \emptyset$

3) $a\in\Sigma$

Case $a=b$:

$\partial a(a^* ) = $

$\partial a(a) (a^* ) = \varepsilon (a^*) = a^*$

Case $a \neq b$:

$\partial a(b^* ) = $

$\partial a(b) (b^* ) = \emptyset (b^*) = \emptyset$

But how to prove for Inductive Step when regular expression $r$ is:

1) Concatenation: $r=\alpha\beta$

2) Union: $r=\alpha + \beta$

3) Kleene Star: $r=\alpha^*$

Answer 1

Using structural induction seems like overkill, or, which is more likely in your case, overly formal in a way which complete obstructs what is going on.

Here is a simple proof that explains why $\partial_a(r^*) = \partial_a(r)r^*$. We consider two cases:

1. $\epsilon \notin L[r]$. This implies that $\partial_a(r^{n+1}) = \partial_a(r)r^n$. Since $\partial_a(\epsilon) = \emptyset$, we get $$ \partial_a(r^*) = \bigcup_{n \geq 0} \partial_a(r^n) = \bigcup_{n \geq 1} \partial_a(r)r^{n-1} = \partial_a(r) \bigcup_{n \geq 1} r^{n-1} = \partial_a(r) r^*. $$

2. $\epsilon \in L[r]$. Write $r = \epsilon + s$, where $\epsilon \notin L[s]$. Then $r^* = s^*$, and so using the preceding case applied to $s$, we get $$ \partial_a(r^*) = \partial_a(s^*) = \partial_a(s)s^* = \partial_a(r)r^*, $$ since $\partial_a(r) = \partial_a(\epsilon) \cup \partial_a(s) = \partial_a(s)$.

---

If you did want to use a proof by structural induction, then you would need to let us know what identities of the Brzozowski derivative and of regular expressions you are allowed to use.

For example, if you are allowed to use $\partial_a(L_1 \cup L_2) = \partial_a(L_1) \cup \partial_a(L_2)$, then you immediately get the inductive step for union.

As another example, for the base case $r = b$, you can use the fact that every word in $b^*$ is either empty or starts with a $b$, and consequently $\partial_a(b^*) = \emptyset$. Since also $\partial_a(b) = \emptyset$, you would deduce this base case. Perhaps the identities you are allowed to use can implement this argument.