"T0L Systems and Languages" (1973)
T0L-System とは
Ｇ＝<Ｖ,Σ,ω,Ｐ>
- Ｖ： alphabet.
- ω： axiom. 開始文字列（∈Ｖ*）
- Ｐ： table. 導出規則のテーブル = {P1, ..., Pn}
- Pi： a -> α の形の"導出規則"の有限集合。ただしa∈Ｖ,α∈Ｖ*。Piはcomplete（∀a∈Ｖ: aから始まる導出規則が存在）
１ステップの書き換え s => t は
- Ｐからどれか一つPiを選ぶ
- s = a1a2...an, a1->α1∈Pi, ..., an->αn∈Pi のとき t=α1...αn
で定義される。Gの定義する言語は L(G) = {t∈Ｖ* | ω=>*t}。
0L-System と違ってテーブルを複数個持つことで、どのテーブルを使ったかでなんとなくグローバルな同期がとれるようになっているのがポイント。また、終端記号と非終端記号の区別がないので文脈自由言語ともまたuncomparableなクラスになっている。
最終更新：2009年04月03日 16:42
