# Deterministic Finite Automata - Myhill Nerode

1. Dec 19, 2013

### knowLittle

1. The problem statement, all variables and given/known data
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.

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

Last edited: Dec 19, 2013