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

Возможно ли составить конечный детерминированный автомат, который допускает только целые числа (в двоичной системе счисления), являющиеся квадратами?

Например $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.

а вообще, как любое другое число, а не только квадраты - разложить побитно и рассматривать как сумму степеней двойки (0, 1, 10, 100, 1000 и т.д.)
В чем проблема-то?



Редактировалось 1 раз(а). Последний 28.02.2014 21:50.

То есть, если, допустим, если ещё несколько ограничить начальные условия до нахождения, к примеру, степеней 2-ки в потоке двоичных чисел, то однозначный алгоритм мог бы выглядеть так:

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

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



Редактировалось 1 раз(а). Последний 01.03.2014 09:22.

Цитата
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.

А если состояния означают не квадраты чисел, а что-то другое, тогда другое док-во нужно)