4,762 views
8 votes
8 votes

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

3 Answers

Best answer
17 votes
17 votes

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.

edited by
1 votes
1 votes
* 1 1 *  * 1 1 *  = 8 possibilites

out of 8 possibilites only below 2 strings will be accepted by given DFA.

01110111

01110110
Answer:

Related questions

19 votes
19 votes
5 answers
1
Isha Karn asked Oct 29, 2014
10,465 views
The number of states required by a Finite State Machine,to simulate the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits is?$m \...
7 votes
7 votes
5 answers
2
naga praveen asked Jun 13, 2016
5,383 views
The following Finite Automaton recognizes which of the given languages?$\{ 1, 0 \}^* \{ 0 1 \}$$\{ 1,0\}^*\{ 1\}$$\{ 1 \} \{1, 0\}^*\{ 1 \}$$1^*0^*\{0,1\}$
6 votes
6 votes
4 answers
3
kvkumar asked Jun 29, 2016
5,243 views
How many states are there in a minimum state deterministic finite automaton accepting the language $L = \{w \mid w \in \{0,1\}^*,$ number of 0's is divisible by 2 and num...
2 votes
2 votes
1 answer
4
ajit asked Sep 23, 2015
4,725 views
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?it may halt and accept the inputit may halt by changing...