Peter Linz Edition 4 Exercise 3.1 Question 27 (Page No. 77)

Question

Find a regular expression that denotes all bit strings whose value, when interpreted as a binary integer, is greater than or equal to 40.

Comments

my approach is to OR all binary strings from 40 to 63 and then add (1+0)* in the end like

(40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+61+61+62+63)(0+1)*

is it correct?

---

No, It would be wrong because your RE will Not generate many strings say : 64(1000000), 65 (1000001), and many more.

---

(0+1)*1(0+1)1(0+1)(0+1)(0+1)(0+1)∗ will this be ok

Answer 1

First Let's write RE for all bit strings whose value, when interpreted as a binary integer, is greater than or equal to 64 (Because it will be 7 or more than 7 bits for all these numbers in binary) : $(0+1)^*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)^*\,$  

And Now just add strings from 40 to 63 to make RE Complete.

---

$(0+1)^*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)^*\,$ = $0^*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)^*\,$ 

Comments

(0+1)*1(0+1)1(0+1)(0+1)(0+1)(0+1)∗ will this be ok

---

(101+110+111)(0+1)(0+1)(0+1) + 1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)* , is this answer right ?