"Extension of Tabled 0L-Systems and Languages" (1973)
ET0
L-Systemを提案した論文。
L-System系の言語理論(developmental language)の方向で、Chomsky系の形式言語理論に親和性が高い形にまとめたのがこの研究。良いClosure Propertyを持っていたり（Full AFL）、文脈自由言語を真に含んでいたりする。
これ以前のL-System系のシステムと違って、非終端記号と終端記号の区別を入れたのがポイントなのだと思う。
ET0L とは
Ｇ＝<Ｖ,Σ,ω,Ｐ>
- Ｖ： alphabet. 非終端記号と終端記号の集合
- Σ： target 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}。
各PiがDeterministicな場合（つまり、∀a∈Ｖ: aから始まる導出規則が"唯一"存在な場合）、システム自体がDeterministicであるという。EDT0L と書く。αが常に空文字列でないような場合を Productive という。
CFG との関係
1ステップで全体を並行して一気に書き換えるのがポイント。どのPiを使ったかによって、導出の深さが同じところの間でなんとなくシンクロがとられて、文脈自由を越える言語が書ける。
T0L との関係
Ｖ＝ΣなのがT0L。非終端記号と終端記号の区別を入れたのがET0L。
E0L との関係
|Ｐ|=1 なのが E0L。テーブルが複数種類あるのが ET0L。
Ｖ＝Σで|Ｐ|=1なのが0L。
0L は L の拡張ではなく制限なので注意。
"Surface Tree Languages and Parallel Derivation Trees" (1976)
ET0L = yield(T(MON))。ET0L言語族は、monadic treeを入力言語としてTop-down
Tree Transducerで生成できる木のyield(葉を左から右に並べた文字列)として得られる言語族に等しい。また、deterministic 版についても EDT0L = yield(DT(MON)) が成り立つ。
最終更新：2009年04月03日 16:41
