Regular Tree Grammar - formallang.memo

"Tree Generating Regular Systems" (1969)

文字列だとオートマトンに対する(左|右)線形文法という文法があるのと同様に、ツリーオートマトンに対応する言語クラスを文法的に定義したもの。Bottom-up ツリーオートマトンと表現力が等しいことが示されている。

• Walter S. Brainerd
• Information and Control, vol. 14, pp. 217-231
• http://dx.doi.org/10.1016/S0019-9958(69)90065-5

Regular Tree Grammar とは

G = <Σ,N,S,R>

• Σ : アルファベット（要は木のノードのラベル。ranked = ラベルによってこの数は固定）
• N : 非終端記号
• S ∈ N : 開始記号
• R : 導出規則
  • A → RHS where RHS ::= σ(RHS,...,RHS) | A の集まり

S から始めて非終端記号がなくなるまで書き換えを続けてってできたものが出力木、という形で木言語を定義する。