MSB を 1 として 5 で割り切れる 2 進数の文法を見つけ、L の反転を見つけるにはどうすればよいですか?
だから、私は..のような数字を生成する文法が必要です.
5 = 101
10 = 1010
15 = 1111
20 = 10100
25 = 110011
等々
質問する
2225 次
2 に答える
2
これは宿題で、ヒントが欲しいだけだと思います。
少し似た質問を考えてみましょう。ただし、基数は 10 です。3 で割り切れる数の CFG をどのように書くことができますか。
一見、ありそうにないように思えますが、実際には非常に単純です。次の観察から始めます。
10k ≅ 1 (mod 3)負でない整数の場合k。
ここdδで、dは 10 進数で、δは (おそらく空の) 10 進数のシーケンスです。|δ|の長さで書きδます。次のことは明らかです。
d × 10|δ| ≅ d (mod 3)、以来。10|δ| ≅ 1 (mod 3)
しかしdδ = d × 10|δ| + δ
だからdδ ≅ d + δ (mod 3)。
ここで、との 3 つの言語があるとします。ここで、は であるすべての 10 進数の言語です。L0L1L2Lii mod 3
セットの包含ステートメントを、あたかも文法上の生成物であるかのように記述し、言語と文法を混乱させることで、表記法を乱用します。私を許して。CFG に焦点を当てた方が読みやすいようです。
1 桁の数値の場合、次のように定義できます。
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 です。これで完了です。(まあ、ほぼ完了です。が alphabet のすべての文字列の集合であることを証明できれば便利ですが、文字列の長さの帰納法によって簡単に証明できます。)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 で割り切れる 2 進数に対してどのように繰り返すことができるでしょうか?
于 2014-06-15T02:24:03.200 に答える
0
5 の偶数倍数 (10,20,30...) をすべて与える文法を簡単に手に入れることができます。奇数倍..あなたは
これが役立つことを願っています-おそらく最も賢い方法ではありません
于 2014-06-14T11:43:51.693 に答える