正則言語について調べていたら，Arden's ruleというものを見つけたのでメモ．

Arden's rule

$\Sigma$ をアルファベットの集合とし，$A, B\subset \Sigma^{\ast}$ とする．方程式

X=A+BX

を考える．
$(1)$ $\varepsilon \not\in B$ なら，解は $X_0:=B^{\ast}A$ のみ．
$(2)$ $\varepsilon \in B$ なら，解は$A \subset \tilde{A} \subset \Sigma^{\ast}$ なる $\tilde{A}$ を用いて $B^{\ast}\tilde{A}$ と書ける．特に，解のうち（包含関係 $\subset$ について）最小のものは $X_0$ である．

証明
$X_0$ が解であることは

\begin{align}
A+BX_0
&=A+B(B^{\ast}A)\\
&=A+B^{+}A\\
&=(\varepsilon+B^{+})A\\
&=B^{\ast}A
=X_0
\end{align}

となることから従う．
$(1)$ 一意性を示せば良い．任意の$n \in \mathbb{N}$ に対し

\begin{align}
X
&=A+BX
=A+B(A+BX)\\
&=A+BA+B^{2}X\\
&=\cdots \\
&=\sum_{k=0}^{n}B^{k}A+B^{n+1}X
\end{align}

である．
今 $n \in \mathbb{N}$ を任意に固定する．$|w|=n$ となる $w \in X$ を任意に取ると，$\varepsilon \not \in B$ より任意の $B^{n+1}X$ の元の長さは $n+1$ 以上であるから，$w \in \sum_{k=0}^{n}B^{k}A \subset X_0.$ $n$は任意だから $X \subset X_0.$
逆の包含関係を示す．$w \in X_0$ とすると $X_0$ の定義から，$n \in \mathbb{N}$ があって $w \in \sum_{k=0}^{n}B^{k}A$ となるが，

\sum_{k=0}^{n}B^{k}A
\subset \sum_{k=0}^{n}B^{k}A + B^{n+1}X
=X

だから $w \in X.$ よって $X_0 \subset X.$
$(2)$ まず $X_0$ が最小の解であることを示す．$X$ を任意の解とする．$w \in X$ に対し $Bw \subset BX \subset A+BX =X$ だから，任意の $Y \subset X$ に対し $BY \subset X$ となる． 特に $BX \subset X.$ 帰納的に $B^{k}X \subset X$ となるので $B^{\ast}X \subset X.$ これと $A \subset A+BX=X$ より

X_0
=B^{\ast}A
\subset B^{\ast}X
\subset X.

よって $X_0$ が最小の解である．
これにより，任意の解は $X=X_0+Y \ (Y\subset \Sigma^{\ast})$ と書けるので，$Y$ は $Y=BY$ を満たす．従って $Y_0 \subset \Sigma^{\ast}$ を任意として $Y=B^{\ast}Y_0.$ よって $\tilde{A}=A+Y_0$ とおけば

X
=X_0+Y
=B^{\ast}A+B^{\ast}Y_0
=B^{\ast}(A+Y_0)
=B^{\ast}\tilde{A}.