DFA for Boolean Formula Let $ f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function.
Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n  \}$
The subsets $S_{f}$ are viewed below as languages consisting of bit-strings of length n.


*

*Let $S_{f}$ be non-empty. Then any DFA accepting exactly the language $S_{f}$ must have at least n+2 states.

*Prove that any language $S_{f}$ has DFA with at most $2^{n+1}$ states.

*Prove that any language $S_{f}$ has DFA with just one final accepting state.

*Let $n\geq 5$. Prove that there exists a boolean function $f$ such that any DFA accepting exactly $S_{f}$ has at least ${2^{n-2}}/\left({n-2}\right)$ states.

My question is about 2:
I am using the trivial case where $S_{f}=\{(1,0)\}$ , then according to the rules mentioned in 2, the states of my DFA are at most 8. Note that my trivial $S_{f}$ satisfies the condition $f\left(\ 1 , 0 \right)=1 \equiv 1 \vee 0 = 1 $
I do not see 8 states. I see from a truth table that the combinations {(0,1), (1,1), (1,0)} yield 1. 
I don't understand where 8 states come from. Help please. 

Question for 3:
Isn't a DFA by definition a machine that accepts only one state. 
What is there to prove? How to prove it? The definition states it. Am I wrong? 

Question 4:
Say I have a $f(1 \vee 0 \vee 0 \vee 0 \vee 0)$, by Myhill Nerode I can find the equivalence of classes and reduce the n=5 in states graphically to something as 
-->$q_{1}$--1-->$q_{2}$ --0--> $q_{3}$--0--->$q_{2}$ and from $q_{2}$--0-->$q_{3}$--garbage-->$q_{4}$
This yields 4 states, but the formula returns for $n=5$ it should have at least $2.\bar{6}$ states.
What am I doing wrong? Thank you.
 A: Recall that a DFA is a $5$-tuple $M = ( Q , \Sigma , \delta , q_0 , F )$ where


*

*$Q$ is the set of states of $M$;

*$\Sigma$ is the underlying alphabet of $M$;

*$\delta : Q \times \Sigma \to Q$ is the transition function;

*$q_0 \in Q$ is the starting state; and

*$F \subseteq Q$ is the set of accepting states.


There is nothing in the definition of a DFA that requires that it has a single accepting state.  In fact, some regular languages cannot be accepted by a DFA with a single accepting state, for example $L = \{ \mathtt{0}^n : n \geq 0 \} \cup \{ \mathtt{1}^n : n \geq 0 \}$.

If $f$ is an $n$-ary boolean function, then (at least according to my interpretation), $S_f$ is the family of all length $n$ binary strings (i.e., strings over $\Sigma = \{ \mathtt{0} ,\mathtt{1} \}$) $w = b_1 \cdots b_n$ such that $f(w) = f ( b_1 , \ldots , b_n ) = 1$.  To construct a DFA $M_f$ with $2^{n+1}$ many states which accepts $S_f$ consider the following outline:


*

*up to length $n$, have $M_f$ keep track of exactly which binary string it has read so far (i.e., $M_f$ has a single state $q_w$ for every binary string $w$ of length $\leq n$);

*from length $n+1$ onwards, $M_f$ should know that the string is too long to be in $S_f$, so we can include an additional "too long" state;

*the transition function should be obvious; 

*the starting state is the state associated with the empty string $\varepsilon$; and

*the accepting states are exactly those $q_w$ where $q_w$ has length $n$ and $f ( w ) = 1$.


I'll leave the details and the checking that this is as required up to you.

To get a DFA with a single accepting state, consider altering the DFA $M_f$ above by "collapsing" all of the accepting states to a single state $q_{\text{accept}}$ which has the following properties:


*

*if $\delta ( q , b ) = q^\prime$ for some accepting state $q^\prime$, then $\delta^\prime ( q , b ) = q_{\text{accept}}$ in the new DFA;

*if $\delta ( q^\prime , b ) = q$ for some accepting state $q^\prime$, then $\delta^\prime ( q_{\text{accept}} , b ) = q$ in the new DFA.


A little bit of work is required to show that this results in a well-defined DFA (for example, the transition function $\delta^\prime$ doesn't give contradictory results), and that this DFA does indeed accept the same language.  (As mentioned before, not all regular languages can be accepted by a DFA with a single accepting state, so the fact that this works will rely somewhat on the structure of the DFA $M_f$ constructed above.)
