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的任何语法都适应这种语言，它仍然是无上下文的。

我们来看看n = 5，k = 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会在该数字的二进制表示的末尾添加零;与使用十进制时乘以十相同。乘以2 ^（k + 1）将增加k + 1个零。因为k是自然数，所以必须至少添加一个零。在这个数字上加一个会将最低有效位从0翻转到1.最终结果是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的形式。