Michael Sipser Edition 3 Exercise 1 Question 6 (Page No. 84)

Question

Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is $\{0,1\}.$

1. $\text{\{w| w begins with a 1 and ends with a 0\}}$
2. $\text{\{w| w contains at least three 1s\}}$
3. $\text{\{w| w contains the substring 0101 (i.e., w = x0101y for some x and y)\}}$
4. $\text{\{w| w has length at least 3 and its third symbol is a 0\}}$
5. $\text{\{w| w starts with 0 and has odd length, or starts with 1 and has even length\}}$
6. $\text{\{w| w doesn’t contain the substring 110\}}$
7. $\text{\{w| the length of w is at most 5\}}$
8. $\text{\{w| w is any string except 11 and 111\}}$
9. $\text{\{w| every odd position of w is a 1\}}$
10. $\text{\{w| w contains at least two 0's and at most one 1\}}$
11. $\{\epsilon, 0\}$
12. $\text{\{w| w contains an even number of 0's, or contains exactly two 1's\}}$
13. $\text{The empty set}$
14. $\text{All strings except the empty string}$ 

Answer 1

a. L=w begins with 1 and ends with 0

b. L=wa contains atleast three 1s

c. L=w contains sub-string 0101

d. L=w has length atleast 3 and third symbol is 0

e. L=w starts with 0 and has odd length, or starts with 1 and has even length

f. L=w contains the sub-string 110

L'=w doesn't contains sub-string 110

g. L=length of w is at most 5

h. L=w is any string except 11 and 111

i. L=every odd position of w is a 1

j. L=w contains at least two 0's and at most one 1

it is the intersection of two DFA's. the first DFA represents the language where string contains atleast two 0s and the second DFA represents the DFA where the string has at most one 1

intersection of the two DFAs will be

L=000*+(100+010+000*1)0*

k. L=ϵ+0

l. L=w contains an even number of 0's, or contains exactly two 1's

m. DFA accepts all string

n. DFA accepts all strings except empty string

Comments

DFA of  "l. L=w contains an even number of 0's, or contains exactly two 1's" only allows words that start with 0 or 1 but it's not specified in the language or?

---

In (h) w is any string except 11 and 111.

But according to the figure you draw, it does not accept the string 0111.

Say the last state is q;

then for input 1 in q , it should remain in q i.e q->1=q.