Michael Sipser Edition 3 Exercise 1 Question 18 (Page No. 86)

Question

Give regular expressions generating the languages of 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. 1(0+1)*0
b. 0*10*10*1(0+1)*
c. (0+1)*0101(0+1)*
d. (0+1)(0+1)0(0+1)*
e. 0((0+1)(0+1))* + 1(0+1)((0+1)(0+1))*
f. 0*+1*+(01)*+(10)*+(010)*
g. (0+1)(0+1)(0+1()(0+1)(0+1)
h. ε+0*+1+ 111$(0+1)^+$ + (0+10)*11$(0+01)^+$
i. (1(0+1))*(1+ε)
j.  0*(00+010+100+001)0*
k. ε+0
l. (1*01*01*)*+0*10*10*
m. Ф
n. $(0+1)^+$

Comments

Can u help me format the answers using this format? Thanks

• Terminals:
  • Any character from the alphabet is a terminal
  • Epsilon (ε) is expressed as: \e, \eps or \epsilon
  • The empty set is expressed as: \emp or \emptyset
• Operations (R is a regular expression):
  • Union is expressed as R|R
  • Star as R*
  • Concatenation as RR
  • Plus as R+