Deterministic Finite Automata - Myhill Nerode

[knowLittle]

Homework Statement

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.

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

---------------------

The Attempt at a Solution

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.

 

[KataKoniK]

I would like to point out that your approach to this problem is not entirely accurate. The Myhill-Nerode theorem is a useful tool for proving the minimality of a DFA, but it is not applicable in this case because we are not given any information about the language being regular or not.

To solve this problem, we need to construct a boolean function that will require at least ${2^{n-2}}/\left({n-2}\right)$ states in its corresponding DFA. One possible approach is to use the concept of parity, which refers to the number of 1s in a bit-string. For example, in a 4-bit string, the parity is even if there are an even number of 1s and odd if there are an odd number of 1s.

We can construct a boolean function that checks the parity of the input bit-string. For n=5, we can define the function as $f(b_1, b_2, b_3, b_4, b_5) = (b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_5)$, where $\oplus$ represents the XOR operator. This function will return 1 if the number of 1s in the input bit-string is odd and 0 if it is even.

Now, let's assume that there exists a DFA with k states that accepts the language $S_f$. This means that the DFA must be able to distinguish between all possible input bit-strings, which means that there must be at least $2^k$ distinct states. However, we know that for n=5, there are only 2^5 = 32 possible input bit-strings. Hence, $2^k \geq 32$, which implies that $k \geq 5$.

Therefore, any DFA that accepts the language $S_f$ for n=5 must have at least 5 states. We can extend this proof to show that for any n ≥ 5, the corresponding boolean function will require at least ${2^{n-2}}/\left({n-2}\right)$ states in its DFA.