Talk:Kleene's algorithm
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Simplifications
[edit]@Dylanmorroll: Many thanks for your simplifications. In fact, your result for R2
01 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)