Design DFA that checks wheter a boolean formula is true or false

Question

I really need some help guys, I made like 100 examples of constucting DFA's and I'm stuck with this one. Any help will be much appreciated.

So I have some random boolean function, for example: f(a,b,c,d) = (a∨c)∧((a∧b)∨(c ↔ d)) and I should make a DFA which accepts all of the strings which are true {3,7,8,11,12,13,14,15 in binary) everything else should be rejected. So basicly I need a DFA who converts these integers into binary form and accepts them, rejecting the other integers left. How I make that? I spent hours trying to quess the states.. How you make a transition table in this case?

Once again, thank you for helping me ! :)

Answer 1

If I understood the question correctly, the problem is 'relatively easy' in the sense that the input is of fixed size, which means that the accepted language is also finite. I will give a sketch of the construction, which will result in a relatively large number of states but does not use a compilcated idea.

Examine the formula with a truth value table. There are 4 variables to be evaluated, which means that there are 2^4 = 16 possible inputs.

Arrange these inputs in a decision tree consisting out of 16 paths from the root (which is the initial state of the DFA) to 16 leaves. A leaf is a terminal state if and only if the path leading to it corresponds to an input which evaluates to yes in the truth value table.

Note that it is always possible for a finite language to be recognized by a DFA - construct a NDFA which accepts every single word in the language and convert this one to a DFA (which can be complex in detail, but such an automaton is guaranteed to exist by this construction).