1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Deterministic Finite Automata - Myhill Nerode

  1. Dec 19, 2013 #1
    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
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Deterministic Finite Automata - Myhill Nerode
Loading...