文字列書き換え系のソースを表示

{{出典の明記|date=2023年2月27日 (月) 10:59 (UTC)}}
'''文字列書き換え系'''（[[英語|英]]: '''String rewriting system'''）は、与えられた文字列に所定の書き換え規則を適用して変換を行う置換系の一種であり、[[ポスト正準系]]の特殊な型である。

== 基本的な文字列書き換え系の等価性 ==
文字列書き換え系の基本的形式は[[項書き換え]]系と本質的に等価である。ある[[アルファベット (計算機科学)|アルファベット]] ''A'' による文字列があり、次のような形式の部分文字列置換規則のみがあるとする。
: <math> x_0x_1\cdots x_n \rightarrow y_0y_1\cdots y_m,\quad x_i, y_i \in A</math>
この規則は、任意の部分文字列 ''x''<sub>0</sub>''x''<sub>1</sub>...''x''<sub>n</sub> が ''y''<sub>0</sub>''y''<sub>1</sub>...''y''<sub>m</sub> に置換されることを意味する。

このような文字列書き換え系は項書き換え系に再定式化することができ、そのときの置換規則は以下のようになる。
: <math> x_0(x_1(\cdots ( x_n(x) )) \cdots ) \rightarrow y_0(y_1(\cdots (y_m(x)) \cdots)</math>
ここで、''x''<sub>i</sub> や ''y''<sub>''i''</sub> は項書き換え系の関数シンボルである。

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

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

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

{{DEFAULTSORT:もしれつかきかえけい}}
{{computer-stub}}

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

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