イラストで学ぶ音声認識 4章

4. 有限状態オートマトン 4.1 有限状態オートマトンとは 4.2 有限状態オートマトンが表現する言語 4.3 さまざまな有限状態オートマトン 4.4 有限状態オートマトンの性質 • 荒木雅弘 :『イラストで学ぶ音声認識』 （講談社, 2015年） • サポートページ

• https://masahiroaraki.github.io/GuideToASR/

4.1 有限状態オートマトンとは • 有限状態オートマトン の定義 • 状態を持つ機械の振る舞いの論理的モデル • 有限状態オートマトンの形式的定義 • Σ : 入力記号の集合 • Q : 状態の集合 • I ⊆ Q : 初期状態の集合 • F ⊆ Q : 最終状態の集合 • E ⊆ Q ✕ Σ ✕ Q : 状態遷移規則の集合

4.1 有限状態オートマトンとは • 有限状態受理機械 (finite state acceptor: FSA) • 入力記号列が特定の規則に従っているかどうかを判定する有限状態 オートマトン • FSAの例 • Σ = {形容詞, 名詞, 助詞, 動詞} • Q = {0, 1, 2, 3, 4} • I = {0} • F = {4} • E = {(0, 名詞, 1), (0, 形容詞, 2), ...}

4.1 有限状態オートマトンとは • 決定性と非決定性 • 決定性オートマトン：現在の状態と入力記号から次状態が一つに定まる • 非決定性オートマトン：上記条件で、次状態が一つに定まらない （同 じ入力記号で異なる状態に遷移可能な場合） • 入力記号に空文字列 ε を含む場合は、必然的に非決定的になる

4.2 有限状態オートマトンが表現する言語 • FSAで表現できる言語＝正規言語 • 正規言語の定義 1. 空集合は正規言語である 2. すべての a ⊆ (Σ∪ε) に対して、{a}は正規言語である 3. αとβが正規言語であるとき、以下も正規言語である a. 連接 α・β b. 選択 α | β c. 繰り返し α* 4. これ以外のものは正規言語ではない

4.3 さまざまな有限状態オートマトン • FSA • 構成要素：{Σ, Q, I, F, E}

4.3 さまざまな有限状態オートマトン • WFSA • 構成要素：{Σ, Q, I, F, E, λ, ρ} • • • • E⊆Q✕Σ✕K✕Q K : 重みの集合 λ : 初期状態の重み ρ : 最終状態の重み 重みが加わる

4.3 さまざまな有限状態オートマトン • FST • 構成要素：{Σ, Δ, Q, I, F, E} • Δ : 出力記号の集合 • E⊆Q✕Σ✕Δ ✕Q 出力が加わる

4.3 さまざまな有限状態オートマトン • WFST • 構成要素：{Σ, Δ, Q, I, F, E, λ, ρ} • E⊆Q✕Σ✕Δ✕K✕Q 重みと出力が加わる

4.4 有限状態オートマトンの性質 • オートマトンの型 • ミーリ型：出力が現在の状態と入力で決まる • ムーア型：出力が現在の状態だけで決まる 相互に変換可能 • オートマトンの有用な性質 • 非決定性オートマトンは、決定性オートマトンに変換することが可能 （決定化） • 決定性オートマトンは、その機能を変えることなく、状態数最小の オートマトンに変換可能（最小化）