Конечный детерминированный автомат

Автор темы dmgr94 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеКниги по математике и экономике в добрые руки!10.08.2023 09:45
Форумы Список тем Новая тема
28.02.2014 21:19
dmgr94
Конечный детерминированный автомат
Возможно ли составить конечный детерминированный автомат, который допускает только целые числа (в двоичной системе счисления), являющиеся квадратами?

Например $0_2=0^2_{10}, 1_2=1^2_{10}, 100_2=2^2_{10}, 1001_2=3^2_{10}, 10000_2=4^2_{10}, 11001_2=5^2_{10}$, и т. д.

Пробовал использовать алгоритм извлечения корня столбиком - не получается...



Редактировалось 2 раз(а). Последний 01.03.2014 00:37.
Ответить Цитировать
28.02.2014 21:34
alexo2
а 10 - это квадрат чего?..
.
Ответить Цитировать
28.02.2014 21:46
alexo2
..
а вообще, как любое другое число, а не только квадраты - разложить побитно и рассматривать как сумму степеней двойки (0, 1, 10, 100, 1000 и т.д.)
В чем проблема-то?



Редактировалось 1 раз(а). Последний 28.02.2014 21:50.
Ответить Цитировать
01.03.2014 00:35
dmgr94
Возможно вы не поняли.
Я имею ввиду возможность построения конечного детерминированного автомата. Числа представляются как строка из нулей и единиц и читаются автоматом посимвольно слева направо.

http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82

P. S. $10$ - я ошибся, хотел написать $100_2$, то есть $4$.



Редактировалось 2 раз(а). Последний 01.03.2014 00:39.
Ответить Цитировать
01.03.2014 08:08
alexo2
//
То есть, если, допустим, если ещё несколько ограничить начальные условия до нахождения, к примеру, степеней 2-ки в потоке двоичных чисел, то однозначный алгоритм мог бы выглядеть так:

начиная с младшего разряда проверять на "true", то есть пропускать 0 и искать первую 1-цу. Во время алгоритма работает также поразрядный счетчик, который инкрементируется при каждом нуле на 1-цу. Как только она нашлась, - проверить - "не закончилось ли число"? То есть, нет ли "более старших" значащих разрядов. Если найдена 1 единица в числе, и старших значащих разрядов нет, - то по значению счетчика определить степень.. (Хотя в задаваемом начальными условиями конечном автомате определение степени - это уже "излишество" и, в общем-то, задача возможно для другого алгоритма).

Если что-то типа такого, - то сомнительно, что возможно создать однозначный алгоритм в соответствии с исходными условиями - для квадратов любого числа. Так как можно манипулировать только двоичной логикой (а в конкретном случае - только порядковыми номерами разрядов и проверкой состояния), то нужно сначала найти однозначную зависимость между степенями двойки и степенями любых чисел.



Редактировалось 1 раз(а). Последний 01.03.2014 09:22.
Ответить Цитировать
01.03.2014 09:10
yog-urt
...
$ n^2= 1+3+...+(2n-1) $



Редактировалось 1 раз(а). Последний 01.03.2014 10:18.
Ответить Цитировать
01.03.2014 21:11
dmgr94
нет никаких счетчиков
Цитата
alexo2
То есть, если, допустим, если ещё несколько ограничить начальные условия до нахождения, к примеру, степеней 2-ки в потоке двоичных чисел, то однозначный алгоритм мог бы выглядеть так:

начиная с младшего разряда проверять на "true", то есть пропускать 0 и искать первую 1-цу. Во время алгоритма работает также поразрядный счетчик, который инкрементируется при каждом нуле на 1-цу. Как только она нашлась, - проверить - "не закончилось ли число"? То есть, нет ли "более старших" значащих разрядов. Если найдена 1 единица в числе, и старших значащих разрядов нет, - то по значению счетчика определить степень.. (Хотя в задаваемом начальными условиями конечном автомате определение степени - это уже "излишество" и, в общем-то, задача возможно для другого алгоритма).

Если что-то типа такого, - то сомнительно, что возможно создать однозначный алгоритм в соответствии с исходными условиями - для квадратов любого числа. Так как можно манипулировать только двоичной логикой (а в конкретном случае - только порядковыми номерами разрядов и проверкой состояния), то нужно сначала найти однозначную зависимость между степенями двойки и степенями любых чисел.

В конечном автомате нет никаких счетчиков. Можно только переходить из одного состояния в другое в зависимости от текущего состояния и текущего символа во входной строке.

Я составил автомат, проверяющий, является ли степень двойки квадратом.
http://savepic.su/4140277.png

Цитата
yog-urt
$ n^2= 1+3+...+(2n-1) $

Как эту формулу я применю в автомате? Там нет никаких арифметических операций!



Редактировалось 1 раз(а). Последний 01.03.2014 21:15.
Ответить Цитировать
02.03.2014 13:40
yog-urt
...
Конечного автомата с такими функциями (в соответствии с постановкой задачи), как я думаю, не существует.
Схема доказательства. Пусть $ s_i $ – некоторое состояние, идентифицирующее квадрат некоторого числа и имеется цепочка из $ s_i $ в $ s_i $. Тогда переход по цепочке соответствует рекуррентному соотношению, определяющему квадраты чисел:
$ a^2_{j+1}=a^2_j2^m+k ( 0 \le k<2^m), j=0,1,... $ .
Результат следует из ответов на вопросы:
- при каких значениях $ m, k $ значения $ a^2_j $ , определенные этим соотношением, являются квадратами натуральных чисел при всех $ j $ ;
- можно ли конечным числом таких соотношений (при допустимых значениях $ m, k $ ) перечислить квадраты всех натуральных чисел.
Ответить Цитировать
02.03.2014 16:39
dmgr94
.
А если состояния означают не квадраты чисел, а что-то другое, тогда другое док-во нужно)
Ответить Цитировать
02.03.2014 21:52
yog-urt
... детали доказательств
Такая схема доказательства может работать в разных случаях. Однако нужно учитывать некоторые детали, которые в данном случае решаются просто. В частности, рассмотреть возможность цепочек с петлями, при этом будет бесконечное число цепочек и тогда класс рекуррентных функций, определенных переходами $ s_i \to s_i $, не будет таким простым. Кроме того, могут возникнуть сложности как в решении совокупности (по j=1,2,...) уравнений относительно параметров $ m, k, $ так и в определении возможности перечисления множества идентифицируемых чисел рекуррентными соотношениями с допустимыми значениями $ m, k $. При решении более сложных задач такого типа может оказаться эффективным аппарат производящих функций.
Ответить Цитировать
« Следующая тема   Предыдущая тема »
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти