Мы можем сформировать DFA, принимающий двоичные числа, делимые на .
Например, DFA, принимающий двоичные числа, делимые на 2, может быть сформирован следующим образом:
Аналогично, DFA, принимающий двоичные числа, делимые на 3, может быть сформирован следующим образом:
Мы можем следовать четко определенной процедуре для формирования этих типов DFA. Однако может ли быть какая-то четко определенная процедура или лучше сказать логика для формирования DFA, принимающих числа вида ?
Например, давайте рассмотрим DFA, принимающий все числа вида . Этот язык будет , поэтому будет иметь регулярное выражение . Мы можем сформировать DFA следующим образом:
Я пытался сформировать DFA для и подобных? Но не смог этого сделать. Или это просто то, что его шаблон из двоичных эквивалентов, который позволял создавать DFA, и мы не можем сформировать DFA, принимая все двоичные числа в форме для конкретных ?
Ответы:
Вот быстрое и грязное доказательство с использованием леммы о накачке, что язык состоящий из в двоичном виде, не является регулярным (примечание: он является регулярным, если представлен в троичной форме, поэтому представление важно).L 3n
Я буду использовать запись из статьи Википедии о лемме Pumping . Предположим для противоречия, что регулярно. Пусть - любая строка с (длина накачки). Используя лемму накачки, напишите с и для всех . Я напишу , и также для числовых значений соответствующих частей, идля их длины в . Численно мы имеем для некоторогоL w∈L |w|≥p w=xyz |y|≥1,|xy|≤p i≥0 xyiz∈L x y z |x|,|y|,|z| w w=3k0 k0∈N , В то же время мы имеем численно . Таким образом, мы имеемw=z+2|z|y+2|z|+|y|x
Теперь давайте прокачаем чтобы получить для всехw i≥0
где . Упрощение мы получаем дляk0<k1<k2<… i≥1
Пусть . Тогда у нас естьC=z−2|z|y/(2|y|−1)
Теперь обратите внимание, что
Следовательно, мы имеемОбратите внимание, что . Таким образом, с одной стороны, абсолютное значение в правой части возрастает, по крайней мере, на , что уходит в бесконечность с . С другой стороны, не зависит от и является константой. Это дает противоречие.C(2|y|−1)=3ki−1(2|y|−3ki−ki−1). |2|y|−3ki−ki−1|≥1 3ki−1 i C(2|y|−1) i
источник
Один из способов увидеть, что это невозможно для (например) языка степеней в двоичном разложении, - рассмотреть производящую функциюL 3
где есть число слов длины в . Эта функция называется рациональным, то есть фактор многочлены, для любого регулярного . В частности, числа удовлетворяют линейному повторению для некоторых и .nk k L p(x)/q(x) L nk nk+p+1=a0nk+⋯+apnk+p p∈N a1,…,ap∈Z
С другой стороны, поскольку является иррациональным числом в , мы получаем, что для всех и последовательность не является периодическим. Это дает противоречие, поскольку после не более чем шагов значения должны повторяться, и повторение может привести к периодическому поведению.log2(3) (1,2) nk∈{0,1} k (nk)k≥1 2p nk,…,nk+p
источник
Полный ответ на ваш вопрос дает (трудный) результат Кобэма [2].
Для заданной базы нумерации набор натуральных чисел называется распознаваемым, если представления в базе его элементов образуют регулярный язык в алфавите . Таким образом, как вы заметили, набор степеней является распознаваемым, поскольку он представлен регулярным набором в алфавите . Аналогично, набор степеней является узнаваемым - он соответствует регулярному набору - и набор степеней равенb b b {0,1,⋯,b−1} 2 2 10∗ {0,1} 4 2 1(00)∗ 3 3 - узнаваемый - он соответствует регулярному набору над алфавитом .10∗ {0,1,2}
Множество натуральных чисел называется в конечном итоге периодическим, если оно представляет собой конечное объединение арифметических прогрессий.
Два основания называются мультипликативно зависимыми, если существует такое что и являются степенями : например, и мультипликативно зависимы, так как и .b,c>1 r>1 b c r 8 32 8=23 8=25
Теорема Кобхэма. Пусть и два мультипликативно независимых основания. Если набор является неузнаваемым и -распознаваемым, то он в конечном счете периодический.b c b c
В частности, пусть будет множеством степеней . Мы видели, что это узнаваемый. Если бы это было также -recognizable, было бы в конечном счете периодично, что, безусловно , не относится к .S 3 3 2 S
Теорема Кобэма привела ко многим удивительным обобщениям и разработкам. Я рекомендую опрос [1], если вы заинтересованы.
[1] В. Брюер, Г. Хансель, К. Мишо, Р. Виллемер, Логические и узнаваемые наборы целых чисел, Journées Montoises (Mons, 1992). Bull. Belg. Математика Soc. Саймон Стевин 1 (1994), нет. 2, 191-238. Исправление в №. 4, 577.p
[2] А. Кобхэм, Унифицированные последовательности тегов, Матем. Теория систем 6 (1972), 164-192.
источник