DFA for Boolean Formula

Question

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.

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

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

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

4. 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.

Answer 1

Recall that a DFA is a $5$-tuple $M = ( Q , \Sigma , \delta , q_0 , F )$ where

1. $Q$ is the set of states of $M$;
2. $\Sigma$ is the underlying alphabet of $M$;
3. $\delta : Q \times \Sigma \to Q$ is the transition function;
4. $q_0 \in Q$ is the starting state; and
5. $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:

1. if $\delta ( q , b ) = q^\prime$ for some accepting state $q^\prime$, then $\delta^\prime ( q , b ) = q_{\text{accept}}$ in the new DFA;
2. 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.)