如何找到可被 5 整除且 MSB 为 1 的二进制数语法并找到 L 的反转
所以，我需要一个生成数字的语法，比如..
5 = 101
10 = 1010
15 = 1111
20 = 10100
25 = 110011
等等
问问题
2225 次
2 回答
2
我假设这是家庭作业，你只是想要一个提示。
让我们考虑一个有点类似的问题，但以 10 为底。我们如何为可被 3 整除的数字编写 CFG。
乍一看，这似乎不太可能，但实际上非常简单。我们从以下观察开始：
10k ≅ 1 (mod 3)对于任何非负整数k。
现在考虑一个整数dδ，其中d是一个十进制数字，并且δ是一个（可能为空的）十进制数字序列。我们写|δ|的长度为δ。很明显：
d × 10|δ| ≅ d (mod 3), 因为.10|δ| ≅ 1 (mod 3)
但dδ = d × 10|δ| + δ
所以dδ ≅ d + δ (mod 3)。
现在假设我们有三种语言，和，其中所有十进制数的语言是。L0L1L2Lii mod 3
我将通过编写集合包含语句来滥用符号，就好像它们是语法产生一样，混淆了语言和语法。对不起。如果您的重点是 CFG，它似乎更容易阅读。
对于个位数，我们可以定义：
D0 → 0 | 3 | 6 | 9
D1 → 1 | 4 | 7
D2 → 2 | 5 | 8
然后我们有：
L0 → D0
L1 → D1
L2 → D2
通过上述算术恒等式，我们还有：
L0 → D0 L0 | D1 L2 | D2 L1
L1 → D0 L1 | D1 L0 | D2 L2
L2 → D0 L2 | D1 L1 | D2 L0
这是一个 CFG，所以我们完成了。（嗯，差不多完成了。证明它是字母表中所有字符串的集合会很有用，但是通过对字符串长度的归纳很容易。）L0 ⋃ L1 ⋃ L2{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
事实上，不仅是上下文无关的语言，还有上下文无关的语言。它们实际上是常规语言。所以有一个等价于它们的正则表达式。例如，我认为是：LiL0
(D0|D2D0*D1|(D1|D2D0*D2)(D0|D1D0*D2)*(D2|D1D0*D1))*
现在，对于可被 5 整除的二进制数，如何重复此操作？
于 2014-06-15T02:24:03.200 回答
0
你可以很容易地得到一个语法工具，现在它会给你所有的 5 (10,20,30...)奇数乘法..你会
希望这会有所帮助 - 虽然它可能不是最聪明的方法
于 2014-06-14T11:43:51.693 回答