DFA для принятия всех двоичных строк в форме степени (не делится на ), т.е. для данного

9

Мы можем сформировать DFA, принимающий двоичные числа, делимые на n .

Например, DFA, принимающий двоичные числа, делимые на 2, может быть сформирован следующим образом:

введите описание изображения здесь

Аналогично, DFA, принимающий двоичные числа, делимые на 3, может быть сформирован следующим образом: введите описание изображения здесь

Мы можем следовать четко определенной процедуре для формирования этих типов DFA. Однако может ли быть какая-то четко определенная процедура или лучше сказать логика для формирования DFA, принимающих числа вида nk ?

Например, давайте рассмотрим DFA, принимающий все числа вида . Этот язык будет , поэтому будет иметь регулярное выражение . Мы можем сформировать DFA следующим образом: 2k{1,10,100,1000,...}10введите описание изображения здесь

Я пытался сформировать DFA для и подобных? Но не смог этого сделать. Или это просто то, что его шаблон из двоичных эквивалентов, который позволял создавать DFA, и мы не можем сформировать DFA, принимая все двоичные числа в форме для конкретных ?3k2nnkn

Maha
источник
Я думаю, что у вас есть ответ здесь
3
@ Рафаэль, нет, это для кратных ; это о полномочиях . nn
DW
Например, могут быть другие «близлежащие» функции, которые могут быть вычислены с помощью DFA, такие как делимость степеней и т. д. Например, функция Коллатца (которая включает в себя степени 3) может быть вычислена преобразователем конечных состояний и т. д.
vzn

Ответы:

10

Вот быстрое и грязное доказательство с использованием леммы о накачке, что язык состоящий из в двоичном виде, не является регулярным (примечание: он является регулярным, если представлен в троичной форме, поэтому представление важно).L3n

Я буду использовать запись из статьи Википедии о лемме Pumping . Предположим для противоречия, что регулярно. Пусть - любая строка с (длина накачки). Используя лемму накачки, напишите с и для всех . Я напишу , и также для числовых значений соответствующих частей, идля их длины в . Численно мы имеем для некоторогоLwL|w|pw=xyz|y|1,|xy|pi0 xyizLxyz|x|,|y|,|z|ww=3k0k0N, В то же время мы имеем численно . Таким образом, мы имеемw=z+2|z|y+2|z|+|y|x

z+2|z|y+2|z|+|y|x=3k0

Теперь давайте прокачаем чтобы получить для всехwi0

z+2|z|y(j=0i1(2|y|)j)+2|z|+i|y|x=3ki,

где . Упрощение мы получаем дляk0<k1<k2<i1

z+2|z|y(2i|y|1)/(2|y|1)+2|z|+i|y|x=3ki.

Пусть . Тогда у нас естьC=z2|z|y/(2|y|1)

3ki=2|z|+i|y|y/(2|y|1)+2|z|+i|y|x+C.

Теперь обратите внимание, что

3ki3ki1=(2|y|1)(3ki1C).

Следовательно, мы имеемОбратите внимание, что . Таким образом, с одной стороны, абсолютное значение в правой части возрастает, по крайней мере, на , что уходит в бесконечность с . С другой стороны, не зависит от и является константой. Это дает противоречие.C(2|y|1)=3ki1(2|y|3kiki1).|2|y|3kiki1|13ki1iC(2|y|1)i

Денис Панкратов
источник
Не могли бы вы немного рассказать, почему это правда? Я спрашиваю, потому что одно это неравенство может быть использовано для достижения противоречия: , умножив обе стороны на , мы получим , таким образом, , что является противоречием (по причине, указанной в вашем доказательстве). |2|y|3kiki1|1|2|y|3kiki1|13ki1|3ki12|y|3ki|3ki1|C(2|y|1)|3ki1
Антон Трунов
1
Так как , у нас есть четное и нечетное. Их разность нечетная, поэтому по крайней мере 1 в абсолютном значении. |y|12|y|3kiki1
Денис Панкратов
10

Один из способов увидеть, что это невозможно для (например) языка степеней в двоичном разложении, - рассмотреть производящую функциюL3

k=0nkzk ,

где есть число слов длины в . Эта функция называется рациональным, то есть фактор многочлены, для любого регулярного . В частности, числа удовлетворяют линейному повторению для некоторых и .nkkLp(x)/q(x)Lnknk+p+1=a0nk++apnk+ppNa1,,apZ

С другой стороны, поскольку является иррациональным числом в , мы получаем, что для всех и последовательность не является периодическим. Это дает противоречие, поскольку после не более чем шагов значения должны повторяться, и повторение может привести к периодическому поведению.log2(3)(1,2)nk{0,1}k(nk)k12pnk,,nk+p

Клаус Дрегер
источник
8

Полный ответ на ваш вопрос дает (трудный) результат Кобэма [2].

Для заданной базы нумерации набор натуральных чисел называется распознаваемым, если представления в базе его элементов образуют регулярный язык в алфавите . Таким образом, как вы заметили, набор степеней является распознаваемым, поскольку он представлен регулярным набором в алфавите . Аналогично, набор степеней является узнаваемым - он соответствует регулярному набору - и набор степеней равенbbb{0,1,,b1}2210{0,1}421(00)33- узнаваемый - он соответствует регулярному набору над алфавитом .10{0,1,2}

Множество натуральных чисел называется в конечном итоге периодическим, если оно представляет собой конечное объединение арифметических прогрессий.

Два основания называются мультипликативно зависимыми, если существует такое что и являются степенями : например, и мультипликативно зависимы, так как и .b,c>1r>1bcr8328=238=25

Теорема Кобхэма. Пусть и два мультипликативно независимых основания. Если набор является неузнаваемым и -распознаваемым, то он в конечном счете периодический.bcbc

В частности, пусть будет множеством степеней . Мы видели, что это узнаваемый. Если бы это было также -recognizable, было бы в конечном счете периодично, что, безусловно , не относится к .S332S

Теорема Кобэма привела ко многим удивительным обобщениям и разработкам. Я рекомендую опрос [1], если вы заинтересованы.

[1] В. Брюер, Г. Хансель, К. Мишо, Р. Виллемер, Логические и узнаваемые наборы целых чисел, Journées Montoises (Mons, 1992). Bull. Belg. Математика Soc. Саймон Стевин 1 (1994), нет. 2, 191-238. Исправление в №. 4, 577.p

[2] А. Кобхэм, Унифицированные последовательности тегов, Матем. Теория систем 6 (1972), 164-192.

J.-E. Штырь
источник
Не могли бы вы исправить ссылки, пожалуйста? Теперь они оба пронумерованы [1] и [1].
Антон Трунов