与えられた:
- から までの文字のみを含むchar 文字列の
S長さl'a''z'ordered置換ルールのセットR( の形式X->Y)。ここでx、yは からの 1 文字です'a' to 'z'(たとえば、'a' -> ' e'有効なルールになる可能性がありますが、'ce'->'abc'決して有効なルールにはなりません)。
のルールrが にR適用されると、ルールがの置換を引き起こす場合、が呼び出されると、ルールのと等しいSすべての文字が のの文字に置き換えられます。Sleft siderright siderrSrtriggered rule
フローチャート (アルゴリズム) : (1) のルールを( のルールの順序に従って)に
交互に適用します。
(2) While : 繰り返し (1)
(3) 終了allRRS(there exists any 'triggered rule' DURING (1) )
質問は次のとおりです。特定の文字列 S とセット R を使用して、アルゴリズムが終了するかどうかを判断する方法はありますか (永久に実行されます)。
例 1 : (手動で実行)
S =
'abcdef'R ={ 'a'->'b' , 'b' -> 'c' }
(順序は、各ルールの左から右への出現順序を意味します)
S と R でアルゴリズムを実行した後:
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): (1.1) の間に 2 つの置換があるため、(1) を繰り返します
。 (1.2): 'cccdef'
(2.2): 途中で置換がないため、(3) に進みます。 (1.2)
(3) :
アルゴリズムを終了 => アルゴリズムは指定された S と R で終了します
。
S =
'abcdef'R ={ 'a'->'b' , 'b' -> 'a' }
(順序は、各ルールの左から右への出現順序を意味します)
S と R でアルゴリズムを実行した後:
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): (1.1) の間に 2 つの置換があるため、(1) を繰り返します
(1.2): 'abcdef--> 'bbcdef' --> 'abcdef'
(2.2): あるため、(1) を繰り返します。 (1.2) (1.3) の間に 2 つの置換
があります: ...... それは (1.1) 永遠に同じです....
ステップ (3) (終了) には到達しません。
=> アルゴリズムは、指定された S と R で終了しません。
- 私はこれに取り組みましたが、「アルゴリズムが停止した場合」という質問に対する効率的なアルゴリズムは見つかりませんでした。
最初に頭に浮かんだアイデアは、入っている
"find cycle"文字のことでしtriggered rulesたが、ルールの数が多すぎて、このアイデアが理想的であるとは言えませんでした。2 つ目は、繰り返しの時間を提案すること
"threshold"です。しきい値を超えた場合、アルゴリズムは終了しないと結論付けます。(
"threshold"十分な大きさである限り) ランダムに選択できますが、このアプローチはあまり魅力的ではありません。常に正しい答えが得られるようにする
upper boundための ものがあればと考えています。"threshold"そして、26 が 'a' から 'z' までの文字の数である場所を思いつきましたがthreshold = 26、それが正しいかどうかを証明することはできません。（一定のステップ数で負のサイクルを決定するベルマンフォードアルゴリズムのようなものだといいのですが..）君はどうでしょう？答えを見つけるのを手伝ってください（これは宿題ではありません）
読んでくれてありがとう。