查找二进制数为1的5可以被5整除的语法 [英] Find a grammar of binary number divisible by 5 with 1 as MSB
问题描述
我如何找到二进制数为5且可被1除为MSB的语法，并找到L的逆数？
因此，我需要一个生成如下数字的语法..
5 = 101
10 = 1010
15 = 1111
20 = 10100
25 = 110011
等等
我假设这是家庭作业，您只需要一个提示即可。
让我们考虑一个类似的问题，但是以10为底。我们如何为3整除的数字编写CFG。
乍一看，这似乎不太可能，但实际上非常简单。我们首先观察到：
10 k &conb;&conb; 1（mod 3）对于任何非负整数 k 。
现在考虑一个整数 dδ ，其中 d 是一个十进制数字，而δ 是一个（可能是空）十进制数字序列。我们将 |&delta || 的长度写为δ 。很明显：
d× 10 |δ | ≅ d（mod 3），因为 10 |δ | ≅ 1（mod 3）。
但是 dδ = d× 10 |δ | +δ
所以 dδ ≅ d +δ （mod 3）。
现在假设我们有三种语言， L 0 ， L 1 和 L 2 ，其中 L i 是所有十进制数字的语言，它们是 i mod 3 。
我将通过写集合包含语句来滥用符号，就好像它们是语法产品一样，使语言和语法混乱。原谅我。
对于单个数字，我们可以定义：
D 0 → 0 | 3 | 6 | 9
D 1 → 1 | 4 | 7
D 2 → 2 | 5 | 8
然后我们有：
L 0 → D 0
L 1 → D 1
L 2 → D 2
通过上述算术标识，我们还具有： p>
L 0 → D 0 L 0 | D 1 L 2 | D 2 L 1
L 1 → D 0 L 1 | D 1 L 0 | D 2 L 2
L 2 → D 0 L 2 | D 1 L 1 | D 2 L 0
那是CFG，所以我们完成了。 （嗯，差不多完成了。证明 L 0 ⋃ L 1 ⋃ L 2 是字母 {0，1，2， 3、4、5、6、7、8、9} ，但是通过对字符串的长度进行归纳就很容易。）
实际上，不仅是 L i 上下文无关的语言；它们实际上是常规语言。因此，有一个等效于它们每个的正则表达式。例如，我相信 L 0 是：
（ D 0 | D 2 D 0 * D 1 |（ D 1 | D 2 D 0 * D 2 ）（ D 0 | D 1 D 0 * D 2 ）*（ D 2 | D 1 D 0 * D 1 ））*
现在，如何对可被5整除的二进制数重复呢？
How can I find a grammar of binary number divisible by 5 with 1 as MSB and find the reversal of L
So, I need a grammar that generates numbers like..
5 = 101
10 = 1010
15 = 1111
20 = 10100
25 = 110011
and so on
I'm assuming this is homework and you just want a hint.
Let's consider a somewhat similar question, but in base 10. How can we write a CFG for numbers divisible by 3.
At first glance, this seems unlikely, but it's actually pretty simple. We start with the observation that:
10k ≅ 1 (mod 3) for any non-negative integer k.
Now consider an integer dδ, where d is a decimal digit and δ is a (possibly empty) sequence of decimal digits. We write |δ| for the length of δ. It's clear that:
d × 10|δ| ≅ d (mod 3), since 10|δ| ≅ 1 (mod 3).
But dδ = d × 10|δ| + δ
So dδ ≅ d + δ (mod 3).
Now suppose we have three languages, L0, L1 and L2, where Li is the language of all decimal numbers which are i mod 3.
I'm going to abuse notation by writing set inclusion statements as though they were grammatical productions, confusing languages and grammars. Forgive me. It seems easier to read if your focus is on CFGs.
For single digit numbers, we can define:
D0 → 0 | 3 | 6 | 9
D1 → 1 | 4 | 7
D2 → 2 | 5 | 8
and then we have:
L0 → D0
L1 → D1
L2 → D2
By the above arithmetic identities, we also have:
L0 → D0 L0 | D1 L2 | D2 L1
L1 → D0 L1 | D1 L0 | D2 L2
L2 → D0 L2 | D1 L1 | D2 L0
That's a CFG, so we're done. (Well, almost done. It would be useful to prove that L0 ⋃ L1 ⋃ L2 is the set of all strings in the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, but that's easy by induction on the length of the string.)
In fact, not only are Li context-free languages; they are actually regular languages. So there is a regular expression equivalent to each of them. For example, I believe that L0 is:
(D0|D2D0*D1|(D1|D2D0*D2)(D0|D1D0*D2)*(D2|D1D0*D1))*
Now, how can this be repeated for binary numbers divisible by 5?
这篇关于查找二进制数为1的5可以被5整除的语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
