retagged by
441 views
2 votes
2 votes

Consider the following deterministic finite state automaton $M$:

Let $S$ denote the set of $seven$ $bit$ binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is:

  1. 1
  2. 5
  3. 7
  4. 8
retagged by

1 Answer

Best answer
2 votes
2 votes
The strings with the 1st, 4th and 7th bits as 1’s will be
1001D001
1001D011
1001D101
1001D111

1011A001
1011A011
1011A101
1011A111

1101A001
1101A011
1101A101
1101A111

1111A001
1111A010
1111A101
1111A111

The first four are accepted. In the remaining three block of fours only the first string is accepted.

 The total number of strings accepted are 7 which is option (C)
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
3
Bikram asked Feb 9, 2017
308 views
Consider the grammar:$S\rightarrow$ $PQ | SQ | PS$$P\rightarrow k$$Q\rightarrow m$To get a set of $n$ terminals, the number of productions to be used are ______. $n^{2...