受理状態

有限オートマトン $M$ では,開始する状態 $q_{0}$と終了する状態 $q_{n}$ 決められています.

このとき,開始状態で最初の入力が行われ,入力の最後で有限オートマトン $M$ が定めた条件を満たしているという状態 $F \subset Q$ のことを受理状態といいます.

\[\begin{xy}\xymatrix{&\ar[d]&\\&*++[o][F-]{q_{0}} \ar@(ur,ul)_1 \ar[r]^{0} & *++[o][F=]{q_{1}}\ar@(ru,rd) []^{0,1} }\end{xy}\]

上にあるようなオートマトンを表す状態遷移図を考えてみます.

このオートマトンに $0$ が入力されると,状態は $q_{0}$ から $q_{1}$ に遷移します.

$q_{1}$ は受理状態なので,オートマトンは,この入力を受理するということになります.

正規集合 regular set

有限オートマトン(FA)によって受理される言語 $\mathcal{L}$ は,正規集合(regular set)といいます.

正規集合は,スティーヴン・コール・クリーネ(Stephen Cole Kleene,1909年1月5日-1994年1月25日)の導入した正規表現という言語 $\mathcal{L}$ に属する語の一定のパターンを表現する「正規表現」という式によって,表現することができます.

これが正規集合が正規集合と呼ばれるようになったことの由来になります.

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 チューリングマシン 状態遷移関数 有限オートマトン 還元可能性 reducibility オートマトン