「線形拘束オートマトン」の版間の差分
削除された内容 追加された内容
m robot Adding: bs:Linearno ograničen automat |
+外部リンク |
||
2行目:
線形拘束オートマトンは[[文脈依存言語]]を受容する。そのクラスの言語の[[文法]]で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存言語によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。
== 外部リンク ==
* [http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf Linear Bounded Automata] by [http://www.cs.uky.edu/~lewis/ Forbes D. Lewis]
* [http://www.seas.upenn.edu/~cit596/notes/dave/chomsky2.html Linear-Bounded Automata] , part of Theory of Computation syllabus, by David Matuszek
* [http://www.seto.nanzan-u.ac.jp/msie/gr-thesis/it/proc/2003/00mt012.pdf 線形拘束オートマトンを用いた組込みソフトウェアの仕様記述に関する考察]、二口祐介（他）、南山大学
[[Category:計算モデル|せんけいこうそくおとまとん]]
| |||