DFAs

Draw Deterministic Finite Automata to accept the following sets of strings over the alphabet {0,1}:

1. All strings that contain exactly 4 "0"s. Solution.
2. All strings ending in "1101". Solution.
3. All strings containing exactly 4 "0"s and at least 2 "1"s. Solution.
4. All strings whose binary interpretation is divisible by 5. Solution.
5. (1.4c) All strings that contain the substring 0101. Solution.
6. (1.4e) All strings that start with 0 and have odd length or start with 1 and have even length. Solution.
7. (1.4f) All strings that don’t contain the substring 110. Solution.
8. (1.4g) All strings of length at most five. Solution.
9. (1.4i) All strings where every odd position is a 1. Solution.

---

 

DFAs

1. All strings that contain exactly 4 0s.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
2. All strings ending in 1101.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
3. All strings containing exactly 4 0s and at least 2 1s.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
4. All strings whose binary interpretation is divisible by 5.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
5. (1.4c) All strings that contain the substring 0101.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
6. (1.4e) All strings that start with 0 and has odd length or start with 1 and has even length.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
7. (1.4f) All strings that don't contain the substring 110.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
8. (1.4g) All strings of length at most 5.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
9. (1.4i) All strings where every odd position is a 1.