計算理論＊正規文法

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

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

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

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

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

No.2 回答者： rabbit_cat 回答日時： 2007/04/19 23:35

＞正規文法であることの証明はどうやって行えば良いのでしょうか…。

実際に正則表現（正規表現）で書いてみればよいです。

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

この回答へのお礼

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

お礼日時：2007/04/21 12:48

No.1 回答者： edomin2004 回答日時： 2007/04/19 21:50

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

なるほど…。

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

この回答への補足

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

補足日時：2007/04/19 21:51