Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ■ チェーンの文字列
- -------------------------
- ■ 規則の定義
- 言語Lを、次の正規表現にて定義する。
- "ちぇぇ*ん"
- なお * はクリーネ閉包(0個以上の繰り返し)である。
- この言語Lに属する文字列は、次のようなものが挙げられる。
- "ちぇぇん"
- "ちぇぇぇん"
- "ちぇぇぇぇん"
- この言語L上にて項書換え系を定義する。書き換え手順は次の通り。
- 手順1:前処理
- 言語Lに属する文字列について、記号を挿入する。
- ・記号 "ち" の直後に記号 "[" を挿入する
- ・記号 "ん" の直前に記号 "," および "]" を挿入する
- 手順2:ちぇんの置換
- 記号列を、以下のパターンマッチ規則によって書き換える
- Rule1. [,Y] → Yぇ
- Rule2. [Xぇ,] → [X,ぇ]
- Rule3. [Xぇ,Yぇ] → [X,[Xぇ,Y]]
- ただしX,Yは、0以上の任意長の記号列にマッチする変数である。
- 手順2は、書き換え規則が適用できなくなるまで繰り返す。
- 書き換えた結果は、言語Lに属する文字列となる。
- ■ チェーンの文字列の定義
- 前述の規則において、文字列
- 『ちぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇん』
- に対して書き換えを 64 回適用した結果を、
- 『ちぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇぇん』の文字列とする。
- ■ より短い文字列での計算例
- 文字列『ちぇぇぇぇん』に書き換えを 1 回適用すると、文字列『ちぇぇぇぇぇぇぇぇぇぇぇぇぇん』が得られる。
- ちぇぇぇぇん
- → ち[ぇぇぇぇ,]ん
- → ち[ぇぇぇ,ぇ]ん
- → ち[ぇぇ,[ぇぇぇ,]]ん
- → ち[ぇぇ,[ぇぇ,ぇ]]ん
- → ち[ぇぇ,[ぇ,[ぇぇ,]]]ん
- → ち[ぇぇ,[ぇ,[ぇ,ぇ]]]ん
- → ち[ぇぇ,[ぇ,[,[ぇ,]]]]ん
- → ち[ぇぇ,[ぇ,[,[,ぇ]]]]ん
- → ち[ぇぇ,[ぇ,[,ぇぇ]]]ん
- → ち[ぇぇ,[ぇ,ぇぇぇ]]ん
- → ち[ぇぇ,[,[ぇ,ぇぇ]]]ん
- → ち[ぇぇ,[,[,[ぇ,ぇ]]]]ん
- → ち[ぇぇ,[,[,[,[ぇ,]]]]]ん
- → ち[ぇぇ,[,[,[,[,ぇ]]]]]ん
- → ち[ぇぇ,[,[,[,ぇぇ]]]]ん
- → ち[ぇぇ,[,[,ぇぇぇ]]]ん
- → ち[ぇぇ,[,ぇぇぇぇ]]ん
- → ち[ぇぇ,ぇぇぇぇぇ]ん
- → ち[ぇ,[ぇぇ,ぇぇぇぇ]]ん
- → ち[ぇ,[ぇ,[ぇぇ,ぇぇぇ]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇぇ,ぇぇ]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇぇ,ぇ]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,[ぇぇ,]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,ぇ]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,[,[ぇ,]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,[,[,ぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,[,ぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[ぇ,ぇぇぇ]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,[ぇ,ぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,[,[ぇ,ぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,[,[,[ぇ,]]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,[,[,[,ぇ]]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,[,[,ぇぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,[,ぇぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,[,ぇぇぇぇ]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[ぇ,ぇぇぇぇぇ]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[ぇ,ぇぇぇぇ]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[ぇ,ぇぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,[ぇ,ぇぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,[,[ぇ,ぇ]]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,[,[,[ぇ,]]]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,[,[,[,ぇ]]]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,[,[,ぇぇ]]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,[,ぇぇぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,[,ぇぇぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,[,ぇぇぇぇぇ]]]]]ん
- → ち[ぇ,[ぇ,[ぇ,[,ぇぇぇぇぇぇ]]]]ん
- → ち[ぇ,[ぇ,[ぇ,ぇぇぇぇぇぇぇ]]]ん
- → ち[ぇ,[ぇ,[,[ぇ,ぇぇぇぇぇぇ]]]]ん
- → ち[ぇ,[ぇ,[,[,[ぇ,ぇぇぇぇぇ]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[ぇ,ぇぇぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[ぇ,ぇぇぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,[ぇ,ぇぇ]]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,[,[ぇ,ぇ]]]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,[,[,[ぇ,]]]]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,[,[,[,ぇ]]]]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,[,[,ぇぇ]]]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,[,ぇぇぇ]]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,[,ぇぇぇぇ]]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,[,ぇぇぇぇぇ]]]]]]ん
- → ち[ぇ,[ぇ,[,[,[,ぇぇぇぇぇぇ]]]]]ん
- → ち[ぇ,[ぇ,[,[,ぇぇぇぇぇぇぇ]]]]ん
- → ち[ぇ,[ぇ,[,ぇぇぇぇぇぇぇぇ]]]ん
- → ち[ぇ,[ぇ,ぇぇぇぇぇぇぇぇぇ]]ん
- → ち[ぇ,[ぇ,ぇぇぇぇぇぇぇぇぇ]]ん
- → ち[ぇ,[,[ぇ,ぇぇぇぇぇぇぇぇ]]]ん
- → ち[ぇ,[,[,[ぇ,ぇぇぇぇぇぇぇ]]]]ん
- → ち[ぇ,[,[,[,[ぇ,ぇぇぇぇぇぇ]]]]]ん
- → ち[ぇ,[,[,[,[,[ぇ,ぇぇぇぇぇ]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[ぇ,ぇぇぇぇ]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[ぇ,ぇぇぇ]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,[ぇ,ぇぇ]]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,[,[ぇ,ぇ]]]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,[,[,[ぇ,]]]]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,[,[,[,ぇ]]]]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,[,[,ぇぇ]]]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,[,ぇぇぇ]]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,[,ぇぇぇぇ]]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,[,ぇぇぇぇぇ]]]]]]]ん
- → ち[ぇ,[,[,[,[,[,ぇぇぇぇぇぇ]]]]]]ん
- → ち[ぇ,[,[,[,[,ぇぇぇぇぇぇぇ]]]]]ん
- → ち[ぇ,[,[,[,ぇぇぇぇぇぇぇぇ]]]]ん
- → ち[ぇ,[,[,ぇぇぇぇぇぇぇぇぇ]]]ん
- → ち[ぇ,[,ぇぇぇぇぇぇぇぇぇぇ]]ん
- → ち[ぇ,ぇぇぇぇぇぇぇぇぇぇぇ]ん
- → ち[,[ぇ,ぇぇぇぇぇぇぇぇぇぇ]]ん
- → ち[,[,[ぇ,ぇぇぇぇぇぇぇぇぇ]]]ん
- → ち[,[,[,[ぇ,ぇぇぇぇぇぇぇぇ]]]]ん
- → ち[,[,[,[,[ぇ,ぇぇぇぇぇぇぇ]]]]]ん
- → ち[,[,[,[,[,[ぇ,ぇぇぇぇぇぇ]]]]]]ん
- → ち[,[,[,[,[,[,[ぇ,ぇぇぇぇぇ]]]]]]]ん
- → ち[,[,[,[,[,[,[,[ぇ,ぇぇぇぇ]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[ぇ,ぇぇぇ]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,[ぇ,ぇぇ]]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,[,[ぇ,ぇ]]]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,[,[,[ぇ,]]]]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,[,[,[,ぇ]]]]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,[,[,ぇぇ]]]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,[,ぇぇぇ]]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,[,ぇぇぇぇ]]]]]]]]]ん
- → ち[,[,[,[,[,[,[,[,ぇぇぇぇぇ]]]]]]]]ん
- → ち[,[,[,[,[,[,[,ぇぇぇぇぇぇ]]]]]]]ん
- → ち[,[,[,[,[,[,ぇぇぇぇぇぇぇ]]]]]]ん
- → ち[,[,[,[,[,ぇぇぇぇぇぇぇぇ]]]]]ん
- → ち[,[,[,[,ぇぇぇぇぇぇぇぇぇ]]]]ん
- → ち[,[,[,ぇぇぇぇぇぇぇぇぇぇ]]]ん
- → ち[,[,ぇぇぇぇぇぇぇぇぇぇぇ]]ん
- → ち[,ぇぇぇぇぇぇぇぇぇぇぇぇ]ん
- → ちぇぇぇぇぇぇぇぇぇぇぇぇぇん
- ------------------
- ■更新履歴
- 2018/03/21 12:00:00, 書き換え規則を修正。ただし有限長の文字列について書き換え結果は変化しない。
- 修正前:
- Rule1. [,Y] → ぇY
- Rule2. [Xぇ,] → [X,ぇ]
- Rule3. [Xぇ,Yぇ] → [X,[Xぇ,Y]]
- 修正後:
- Rule1. [,Y] → ぇY
- Rule2. [ぇX,] → [X,ぇ]
- Rule3. [ぇX,ぇY] → [X,[ぇX,Y]]
- 2018/03/21 12:15:00, 書き換え規則を再度修正。
- 修正前:
- Rule1. [,Y] → ぇY
- Rule2. [ぇX,] → [X,ぇ]
- Rule3. [ぇX,ぇY] → [X,[ぇX,Y]]
- 修正後:
- Rule1. [,Y] → Yぇ
- Rule2. [Xぇ,] → [X,ぇ]
- Rule3. [Xぇ,Yぇ] → [X,[Xぇ,Y]]
- 以上.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement