Content deleted Content added
→Simplifications: new section |
→Kleene's theorem: Reply |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=Start|
{{WikiProject Mathematics|importance=low}}
}}
== Simplifications ==
{{ping|Dylanmorroll}} Many thanks for your simplifications. In fact, your result for ''R''{{su|p=2|b=''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 - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 15:25, 30 April 2018 (UTC)
{{ping|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
[[User:Dylanmorroll|Dylanmorroll]] ([[User talk:Dylanmorroll|talk]]) 11:30, 21 February 2019 (UTC)
== Kleene's theorem ==
Does this page describe the construction used to prove [[Kleene's theorem]] (thus perhaps that link should be redirected here)? [[User:Tule-hog|Tule-hog]] ([[User talk:Tule-hog|talk]]) 21:06, 8 December 2024 (UTC)
:Provided that [[Regular_language#Equivalent_formalisms]] is right, Kleene's theorem state the equivalence of regular expressions and nondeterministic finite automata (with variations depending on the textbook author). Kleene's algorithm is used for one direction of the equivalence proof, and [[Thompson's construction]] for the other one, cf. notess 1 and 2 in the enumeration of equivalent chracterizations of regular languages. Since [[Regular_language#Equivalent_formalisms]] presents both directions, I consider this page a more adequate target of the redirect [[Kleene's theorem]]. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 19:27, 9 December 2024 (UTC)
::Thanks for the clarification. Just in case I'm misunderstanding - 'this page' in your last sentence refers to [[Regular language]], right? [[User:Tule-hog|Tule-hog]] ([[User talk:Tule-hog|talk]]) 19:57, 9 December 2024 (UTC)
:::Yes, indeed. When I wrote my comment, I erroneously believed to be on [[Talk:Regular language]]. - Sorry for the confusion. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 21:15, 10 December 2024 (UTC)
| |||