конечный автомат для проверки делимости на 5 в двоичном коде

[pincher]

На вход автомату подается двоичное целое число, т.е. Т. е. входной алфавит 1 и 0.
Я бы взял за состояния автомата остатки от деления на 5. Вход и выход, очевидно, состояние 0. Например мы находимся в состоянии 0 и получаем на вход 1, остаток от деления единицы на 5 = 1, переходим в состояние 1. Дальше думаю сами сможете продолжить.

ЗЫ я что-то дату не посмотрел. Извиняюсь что старую тему поднял, но тем не менее, не считаю что предыдущие темы помогут решить задачу.
Напишите пожалуйста в личку почему нельзя создавать темы в данном разделе.

[Профессор Снэйп]

-- Пт фев 26, 2010 22:55:40 --

Думаю, тема созрела для выкладывания готового решения. Если не прав, пусть модераторы меня поправят!

[terminator-II]

ненавижу дискретку

[Профессор Снэйп]

Nerex в сообщении #88115 писал(а):

Люди.... АУ мне нужен граф или таблица конечного автомата, а не рассуждения как лучше делить число в двоичной системе на 5.

Халявы здесь нет. На этом форуме не решают задачи за вас (ну, или решают, через два года после того, как задача сформулирована)

-- Пт фев 26, 2010 23:04:51 --

незваный гость в сообщении #88106 писал(а):

Всем любителям признаков делимости: нарисовали бы вы автомат для, скажем, 23. Или 37… Нет, теоретически это можно. Если бумажка достаточного размера.

Угадайте, делимость на какое число проверяет этот автомат?

P. S. С полмесяца назад открыл для себя JFLAP и целый день забавлялся этой программой, в неописуемом восторге рисуя самые разные автоматы. Потом, правда, надоело. Эх, почему всё хорошее так быстро надоедает?

-- Пт фев 26, 2010 23:09:07 --

Вот, кстати, интересная вещь. Оба автомата, диаграммы которых приведены выше, рисовались вполне осмысленно. В них была немеренная куча состояний (несколько десятков). Потом они минимизировались. И вот минимизированные автоматы... нет, они работают абсолютно правильно. Но понять логику их построения, глядя на готовую диаграмму --- задача не для слабонервных гениев! В том же автомате, проверяющем делимость на $5$, попробуйте понять, какое состояние за что отвечает. У меня не получилось

-- Пт фев 26, 2010 23:13:17 --

Ещё несколько задач про автоматы. Задача из первого сообщения осенью здесь обсуждалась

[pincher]

Цитата:

Угадайте, делимость на какое число проверяет этот автомат?

7)

Цитата:

В том же автомате, проверяющем делимость на $5$, попробуйте понять, какое состояние за что отвечает. У меня не получилось

Ветку из начала с 0 не рассматриваем, так как она всего лишь отбрасывает числа начинающие с 0 например 0, 00, 01010...

во вторую ветку идем по 1 в q3. Очевидно что остаток 1.
Из q3 по 0 идем в q2, получаем 10, остаток 2.
и т.д.

переопределим состояния соответствующим остаткам и в итоге получим:
q4=0 (так же можно определить по петле с входным символом 0)
q3=1
q2=2
q0=3
q1=4

[Профессор Снэйп]

pincher в сообщении #292809 писал(а):

q3=1
q2=2
q0=3

$2 \cdot 1 + 0 = 2$
$2 \cdot 1 + 1 = 3$
$q_3 \to^0 q_2$, $q_3 \to^1 q_0$

Понял наконец-то, как это работает! Во я тупой, как пробка

-- Сб фев 27, 2010 02:36:51 --

pincher в сообщении #292809 писал(а):

Ветку из начала с 0 не рассматриваем, так как она всего лишь отбрасывает числа начинающие с 0 например 0, 00, 01010...

$0$ она как раз не отбрасывает