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

b) Find a regular expression for all bit strings, with leading bit 1, interpreted as a binary integer,
with values not between 10 and 30.

2 Answers

1 votes
1 votes

Answer $a$ : 

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)^*\,$ 



Answer $b $ : 

Try Dividing the Problem and then summing up all the possibilities.(Divide and Conquer)

First Let's write RE for All Bit Strings, with leading bit 1, interpreted as a binary integer, with values more than or equal to 32 (Because it will be 6 or more than 6 bits for all these numbers in binary) =  $1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)^*\,$

Now the remaining Strings in the language are : One Length, Two Length, Three Length, and Some Four length, and Some five length Strings.  = $1\,+ \, 1(0+1)\,+1(0+1)(0+1)\,+1000\,+1001\,+1010\,+11110\,+11111\,$  (Assuming that "in between 10 and 30" means 10 and 30 Not Included in the Exclusion of Strings from the language)

So, The Desired RE for the language is :

$1\,+ \, 1(0+1)\,+1(0+1)(0+1)\,+1000\,+1001\,+1010\,+11110\,+11111\,+1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)^*\,$

0 votes
0 votes
[ 32+8 = 40: b'101000' ] ==> Required RegEx: [01]*1[01]1[01]{3}

[ 8+2 = 10: b'01010' & 16+8+4+2 = 30: b'11110' ] ==> Required RegEx: ^(?![01]1[01]10)$

Related questions

0 votes
0 votes
0 answers
1
Aryam asked Jun 8, 2023
202 views
Can anyone help me in this exercise:Show that the language L = {an : n is a multiple of three, but not a multiple of 5} is regular with DFA.i make DFA but i don’t sure ...
0 votes
0 votes
0 answers
4