What are the proofs for properties of Derivates of Regular Expressions (Brzozowski) using induction or equivalences?
These are two exercises about Derivatives of Regular Expressions by Brzozowki Janusz.
- The first exercise is about proving using induction on regular expression r or equivalences that are in both articles attached (Owens and Brzozowski), the property of Derivative of Regular Expression r* (Kleene Star).
- The second exercise is about defining an equation for derivative of regular expression r^+, that is similar to r* but epsilon (empty symbol) is not included. And prove it using induction on Regular Expression r or equivalences that are in both articles attached (Owens and Brzozowski).
By induction on r, there are these cases where Regular Expression r is:
– For Base Case :
1) empty
2) epsilon
3) symbol ‘a’ that belongs to Sigma (alphabet)
– For Induction Step:
1) a.b (concatenation)
2) a+b (union)
3) a* (Kleene Star)