Нормальный алгоритм Маркова

[MestnyBomzh]

[url][/url]Раньше никогда не встречался с НАМ (Нормальный алгоритм Маркова), прочитал немного в интернете как он работает
Задача: Алгоритм берет на вход строчку состоящую из букв $x, y$. На выходе алгоритм печатает одну букву - если на конце четное число $y$, то печатается $y$, во всех остальных случаях печатается $x$
Требуется написать НАМ для этого алгоритма

Я составил следующую систему правил:

$$\left\{ \begin{array}{rcl} xx & \to &x \\ yx & \to &x \\ yyyy& \to & yy \\ yyy& \to & y \\ x \lambda& \to & x \\ xyy \lambda& \to & x \\ xy \lambda & \to & x \\ \end{array} \right.$$

Могли бы проверить верно ли это?

[kotenok gav]

А $0$ - не чётное число?

-- 04 апр 2022, 17:45 --

Так будет правильнее:

$$\left\{ \begin{array}{rcl} xx & \to &x \\ yx & \to &x \\ yy& \to & \\ x \lambda& \to & .y \\ xy \lambda & \to & .x \\ \end{array} \right.$$

[MestnyBomzh]

0 - четное. Спасибо за ответ. Меня интересует точка, которую вы используете в последних двух правилах. Насколько я понял, тут необходимо напечатать один символ, если мы еще печатаем точку это пойдет?
Кстати интересная задумка с $yy \to $ я подумал про это)

[Someone]

MestnyBomzh в сообщении #1551798 писал(а):

Меня интересует точка, которую вы используете в последних двух правилах.

Наверное, имелось в виду $\to\cdot$, что означает, что после выполнения данного правила выполнение алгоритма заканчивается.

[MestnyBomzh]

ааа, точно да, спасибо

[Someone]

MestnyBomzh в сообщении #1551814 писал(а):

ааа

Забыл спросить: что означает буква "$\lambda$"? В описании нормальных алгорифмов Маркова, которое есть в книге по конструктивному математическому анализу, такая буква не употребляется. Она означает, что правее в слове никаких символов нет?

[MestnyBomzh]

я честно посмотрел в интернете похожие задачи и как они решаются, я понял $\lambda$ как символ конца строки

[Someone]

MestnyBomzh в сообщении #1551836 писал(а):

я понял $\lambda$ как символ конца строки

Вообще-то, не рекомендуется изучать незнакомую теорию по примерам, найденным в интернете. Лучше взять какую-нибудь более серьёзную литературу. Я, к сожалению, знаю только одну книгу:
Б. А. Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва 1973.
В этой книге "символ конца строки" в определении нормального алгорифма вообще не упоминается. Можно также посмотреть в Википедии. В русскоязычной или в англоязычной.