made easy work book

Question

how many strings of at most 4 bits that

start with and end with "0" belongs to the language described by (01+10)* 0 (0+1)*  ??

 

please give explanation..

Answer 1

For length at most 4 we will consider strings of length 4, 3, 2, 1, 0.

Language ;- (01+10)* 0 (0+1)* 

Condition :-  string should start and end with 0.

For length 4:-

0 _ _ 0 { such format strings will be counted since they are satisfying criteria. }

so, strings are-

0000

0010

0100

0110

All these strings will get selected because we can always use the 0 (0+1)*.

For length 3

0 _ 0 { such format strings will be counted since they are satisfying criteria. }

Strings that satisfying condition are as follow

010

000

For length 2

00 { such format strings will be counted since they are satisfying criteria. }

String satisfying criteria-

00

For length 1

0 is the only string which start  and end with zero.

For length 0 there is no such string.

So total there are 4 + 2 + 1 + 1

Ans = 8.

Comments

ohhkk thanku nice explanation..