Home > Theory Of Computation > DFA Example : Consider Following DFA M, Let S Be The Set Of All 7 Bit String In Which First,Fourth And Last Bit Is One Then No. Of String In S Which Is Accepted By Machine M Is

DFA Example : Consider Following DFA M, Let S Be The Set Of All 7 Bit String In Which First,Fourth And Last Bit Is One Then No. Of String In S Which Is Accepted By Machine M Is

Consider Following DFA M, Let S Be The Set Of All 7 Bit String In Which First, Fourth And Last Bit Is One Then No. Of String In S Which Is Accepted By Machine M Is

a) 15   b) 16   c) 7   d) 8

 

Solution:- 

Given First, Fourth, Last Bit Is ‘0’

Then No. Of String In S Which Is Accepted By Machine M Is

Now I Have To Know Blank Bits.

0,1 Are Input Alphabets.

Σ={0,1}

 

Let’s Check With Every Possible Combination String Which Accepts The DFA Or Not.

 

So, All 4 Possible Combinations Are Valid That Is Why I’m Writing.

Comparing 00 With All 00,01,10,11 With 00 Four Strings Are Possible.

Next

Comparing o1 With all 00,01,10,11  With 0,1 Only One String Is Possible.

Next

Comparing 10 With All 00,01,10,11 With 10.Only One String Is Possible.

Comparing 11 With All The 00,01,10,11

with 11 on One String Is Possible.

4+1+1+1=7 Possible Strings.

2 thoughts on “DFA Example : Consider Following DFA M, Let S Be The Set Of All 7 Bit String In Which First,Fourth And Last Bit Is One Then No. Of String In S Which Is Accepted By Machine M Is

Leave a Reply