Является ли 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

Вопрос в том, является ли язык 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.

Answer 2

Если x^R означает x в обратном порядке, то вы ищете строки в форме

n1(many zeros)(n)^R

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

Давайте рассмотрим n = 5, k = 2

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

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

1014 *