← All problemsUnverified
How is a^* = 1/(1-a)?
Consider the language a∗. We have
a∗=ε+a+aa+aaa+…=1+a+a2+a3+… ,(since ε is the unit of concatenation)=k=0∑∞ak
in which we now immediately recognize the familiar \textbackslash{}textit{geometric series} whose closed form is well known to be 1−a1. In that sense,
a∗=1−a1 .
We have to be a bit careful as the above is actually a non-commutative division (since multiplication of words is non-commutative), so we write
b∣∣a forb1⋅aand∣b a∣fora⋅b1 ,
whereas b∣∣1 =∣b 1∣=b1 because ε⋅x=x⋅ε=x. Using our new insight -- "Kleene star is a fraction" --, we can now conveniently prove, for instance, the well-known identity a(ba)∗=(ab)∗a. While the standard proof is rather lengthy and involves several axioms of Kleene algebra, our proof fits on a beer coaster (it was actually devised on such, see picture below) and goes as follows:
a(ba)∗=∣1−ba a ∣=∣a1−b1∣(right-expand fraction by a1)=a1−b∣∣ 1 (by x∣∣1 =∣x 1∣)=1−ab∣∣ a (left-expand fraction by a)=(ab)∗a
There are "only" two problems with all of the above: neither …−a nor …1 make sense at the moment. Open Problem: How can we formally make sense of additive and multiplicative inverses on words, such that a∗=1+a+a2+…=1−a1, i.e.\textbackslash{} such that a∗⋅(1−a)=1?