偶数が0で1の数が3の倍数であるすべてのバイナリ文字列を受け入れるFA

Question

この質問はWayne Goddardによる計算理論の紹介（質問1.17）の第1章演習から直接得られます。

最初は、入力内の0の数が偶数であることを保証するための2つの別個のDFAを作成することを考えました。入力内の1の数が3で割り切れることを保証するためにもう1つのDFAを1つの言語私が思っていたよりも難しい仕事になるのです。誰かが私を正しい方向に向けることができれば大変感謝しています。

私は新しいシンボルを観察した後、以前に取得した0と1に関するデータを確実に保持するために、論理的なステップを構築するのが難しいです。

Answer 1

2つの異なるDFAを作成して組み合わせることをお勧めします。 2つのDFAから始まり、本質的に両方を同時に実行する1つのDFAを構築したいと考えています。これはちょうどそれをするproduct constructionを使用する素晴らしい時間です。この考え方は、状態が最初のDFAからの状態と2番目の状態からの状態のペアに対応する新しいDFAを構築することです。あなたがpowersetの構築に精通しているなら、あなたはこの構築がかなり簡単に手に入ります。直感はかなり似ています。