Здравствуйте! Учусь на первом курсе, по матлогике, дали такие задачи.
Не подскажете в правильном ли я начинала решать их.
Реализовать машину Тьюринга и алгорифм Маркова:
Добавить в начало слова 1, если разность между количеством нулей и количеством единиц делится на 3.
При реализации машины Тьюринга, я так поняла, разность между количеством
и
можно посчитать по модулю 3. то есть если
, то
, если
, то
т все считается за один проход). Поступала вот так:
Будем следить за количеством 0 минус количество 1 по модулю 3. Остатки 0, 1, 2 от деления на 3 будем запоминать в состояниях q0, q1, q2, соответственно. Рассмотрим функции
и
, определяемые следующим образом.
Рассмотрим такие правила.
для всех
.
Тогда после одного прохода, начиная с состояния
, машина будет снова в состоянии
тогда и только тогда, когда разность между количеством 0 и количеством 1 делится на 3.
А вот алгорифмы Маркова, начала изучать недавно и не понимаю как реализовать правило которое считает разность количества между 0 и 1. Была идея сделать соотношения пар 0 и 1, но все равно не получается.
Буду благодарна любой помощи, спасибо