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.