Search code examples
automatadfa

DFA with 4 or 5 states

Can someone build a DFA with only 4 or 5 states for the language A ? ∑={0,1}, A={z is element of ∑^* | z=uvwxy and u,y are elements of ∑^* and v,w,x are elements of ∑ and vwx has at least one 0-element}. I can only build a DFA with 6 states, but we should build one with 4 or 5 states. Here is my DFA:

DFA

Solution

  • It looks like your language has these properties:

    • strings have length at least three
    • strings contain at least one 0

    We can use the Myhill-Nerode theorem to show that a minimum DFA for this has more than five states:

    1. the empty string corresponds to the initial state [e]
    2. the string 0 can be followed by (0+1)(0+1)(0+1)(0+1) to get a string in the language and is distinct from the empty string. Call the corresponding state [0].
    3. the string 1 can be followed by (0+1)0(0+1)(0+1) + (0+1)(0+1)0(0+1) to get a string in the language. This is distinct from both 0 and the empty string so it gets a new state, call it [1]
    4. the string 00 can be followed by (0+1)(0+1)(0+1), again distinct, [00]
    5. the string 01 is indistinguishable from 00
    6. the string 10 is indistinguishable from 00 and 01
    7. the string 11 can be followed by (0+1)0(0+1), distinct from all previous; call this [11].
    8. 000 can be followed by (0+1)*, again distinct. This is the 6th string distinguishable from all shorter strings, meaning that a minimal DFA for your language must have at least six states.