Computational Theory

Question

Give the state diagram of DFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0, 1}.

 

1. {w | accept all string except 11 or 110}

 

2. {w | w begins with a 11 and ends with a 0}

 

3. {w | All string accepted except empty set}

 

4. {w : w contains sub string 1111 }

 

5. {w : w start with 00 and has odd length }

 

6. {w| w does not contain the substring 1101}

 

7. { w | w contains at least three 0s }

 

8. { w | w contains the substring 0101, i.e., w = x0101y for some x and y }