私は本当に助けが必要です。私はDFAを構築する100の例のようにしました。どんな助けでも大歓迎です。ブール式が真または偽であるかどうかを確認するDFAを設計する
私はいくつかのランダムなブール関数を持っています： f（a、b、c、d）=（a∨c）∧（（a∧b）∨（c↔d））と私は真であるすべての文字列を受け入れるDFA（バイナリでは3,7,8,11,12,13,14,15）、それ以外はすべて拒否されます。だから基本的には、これらの整数をバイナリ形式に変換して受け入れ、残りの整数を拒否するDFAが必要です。私はどうしたの？私は時を過ごすのに何時間も費やしました。この場合、どうやってトランジションテーブルを作るのですか？
もう一度、私を助けてくれてありがとう！ :)
私が問題を正しく理解していれば、入力は固定サイズであるという意味で「比較的簡単」という問題があります。これは、受け入れられる言語も有限であることを意味します。私は建設のスケッチを与えますが、それは比較的多数の州をもたらしますが、合理的なアイデアは使用しません。
真理値表で数式を調べます。評価する変数は4であり、これは可能な入力が2^4 = 16であることを意味します。
これらの入力は、16のルートからルート（これはDFAの初期状態）から16までの経路で構成されています。リーフは、それに通じるパスが真理値表でyesと評価される入力に対応する場合にのみ、終端ステートになります。
DFAによって有限言語が認識されることは常に可能であることに注意してください。言語内のすべての単語を受け入れ、これをDFAに変換するNDFAを構築します（詳細は複雑ですが、オートマトンは、this構成で保証されています）。
ありがとうございます。問題はこれが試験の仕事であることです。つまり、あなたはそれに5〜6分かかると思います。私は256パスの意思決定ツリーを作ってはいけません.NFAを構築してDFAに変換します。私はちょうどバイナリofcで3,7,8,11,12,13,14,15の数字を受け入れ、0,1,2,4,5、 6,9,10。 – Stenli
長すぎるソリューションを許可するパターンには、受け入れ、拒否するパターンがあると思いますか？明示的にすべてのパスを書き留めるのは少し時間がかかります。しかし、私は何とか入力の数を誤って計算しました。実際の数はより少なくなります。 – Codor
@stenil：上記の投稿が役に立つのなら、受け入れてupvoteしてください。多くの時間と労力が必要なため、受け取った返信を尊重してください。 – Billa
したがって、評価する数式は固定されていますが、問題の1つではありませんか？ DFAの入力は4つのブール値ですか？ – Codor
はい数式は固定されており、入力は正確に4つの値になります。それ以降は無視されます – Stenli