有限オートマトン

complexity

概要

よく「状態遷移図」と言われてこのような図を思い浮かべる.

これは有限オートマトン と呼ばれている.
ある特定の文字列を入力として左上の部分からスタートし受理状態(図の二重丸の部分)に辿りつければ 受理する という. 受理する文字列として, 例えば aa, abaa, aaaa などが考えられる.

ある入力に対する遷移先が必ず1つの時は決定的とよばれ, そのようなオートマトンを決定性有限オートマトン(DFA;Deterministic Finite Automata) と呼ぶ. そうでない時は 非決定性有限オートマトン(NFA) と呼ぶ. 非決定性有限オートマトンは決定性有限オートマトンに必ず変換できる. (つまり, 性能は同じ)

DFAの定義

DFA $‘A‘$ を

$‘A=(Q,\Sigma ,q_0,A,\delta )‘$ と定義する.

• $‘Q‘$: 状態(例だと $‘\{A,B,C\}‘$)
• $‘\Sigma ‘$: 入力アルファベット (例だと $‘\{a,b\}‘$)
• $‘q_0‘$: 開始状態(例だと $‘A‘$)
• $‘A‘$: 受理状態(例だと $‘\{C\}‘$)
• $‘\delta :Q\times \Sigma \to Q‘$: 遷移関数

言語

DFA $‘A‘$ によって受理される文字列の集合をDFA $‘A‘$ の言語 という. DFAで受理できる言語のことを 正規表現 という.

DFAの限界

DFAはいかなる言語でも受理出来るかというとそうではない. 例えば $‘L=\{a^k{b}^k\mid k\in \mathbb{N}\}‘$ (例: ab, aabb, aaabbb ...)のような特定回数繰り返す文字列を受理するDFAは作ることが出来ない.