# $B_{3}$ is automatic, a simple proof

$B_{3}$ is particularly nice to analyze due to the uniqueness of the Garside normal form.

The Garside normal form is unique in $B_{3}$, and is in the form $Δ_{m}σ_{a_{1}}…σ_{a_{k}}$, such that $a_{i}=a_{i+1}$, $e_{1},e_{k}≥1$ and $e_{2},…,e_{k−1}≥2$.

For any word $w∈B_{n}$, the Garside normal form $Δ_{m}p$ is unique up to elements $p$ in $B_{n}$ and $p$ does not have a factor of $Δ$. Now we show that there is only one way to write $p$.

Every $p$ must be in this form. If for some $k>i>1$, $e_{i}=1$, then $a_{i−1}a_{i}a_{i+1}=a_{i−1}Δa_{i+1}$, which is a contradiction because $p$ doesn’t have a factor of $Δ$.

Every word in that form is also in $B_{n}$, and without $Δ$ factor.

It’s impossible to rewrite any word in this form with the relations $σ_{1}σ_{2}σ_{1}=σ_{2}σ_{1}σ_{2}$. Therefore this form is unique.

The Garside normal form of $B_{3}$ is regular.

Let $A={Δ,Δ_{−1},σ_{1},σ_{2}}$, then $A$ generates $G$. The Garside normal form is a regular language over $A$ because they exist an explicit regular expression $R$ that matches it.

$R=(Δ_{∗}∪(Δ_{−1∗}))(X∪X_{′})$ where $X=σ_{1}(σ_{2}σ_{2}σ_{2}σ_{1}σ_{1}σ_{1})_{∗}((σ_{2}σ_{2}σ_{2}σ_{1})∪σ_{2}))$ and $X_{′}$ is the same except the $σ_{2}$ and $σ_{1}$ are switched.

Let $W$ be a FSA generated by the regular expression $R$.

$M_{ϵ}$ exists, because the Garside normal form is unique, then $M_{ϵ}$ accepts all language of the form ${(w,w)∣w∈L(W)}$. It have the complete same structure as $W$, but replacing every edge $x$ with $(x,x)$.

Instead of construct $M_{x}$ directly, we only need to prove the fellow traveler property is true. This can be done by checking it is true for every $M_{x}$ independently.

Define $R(σ_{a_{1}}…σ_{a_{k}})=σ_{3−a_{1}}…σ_{3−a_{k}}$.

Note that every generator has a constant distance from another generator.

Consider $x$ case by case:

- $Δ$: The words differ in 1 $Δ$ are $Δ_{m}p$ and $Δ_{m+1}R(p)$.Assume $m$ is non-negative. At time $∣m∣+1$, one encounters $Δ_{m}σ_{a_{1}}$ and $Δ_{m+1}$, which has a distance of $2$. At time $∣m∣+2$, $Δ_{m}σ_{a_{1}}σ_{a_{2}}$ and $Δ_{m+1}σ_{3−a_{1}}=Δ_{m}σ_{a_{1}}Δ$, which also has distance 2. By induction, the distance is 2 till the end, where one has $Δ_{m}σ_{a_{1}}…σ_{a_{k}}$ and $Δ_{m}σ_{a_{1}}…σ_{a_{k−1}}Δ$. With one more step, it decrease the distance to $1$. When $m$ is negative, it’s similar.
- $Δ_{−1}$: Similar to $Δ$ case.
- $σ_{1}$: There are two cases. If the word end with $σ_{1}$, or end with $σ_{2}$, where $b≥2$, then the two words are exactly the same until the end. Thus implies the fellow traveler property. If the word end with a single $σ_{2}$, then the words are $Δ_{m}pσ_{1}σ_{2}$ and $Δ_{m}pσ_{1}σ_{2}σ_{1}$. The second word in normal form is $Δ_{m+1}R(pσ_{1})$. Note the first word is $Δ_{m}pσ_{1}⋅σ_{1}σ_{2}$ We can use the fact that adding the $Δ$ have fellow traveler property to prove this also have that property.
- $σ_{2}$: Similar to $σ_{2}$ case.

The fellow traveler property is true for each generator.

We now have the theorem

$B_{3}$ is automatic.