投稿者: 
チョムスキー階層で触れた有限オートマトンについて。
チョムスキー階層(Chomsky hierarchy)と前回の投稿で下記に触れた。
- 有限オートマトン (finite automaton)
正則文法 (regular grammar)
(北 1999)
本投稿ではまず、このオートマトン (automaton)をさらに深掘りして有限オートマトンについてまとめたい。
前回の投稿では、自動販売機を例に説明したがその例を引き続き使うものとする。
自販機はオートマトンの1例であるが、自販機に投入できる硬貨の種類は有限である。また、目標金額が決定されているので上限も設定されている。
例えば、投入出来る硬貨が10円,50円,100円だとすれば硬貨の3種類、目標金額が150円だとする。すると内部状態は下記のように洗い出せる。
| 現在の金額 | 挿入された硬貨 | 新しい金額 |
|---|---|---|
| 0円 | 10円 | 10円 |
| 10円 | 10円 | 20円 |
| 20円 | 10円 | 30円 |
| 30円 | 10円 | 40円 |
| 40円 | 10円 | 50円 |
| 50円 | 10円 | 60円 |
| 60円 | 10円 | 70円 |
| 70円 | 10円 | 80円 |
| 80円 | 10円 | 90円 |
| 90円 | 10円 | 100円 |
| 100円 | 10円 | 110円 |
| 110円 | 10円 | 120円 |
| 120円 | 10円 | 130円 |
| 130円 | 10円 | 140円 |
| 140円 | 10円 | 150円 |
| 0円 | 50円 | 50円 |
| 50円 | 50円 | 100円 |
| 100円 | 50円 | 150円 |
| 0円 | 100円 | 100円 |
| 100円 | 100円 | 150円 |
このように内部状態の遷移数が有限となるものを有限オートマトンと呼ぶ。
参考文献
- 新屋良磨. (2017). オートマトン理論再考. コンピュータ ソフトウェア, 34(3), 33-335.
- 電子情報通信学会 知識ベース 1-1 オートマトン
https://www.ieice-hbkb.org/files/ad_base/view_pdf.html?p=/files/06/06gun_02hen_01.pdf#page=2 - 北研二. (1999). 確率的言語モデル. 言語と計算, 4.