edited by
11,143 views
40 votes
40 votes

The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output

  1. outputs the sum of the present and the previous bits of the input
  2. outputs $01$ whenever the input sequence contains $11$
  3. outputs $00$ whenever the input sequence contains $10$
  4. none of the above
edited by

3 Answers

Best answer
54 votes
54 votes

Answer should be option (A).

Option (B) and (C)  are clearly wrong. It says: $(\text{input } 11 \implies \text{output }01)$ and $(\text{input } 10 \implies \text{output }00)$, respectively, but, here for every single bit input the output is $2$ bit sequence.

Now, for option (A) we can trace out. Suppose string is $0111$. 

at $A$---$0$---> $A$----$1$---> $B$--$1$-->$C$---$1$-->$C$

$O/P$        $00$          $01$       $10$         $10$   

We can see here at $(A,0)$---> $(A,00)$ which sum of $0+0=00$, (previous $i/p$ bit $+$ present $i/p$ bit)

$(A,1)$--->$(B,01)$ which is sum of $0+1= 1=01$,

$(B.1)$--->$(C,10)$ which is sum of $1+1=$ (previous $i/p$ bit $+$ present $i/p$ bit)$=10$,

$(C,1)$---> $(C,10)$ which is sum of $1+1=10$

So, answer should be (A).

edited by
2 votes
2 votes
By taking up a string we may able to figure out the pattern

Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10

option A is correct

option B and C are wrong where they don't produce a correct pattern.
Answer:

Related questions

26 votes
26 votes
3 answers
1
Kathleen asked Sep 15, 2014
7,834 views
The smallest finite automaton which accepts the language $\{x \mid$ length of $x$ is divisible by $3\}$ has$2$ states$3$ states$4$ states$5$ states
25 votes
25 votes
1 answer
2
Kathleen asked Sep 15, 2014
4,169 views
We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$Give an NFA for this purposeGive a DFA for this purpose