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 。如果是上下文无关的，有人可以帮我建立上下文无关的语法吗？
问问题
204 次
2 回答
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
于 2019-02-11T13:51:22.050 回答
0
问题是语言是否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 是自然数，所以必须至少添加一个零。向这个数字加 1 会将最低有效位从 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.
于 2019-02-13T17:24:04.357 回答