The Gateway to Computer Science Excellence
+6 votes
2.5k views

Consider the following Deterministic Finite Automaton $M$.

Let $S$ denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in $S$ that are accepted by $M$ is

  1. 0
  2. 1
  3. 2
  4. 3
in Theory of Computation by Veteran (105k points) | 2.5k views

3 Answers

+14 votes
Best answer

There are only Two cases a) and b) in which we get $2^{nd},3^{rd},6^{th},\text{and},\;7^{th}$ bits as $1$

1.

2. 

In case 1) we are not reaching at final state with $8$ bits

From Case 2)

The number of $8$ bit strings in S that are accepted by M =2

1. 01110111

2.01110110

Hence,(c)2 is the correct choice.

by Boss (41.2k points)
edited by
0
Explanation is good. But please increase the size of the image because numbers are not properly visible.
0
I think Now images are ok :)
+2 votes
Just looking at the finite Automata, there will be two string:

01100111

01100110
by Boss (42.3k points)
+1 vote
Answer is C
by Loyal (9.9k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,240 answers
198,008 comments
104,600 users