線形拘束オートマトン

線形拘束オートマトンについて

---

今まで、下記の中の有限オートマトンとプッシュダウン・オートマトンを見てきた。

1. 有限オートマトン (finite automaton)
   正則文法 (regular grammar)
2. プッシュダウン・オートマトン (pushdown automaton)
   文脈自由文法 (context-free grammar)
3. 線形拘束オートマトン (linear bounded automaton)
   文脈依存文法 (context-sensitive grammar)
4. チューリング機械 (Turing Machine)
   句構造文法 (phrase structure grammar)

(北 1999)

今回は 線形拘束オートマトンを見ていくこととする。

線形拘束オートマトン (linear bounded automaton, LBA)は限られた範囲内の情報を読み取っていくことを想定したモデルである。この際の情報が使用可能な線形の情報に拘束される。そのため、このクラスを線形拘束オートマトンという。

このクラスは文脈依存文法 (context-sensitive grammar)の言語表現を可能にするクラスに該当する。

参考文献

• 北研二. (1999). 確率的言語モデル. 言語と計算, 4.
• 西野, 哲朗 et al. (1995). 形式言語理論入門. 東京電機大学出版局.