Прекращение замены букв

Question

Дано:

• Строка символа S длина l содержащий только символы из 'a' в 'z'
• Набор из ordered правила замещения R (в виде X->Y) где x, y отдельные буквы от 'a' to 'z' (например, 'a' -> ' e' может быть действительным правилом, но 'ce'->'abc' никогда не будет действительным правилом)

Когда правило r в R применяется на S, все буквы S которые равны left side правила r будет заменен буквой в right side из rесли правило r вызвать любую замену в S, r называется triggered rule,

Блок-схема (алгоритм):
(1) поочередно применять all правила в R (следуя порядку правил в R) на S,
(2) Хотя (there exists any 'triggered rule' DURING (1) ): повторить (1)
(3) Завершить

Вопрос в следующем: есть ли способ определить, будет ли алгоритм с заданной строкой S и набором R завершаться или нет (работает вечно)

Пример 1: (выполняется вручную)

S = 'abcdef' R = { 'a'->'b' , 'b' -> 'c' }
(под порядком подразумевается порядок появления слева направо каждого правила)

Алгоритм бега по S и R:
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): повторите (1), потому что во время (1.1) есть 2 замены
(1.2): 'cccdef'
(2.2): переходите к (3), потому что во время (1.2) замены нет
(3): завершить алгоритм
=> Алгоритм завершается с заданными S и R
Example2:

S = 'abcdef' R = { 'a'->'b' , 'b' -> 'a' }
(под порядком подразумевается порядок появления слева направо каждого правила)

Алгоритм бега по S и R:
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): повторите (1), потому что во время (1.1) есть 2 замены
(1.2): 'abcdef -> 'bbcdef' -> 'abcdef'
(2.2): повторите (1), потому что во время (1.2) есть 2 замены
(1.3): ...... это было бы похоже (1.1) навсегда....
Шаг (3) (прекратить) никогда не достигается.
=> Алгоритм не завершится с заданными S и R.

• Я работал над этим и не нашел эффективного алгоритма для вопроса "останавливается ли алгоритм".

• Первая идея пришла мне в голову, чтобы "find cycle" букв, которые находятся в triggered rules но число правил может быть слишком большим, чтобы эта идея была идеальной.

• Второй - предложить "threshold" на время повтора, если порог превышен, мы заключаем, что алгоритм не будет завершен.

• "threshold" может быть выбран случайным образом (при условии, что он достаточно большой) - этот подход не является действительно убедительным.

• Я думаю, что если есть upper bound для"threshold" что гарантирует, что мы всегда получаем правильный ответ. И я придумал threshold = 26 где 26 - номер буквы от "а" до "z" - но я не могу доказать, что это правда (или нет). (Я надеюсь, что это будет что-то вроде алгоритма Беллмана-Форда, который определяет отрицательный цикл за фиксированное число шагов,..)

• Как насчет тебя? Пожалуйста, помогите мне найти ответ (это не домашняя работа)

  Спасибо за чтение.

Answer 1

Один из простых способов решить эту проблему - рассмотреть строку длины 1 и посмотреть, может ли задача зацикливаться для любой заданной начальной буквы. Поскольку длина строки никогда не меняется, и применение правила применяется независимо к каждому символу в S, достаточно рассмотреть только строку длины 1.

Теперь начнем с диаграммы состояний с 26 состояниями - по 1 на каждую букву алфавита. Теперь для ваших переходов состояний рассмотрим этот процесс:

Применяйте переходы из R 1 по порядку, пока не достигнете конца R. Если из определенного состояния (буквы) вы никогда не достигнете новой буквы, вы знаете, что если вы достигнете начальной буквы, вы прекратите, В противном случае после применения всей последовательности R вы получите новую букву. Это будет ваше новое состояние.

Обратите внимание, что все переходы состояний являются детерминированными, потому что мы применяем всю последовательность R, а не только отдельные переходы. Если мы применяем отдельные переходы, мы можем запутаться, потому что у нас может быть a -> b, b->a, a->c. Рассматривая отдельные операции, мы могли бы подумать, что есть два возможных перехода от a (к b или к c), но на самом деле, рассматривая всю последовательность, мы окончательно видим, что переходы к c.

Вы закончите создание диаграммы состояний после рассмотрения следующих состояний каждой начальной буквы. Создание всей диаграммы состояний таким образом требует 26 * |R| операции. Если диаграмма состояний содержит цикл, то если строка S содержит какие-либо буквы в цикле, то она не может остановиться, в противном случае она остановится.

В качестве альтернативы, если вы просто остановитесь после 26 итераций по всей последовательности из R, вы также можете использовать это.