Нормальный алгоритм Маркова: увеличение числа на 1

Вот такой нынче у меня был спор с преподавателем, так и не разрешила проблему, может кто подскажет.
Дано задание: описать алгоритм увеличения числа на единицу.

Преподаватель это решил приблизительно так: "ну тут мы в конце добавляем * ну и дальше заменяем 9*->*0, дальше завершающим действием будет замена чисел стоящих перед 9:
8*-> 9
7*-> 8
...
e -> * - это мы перед числом ставим * ну и при **: ** -> 1"

Надеюсь, что принцип форумчанинам понятен? Я знаю, что я слишком сократила... Если очень сумбурно, я перепишу.

Но в общем, мой вопрос таков: в теории этих вот нормальных алгоритмов, чем ограничивается длинна слова? То есть, к примеру, слово состоит из 5ти символов, а есть ли "спереди слова и сзади" пустые символы, которые какбы ограничивают его?

И еще один вопрос. Преподаватель не уточнил, каким образом мы * перемещаем в конец нашего числа, так вот, не вызовет ли эта часть алгоритма вместе с частью об изменении цыфр зацыкливания? нужно ли добавлять еще один дополнительный символ?

Ну и последнее, если кто-то ничего не понял из моей ахинеи, как по-вашему решить это задание???

Спасибо.

0

не припомню, чтобы в НАМ была длина слова, но для данной задачи можно добавить в начале и в конце слова символы, а в конце алгоритма стереть их. Если его правильно написать, то никакого зацикливания не будет:
0* -> 1
1* -> 2
2* -> 3
...
8* -> 9
9* -> *0
** -> 1
* - λ (пустой символ)

0

Сообщение от KaiTheCat не припомню, чтобы в НАМ была длина слова, но для данной задачи можно добавить в начале и в конце слова символы, а в конце алгоритма стереть их. Если его правильно написать, то никакого зацикливания не будет: 0* -> 1 1* -> 2 2* -> 3 ... 8* -> 9 9* -> *0 ** -> 1 * - λ (пустой символ)

вот и я "спорила" о том же, что просто так "*" в конце слова не поставить. То, что вы написали сверху, - это как раз и есть алгоритм увеличения на единицу. Это легко и я это написала.
Но все же скажите, пожалуйста, если знаете, как объединить это "увеличение" с "прибавлением звездочки в начало и конец числа?

0

0λ -> 0?
1λ -> 1?
...
8λ -> 8?
9λ -> *0!
0? -> 1!
1? -> 2!
...
8? -> 9!
0* -> 1
1* -> 2
2* -> 3
...
8* -> 9
9* -> *0
* -> 1
! -> λ

2

Сообщение от KaiTheCat 0λ -> 0? 1λ -> 1? ... 8λ -> 8? 9λ -> *0! 0? -> 1! 1? -> 2! ... 8? -> 9! 0* -> 1 1* -> 2 2* -> 3 ... 8* -> 9 9* -> *0 * -> 1 ! -> λ

Ага, ну так, как и предполагалось, нужно использовать два дополнительных символа. Что и требовалось доказать.

0