Talk:Kleene's algorithm

Simplifications

@Dylanmorroll: Many thanks for your simplifications. In fact, your result for R²
₀₁ coincides with the expression I obtained intuitively from the automaton picture, cf. File:Deterministicfiniteautomaton.svg#Summary. I'm not sure your proofs should be shown in the article (it might depend on their length), but I'd be personally interested to see them. In particular, I wonder whether they needed some intuition or whether they were possible by mechanizable application of simplification rules. Would it be possible for you to upload the proofs (a jpg of a handwritten version might be achievable with least effort, I guess)? Thanks in advance. Best regards - Jochen Burghardt (talk) 15:25, 30 April 2018 (UTC)

@Jochen Burghardt: Sorry for the late reply I completely forgot about this till I saw an old email. Sure thing - I actually achieved these through a program I created for my final year university project so it is in fact achievable by a mechanised application of rules! Here is my working:

Simplify: a*b*ba((a|b)b*a|\e)*(a|b)b*|a*b*b s: a*b*ba((a|b)b*a|\e)*(a|b)b*|a*b*b

applied (a|ε)* = (a)*

e: a*b*ba((a|b)b*a)*(a|b)b*|a*b*b

s: a*b*ba((a|b)b*a)*(a|b)b*|a*b*b

no simplification rules applied

e: a*b*ba((a|b)b*a)*(a|b)b*|a*b*b

applied reverse sort stars

m: a*bb*a(a|b)b*(a(a|b)b*)*|a*bb*

s: a*bb*a(a|b)b*(a(a|b)b*)*|a*bb*

no simplification rules applied

e: a*bb*a(a|b)b*(a(a|b)b*)*|a*bb*

applied sort stars

m: a*b*b(a(a|b)b*)*a(a|b)b*|a*b*b

s: a*b*b(a(a|b)b*)*a(a|b)b*|a*b*b

applied a*aa|a = a*a

e: a*b*b(a(a|b)b*)*

s: a*b*b(a(a|b)b*)*

no simplification rules applied

e: a*b*b(a(a|b)b*)*

applied reverse sort stars

m: a*bb*(a(a|b)b*)*

s: a*bb*(a(a|b)b*)*

no simplification rules applied

e: a*bb*(a(a|b)b*)*

applied sort stars

m: a*b*b(a(a|b)b*)*

s: a*b*b(a(a|b)b*)*

no simplification rules applied

e: a*b*b(a(a|b)b*)*

applied a*(ba*)* = (a|b)*

applied add all alternations

m: a*b(b|a(a|b))*

s: a*b(b|a(a|b))*

no simplification rules applied

e: a*b(b|a(a|b))*

applied reverse sort stars

m: a*b(b|a(a|b))*

s: a*b(b|a(a|b))*

no simplification rules applied

e: a*b(b|a(a|b))*

applied sort stars

m: a*b(b|a(a|b))*

s: a*b(b|a(a|b))*

no simplification rules applied

e: a*b(b|a(a|b))*

applied add all alternations

m: a*b(b|a(a|b))*

no rules applied - end of simplification

e: a*b(b|a(a|b))*

Here I start with a regular expression and try and apply a list of simplification rules. If none apply I then sort all stars to the end of the list of characters it applies to (i.e. aa*a becomes aaa*). If no rules apply still I then sort all stars to the beginning of their respective characters (i.e. aaa* now becomes a*aa). If no rules apply I then add any alternations back in so a*(ba*)* becomes (a|b)*. This process repeats until no rules apply! I wrote a dissertation on the project if you're interested - here is a link to view it online: https://1drv.ms/b/s!AtDZ8Q45oumTgtc9M_TSs2Fzyr5EgA

All the best, Dylan Dylanmorroll (talk) 11:30, 21 February 2019 (UTC)