Необходимо посмотрить детерминированный конечный автомат, который проверяет делимость числа (последовательность нулей и единиц должна начинаться с 1) по модулю 5.

Здравствуйте, ZNad, Вы писали:

ZN>Необходимо посмотрить детерминированный конечный автомат, который проверяет делимость числа (последовательность нулей и единиц должна начинаться с 1) по модулю 5.

Классическая задача из домашки по теории автоматов
Хинт: рассмотрим последнюю десятичную цифру числа. Конечные состояния автомата должны соотвествовать цифрам 0 и 5.
Далее: input = 0 — это умножение на 2. Соотв., если последняя цифра была 0, то станет 0, была 1 — будет 2 и т.д.
Аналогично, input = 1 => умножение на 2 плюс 1. Соотв., если последняя цифра была 0, то станет 1, была 1 — будет 3 и т.д.
Причем сразу очевидно, что состояние когда последняя цифра 1 идентично состоянию 6, ну и т.д.
Так что состояний получается совсем немного.

Здравствуйте, ZNad, Вы писали:

ZN>Необходимо посмотрить детерминированный конечный автомат, который проверяет делимость числа (последовательность нулей и единиц должна начинаться с 1) по модулю 5.

Я так понял, что вводится двоичное число, начиная со старшего разряда. Надо определить, делится ли оно на 5.

По сути надо всего 5 состояний: остаток от деления введеного до сих пор числа на 5. Ввод очередной цифры увеличивает предыдущий результат в двое (по модулю 5), и прибавляет новую цифру (0 или 1). Т.е. при вводе x (0 или 1) переходим из 0->x, 1->2+x, 2->4+x(mod 5), 3->1+x, 4->3+x.

Состояние 0 означает, что введенное до сих пор число делится на 5. Оно же является и начальным.

Здравствуйте, ZNad, Вы писали:

ZN>Необходимо посмотрить детерминированный конечный автомат, который проверяет делимость числа (последовательность нулей и единиц должна начинаться с 1) по модулю 5.

Если число подаётся старшими разрядами вперёд, то каждый новый символ — это переход от числа X[k] = x[1]...x[k] к X[k+1] = X*b+x[k+1], где b — основание системы счисления.
В конце получаем число x[1]...x[n]
Отобразим в кольцо по модулю r (r = 5)

Пусть в позиции k мы имеем Y[k] = x[1]...x[k] mod r.
Тогда в позиции k+1 будет Y[k+1] = Y[k]*b+x[k] mod r.
При том, что X[0] = 0 и, соответственно, Y[0] = 0.

Нарисуем табличку (Y,x)->(Y). Это и будет таблица переходов КА.
Всего у нас есть r состояний: Y=0..r-1

---

Если же число подаётся младшими разрядами вперёд, то X[k+1] = X[k] + x[k+1]*b^(k+1).
Соответственно, Y[k+1] = Y[k] + x[k+1]*b^(k+1) mod r

Пусть последовательность B[k] = b^k mod r, т.е. B[k+1] = B[k]*b mod r.
Ясно, что раз мы в кольце по модулю, то эта последовательность зацикливается, так что автомат по-прежнему конечный.

Рисуем таблички: (B)->(B) и (Y,B,x)->(Y).
Объединяем их: ((Y,B),x)->(Y,B).
То есть, состоянием автомата является пара (Y,B), а общее количество состояний — r*l,
где l — количество разных значений B (логарифм нуля в конечном кольце), l<=r.