Является ли bin(n)bin(2^(k+1) * n + 1)^R контекстом бесплатно?

Question

bin - самое короткое число в двоичной системе

Является ли bin(n)bin(2^(k+1) * n + 1)^R контекстом бесплатно?

k, n принадлежит натуральным числам.

Я знаю, что bin(n)bin(n + 1)^R не зависит от контекста, но я не знаю, как решить bin(n)bin(2^(k+1) * n + 1)^R . Если контекстно-свободен, может ли кто-нибудь помочь мне построить контекстно-свободную грамматику?

Answer 1

Если предположить, x^R средства x наоборот, то вы ищете строки в виде

n1(many zeros)(n)^R

Так как "много нулей" в этом случае просто 0*регулярное выражение, вы можете адаптировать любую грамматику для n(n+1)^R на этот язык, и он по-прежнему будет контекстно-свободным

Давайте посмотрим на п =5, к =2

n = 101
2^(k+1) = 2^3 = 1000
1000 * 101 is 101000
101000 + 1 is 101001
101001^R is 100101

Последняя строка

n1(zeroes)n^R
101100101

Answer 2

Вопрос в том, является ли язык bin(n)bin(2^(k+1) * n + 1)^R не зависит от контекста я беру bin(n) означать двоичное представление натурального числа n без каких-либо ведущих нулей.

предполагать bin(n') = x, Вот, x является конечной строкой двоичных цифр, начинающейся с 1, Определим, как выглядит bin(2^(k+1) * n + 1). Во-первых, обратите внимание, что умножение числа на два добавляет ноль в конец двоичного представления этого числа; точно так же, как умножение на десять при использовании десятичной дроби. Умножение на 2 ^ (k + 1) добавит k + 1 нулей. Поскольку k - натуральное число, необходимо добавить хотя бы один ноль. При добавлении единицы к этому номеру младший значащий бит перевернется с 1 на 0. Конечный результат состоит в том, что bin(2^(k+1) * n + 1) = x(0^k)1,

Язык bin(n)bin(2^(k+1) * n + 1)^R состоит из строк в форме x(x(0^k)1)^R, Мы можем распространять ^R путем обращения каждой из соединенных подстрок и порядка объединения, чтобы увидеть, что эти строки имеют форму x1(0^k)(x^R), Мы замечаем, что самый внешний компонент этих строк начинается с произвольной двоичной строки x и заканчивается x^R; мы можем справиться с этим с помощью контекстно-свободной грамматики, так же, как и языки палиндромов. Самый внутренний компонент 1(0^k), который описывает обычный язык 10*; мы, безусловно, можем справиться с этим в CFG. CFG, который работает, является следующим:

S := 0S0 | 1S1 | T
T := T0 | 1

Основное понимание в получении этого заключается в определении формы (bin(2^(k+1) * x + 1)^R,