文字列書き換え系

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "文字列書き換え系" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年2月)

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

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

${\displaystyle x_{0}x_{1}\cdots x_{n}\rightarrow y_{0}y_{1}\cdots y_{m},\quad x_{i},y_{i}\in A}$

この規則は、任意の部分文字列 x₀x₁...x_n が y₀y₁...y_m に置換されることを意味する。

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

${\displaystyle x_{0}(x_{1}(\cdots (x_{n}(x)))\cdots )\rightarrow y_{0}(y_{1}(\cdots (y_{m}(x))\cdots )}$

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

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

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

• 形式文法
• L-system
• マルコフアルゴリズム

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集