有限オートマトンの等価性
2つの有限オートマトン$ M_1 = (Q_1, \Sigma_1, \Delta_1, \delta_1, q_{01}, F_1)と$ M_2 = (Q_2, \Sigma_2 \Delta_2, \delta_2, q_{02}, F_2)を考える
2つがそれぞれ受理する言語$ L(M_1)と$ L(M_2)とが等しいとき、$ M_1 \equiv M_2と書いて、2つは等価であるという
この定義は有限オートマトン以外のオートマトンにも同様に用いられる
状態の等価性
言語 $ L(M)はそのオートマトンの初期状態$ q_0を用いて$ L(q_0)のように書くこともできる
この初期状態の代わりに別な状態$ pを初期状態に用いると別なオートマトンを定義できる
このオートマトンにより定まる言語を $ L(p)とおく。
オートマトンを固定すると、状態によって言語を定めることができるということ
これを用いると、次の式で「状態の等価性」を定義できる
$ L(p) = L(q)のとき $ p \equiv q 、つまり、状態により定まる言語が等しいとき、状態は等価であるという。