← All problems
Unverified

How is a^* = 1/(1-a)?

Consider the language a∗a^*. We have

a∗=ε+a+aa+aaa+…=1+a+a2+a3+… ,(since ε is the unit of concatenation)=∑k=0∞ak\begin{aligned} a^* &{}= \varepsilon + a + aa + aaa + \ldots\\ &{}= 1 + a + a^2 + a^3 + \ldots~, \qquad\text{(since }\varepsilon\text{ is the unit of concatenation)}\\ &{}= \sum_{k = 0}^\infty a^k \end{aligned}

in which we now immediately recognize the familiar \textbackslash{}textit{geometric series} whose closed form is well known to be 11−a\frac{1}{1 - a}. In that sense,

a∗=11−a .\begin{aligned} a^* = \frac{1}{1 - a}~. \end{aligned}

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

∣ a  b ∣for1b⋅aand a ∣∣ b fora⋅1b ,\begin{aligned} \frac{ {|}\,a~}{~b\,{|}} \quad\text{for}\quad \frac{1}{b} \cdot a \qquad\text{and}\qquad \frac{~a\,{|}}{ {|}\,b~} \quad\text{for}\quad{} a \cdot \frac{1}{b}~, \end{aligned}

whereas ∣ 1  b ∣= 1 ∣∣ b =1b\frac{ {|}\,1~}{~b\,{|}} = \frac{~1\,{|}}{ {|}\,b~} = \frac{1}{b} because ε⋅x=x⋅ε=x\varepsilon \cdot x = x \cdot \varepsilon = x. Using our new insight -- "Kleene star is a fraction" --, we can now conveniently prove, for instance, the well-known identity a(ba)∗=(ab)∗aa(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)∗= a ∣∣ 1−ba=1∣∣ 1a−b(right-expand fraction by 1a)=∣ 1 1a−b ∣(by ∣ 1  x ∣= 1 ∣∣ x )=∣ a 1−ab ∣(left-expand fraction by a)=(ab)∗a\begin{aligned} a(ba)^* &{} = \frac{\quad{}~a~\quad{|}}{ {|}\,1 - ba}\\ &{} = \frac{\quad{}1\quad{|}}{ {|}\,\frac{1}{a} - b} \qquad\text{(right-expand fraction by }\frac{1}{a}\text{)}\\ &{} = \frac{ {|}\quad{}~1~\quad}{\frac{1}{a} - b\,{|}} \qquad\text{(by }\frac{ {|}\,1~}{~x\,{|}} = \frac{~1\,{|}}{ {|}\,x~}\text{)}\\ &{} = \frac{ {|}\quad{}~a~\quad}{1 - ab\,{|}} \qquad\text{(left-expand fraction by }a\text{)}\\ &{} =(ab)^*a \end{aligned}

There are "only" two problems with all of the above: neither …−a{\ldots} - a nor 1…\tfrac{1}{\ldots} 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+…=11−aa^* = 1 + a + a^2 + {\dots} = \frac{1}{1 - a}, i.e.\textbackslash{} such that a∗⋅(1−a)=1a^* \cdot (1 - a) = 1?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu