計算理論＊正規文法

質問

4で割れる2進数…を表す？正規文法を作るという課題を出されたのですが良く分かりません。

まず、どうやって正規文法を作るのかも分からないです(^_^;)

正規文法と文脈自由文法の違いが理解できなくて(>_<)

あと、文脈自由文法であることの証明は本などで見たのですが、正規文法であることの証明はどうやって行えば良いのでしょうか…。

「計算理論の基礎」という分厚い本を見ているのですが…(/_;)

回答No.2

rabbit_cat

＞正規文法であることの証明はどうやって行えば良いのでしょうか…。
実際に正則表現（正規表現）で書いてみればよいです。

＞どこに注目すれば良いか分かりません(^_^;)
下２桁が常に０ですね。

お礼

正規表現で書けるから正規文法…って言っちゃって良いんですか？？
証明の場合です。

回答No.1

noname#77845

「どうやって正規文法を作るのかも分からない」
なるほど…。

では、「4で割れる2進数」はどういう２進数か判りますか？

補足

4 → 00100
8 → 01000
12 → 01100
16 → 10000
とかですよね…
どこに注目すれば良いか分かりません(^_^;)
2bitシフトできる…とかしか思い浮かばないですorz