文字列書き換え系

文字列書き換え系（英: String rewriting system）は、与えられた文字列に所定の書き換え規則を適用して変換を行う置換系の一種であり、ポスト正準系の特殊な型である。

 基本的な文字列書き換え系の等価性 
文字列書き換え系の基本的形式は項書き換え系と本質的に等価である。あるアルファベット A による文字列があり、次のような形式の部分文字列置換規則のみがあるとする。

この規則は、任意の部分文字列 x0x1...xn が y0y1...ym に置換されることを意味する。

このような文字列書き換え系は項書き換え系に再定式化することができ、そのときの置換規則は以下のようになる。

ここで、xi や yi は項書き換え系の関数シンボルである。

すなわちこの項書き換え系における文字列は、基底項である。

 例 
決定性の文字列書き換えに基づいた計算モデルの例として、マルコフアルゴリズム、各種形式文法、L-system などがある。L-system はカントール集合やメンガーのスポンジといったある種のフラクタルの生成に適している。

 関連項目 
形式文法
L-system
マルコフアルゴリズム

Category:計算理論
Category:形式手法
Category:数学に関する記事

de:Semi-Thue-System
en:Semi-Thue system
hr:Semi-Thue sustav
pl:System półthueowski
pt:Sistemas de Thue-Semi