The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
2.3k 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 (98.7k points) | 2.3k views

3 Answers

+12 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 (40.8k 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 (41.3k points)
+1 vote
Answer is C
by Loyal (9.3k points)
Answer:

Related questions

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
49,830 questions
54,807 answers
189,530 comments
80,835 users