---
title: イラストで学ぶ音声認識 改訂第2版 4. 有限状態オートマトン
tags:  #音声認識  
author: [荒木 雅弘](https://convert.docswell.com/user/MasahiroAraki)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/GJ52YN5DJ4.jpg?width=480
description: イラストで学ぶ音声認識 改訂第2版 4. 有限状態オートマトン by 荒木 雅弘
published: June 05, 25
canonical: https://convert.docswell.com/s/MasahiroAraki/KMXD16-2025-06-05-141016
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/GJ52YN5DJ4.jpg)

イラストで学ぶ音声認識 改訂第2版
4. 有限状態オートマトン
4.1 有限状態オートマトンとは
4.2 有限状態オートマトンが表現する言語
4.3 さまざまな有限状態オートマトン
4.4 出力を生成する方法の違い
4.5 WFST の演算
1


# Page. 2

![Page Image](https://bcdn.docswell.com/page/LE3K525QE5.jpg)

4.1 有限状態オートマトンとは
有限状態オートマトン の定義
状態を持つ機械の振る舞いの論理的モデル
単純な有限状態オートマトンの形式的定義
: 入力記号の集合
: 状態の集合
: 初期状態の集合
: 最終状態の集合
: 状態遷移規則の集合
2


# Page. 3

![Page Image](https://bcdn.docswell.com/page/8ED3DZDW7G.jpg)

4.1 有限状態オートマトンとは
単純なオートマトンの例
入力記号列が特定の規則に従っているかどうかを，状態遷移に基づいて判定
する
= {形容詞, 名詞, 助詞, 動詞}
= {0, 1, 2, 3, 4}
= {0}
= {4}
= {(0, 名詞, 1), (0, 形容詞, 2), ...}
3


# Page. 4

![Page Image](https://bcdn.docswell.com/page/V7P4XDXXE8.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/2JVXL1L37Q.jpg)

4.2 有限状態オートマトンが表現する言語
有限状態オートマトンで表現できる言語＝正規言語
正規言語の定義
空集合は正規言語である
すべての
に対して， は正規言語である
と が正規言語であるとき，以下も正規言語である
連接 :
選択 :
繰り返し :
これ以外のものは正規言語ではない
5


# Page. 6

![Page Image](https://bcdn.docswell.com/page/5EGVX2XYEL.jpg)

4.3 さまざまな有限状態オートマトン
FSA (finite state acceptor)
入力された記号列が受理されるかどうかを判定する
構成要素：
6


# Page. 7

![Page Image](https://bcdn.docswell.com/page/4JQ68P86JP.jpg)

4.3 さまざまな有限状態オートマトン
WFSA (weighted finite state acceptor)
構成要素：
（状態遷移に重みが加わる）
: 重みの集合（ , など）, : 初期状態の重み, : 最終状態の重み
7


# Page. 8

![Page Image](https://bcdn.docswell.com/page/K7442Y2M71.jpg)

4.3 さまざまな有限状態オートマトン
FST (finite state transducer)
構成要素：
: 出力記号の集合
（状態遷移時に記号が出力される）
8


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LJ14M6MYJG.jpg)

4.3 さまざまな有限状態オートマトン
WFST (weighted finite state transducer)
構成要素：
（状態遷移に重みと出力記号が加わる）
9


# Page. 10

![Page Image](https://bcdn.docswell.com/page/GJWX3W31E2.jpg)

4.4 出力を生成する方法の違い
オートマトンの型
ミーリ型：出力が状態遷移時に決まる
ムーア型：出力が現在の状態で決まる
ミーリ型とムーア型は相互に変換可能
この2つは等価な
オートマトンです．
1:x
0:x
2:y
10


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4EZ6V5VXE3.jpg)

4.5 WFST の演算
オートマトンの有用な性質
決定化：非決定性オートマトンは，決定性オートマトンに変換可能
最小化：決定性オートマトンは，その機能を変えることなく，状態数最小の
オートマトンに変換可能
WFST の有用な操作
合成：2つの WFST を合成して新しい WFST を作る
重み移動：状態間で重みを移動させて，計算を効率化する
11


# Page. 12

![Page Image](https://bcdn.docswell.com/page/Y762595PEV.jpg)

4.5 WFST の演算
FSTの合成
2つのFST
において， の出力が の入力となるとき，合成して
ができる
12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/G752YNYP74.jpg)

4.5 WFST の演算
WFSTの合成における重みの扱い
重みが確率値の場合，通常の合成では掛け算をおこなう
しかし音声認識における探索では，確率の対数の負数をとった値に対してビ
タビアルゴリズムを適用する
すなわち，確率の掛け算は足し算に，独立な確率の和は最小値演算になる
乗法演算が足し算，加法演算が最小値となる構造をTropical半環とよぶ．
Tropical半環は通常の確率演算と同じ構造を持っているので，この構造で
WFSTの合成をおこなうことができる
13


# Page. 14

![Page Image](https://bcdn.docswell.com/page/9J24G5GZ7R.jpg)

4.5 WFST の演算
決定化
単純に合成した WFST は多くの非決定性をもつので，探索の効率化のため遷
移を決定性に変換
14


# Page. 15

![Page Image](https://bcdn.docswell.com/page/DEYMVKVNEM.jpg)

4.5 WFST の演算
WFST の最小化手順
等価な状態を集合分割によって求める
15


