GATE CSE 2003 | Question: 44

Question

A $\text{1-input}$, $\text{2-output}$ synchronous sequential circuit behaves as follows:

Let $z_k, n_k$ denote the number of $0’s$ and $1’s$ respectively in initial $k$ bits of the input

$(z_k+n_k=k)$. The circuit outputs $00$ until one of the following conditions holds.

• $z_k-n_k=2$. In this case, the output at the k-th and all subsequent clock ticks is $10$.
• $n_k-z_k=2$. In this case, the output at the k-th and all subsequent clock ticks is $01$.

What is the minimum number of states required in the state transition graph of the above circuit?

• A. $5$
• B. $6$
• C. $7$
• D. $8$

Comments

We have k bits of input after k clock pulses. Now, the question is giving some condition for this input.

zk - nk = 2 This means the number of zeroes in first k bits is 2 greater than the number of 1's. For example if k = 6, 010100 is valid, but not 010101

---

Is Determinstic diagram possible for this problem,??

After finding |no of 0's - no of 1's | = 2 in first k bits we have to output 10 or 01,

while checking 1st k bits we may encounter #1's - #0's not in range [-2,2] still condition holds true when all k bits examined ..

k =10 string is 111110000 | 11100110011..

---

Giving Mealy Machine for this problem is more appropriate than giving Moore machine.

Though we can convert the mealy machine to an equivalent Moore machine, in general, while converting mealy to Moore, the number of states may increase up to - Number of states in Mealy Machine $\times$ Number of output symbols. But, for this problem, the number of states will remain the same for both machines.

So, the below machine will be more appropriate I think.

State number denotes $z_k – n_k$.

Answer 1

Though the question is from digital logic, the answer is purely from automata. As per the question, we just need to count the difference of the number of $0'$s and $1'$s in the first $k$ bits of a number. And we just need to count till this count reaches $2$ or $-2$ (negative when the number of $0's$ is less than the number of $1's$). So, the possibilities are $-2, -1, 0, 1,$ and $2$ which represent the five states of the state transition diagram.

For state $-2$, the output of the circuit  will be $01$, for state $2$, the output will be $10$ (both these states not having any outgoing transitions) and for other $3$ states, the output will be $00$ as per the given description of the circuit.

Correct Answer: $A$

Comments

NO you are there will be only five states.

---

no bcz mealay machine can not perform addition or subtraction as it does not have memory .

---

On input $001111$, the output will be $10$ when it should be $01$.

Answer 2

The Automaton will look like this. 😎

Comments

For the input 110000 output should be 10

And for input 001111 output should be 01

 

I think these two inputs will not be giving correct result for your DFA

---

Awesome

---

@Subhadip Patra why the C and E states won't go to other .. even one more1 is added to i/p then n1-n0 = 3

Answer 3

Z_k - N_k.  = { -2,-1,0,1,2 }

Z-N = 2 ( no of zeros - number of ones =2 )

Z-N = -2 (no of ones - number of zeros =2 )

So there will be a total of 5 states i.e -2,-1,0,1,2 . With initial state as 0 ( output 00 ) as number of ones and number of zeros are 0.

Final states as -2 ( output 01 ) and 2 (output 10 ) with self loop for all the subsequent inputs.

-1 and 1 are intermediate states.

Answer 4

It can be solved using concept of TOC hence total no of states is  5

Comments

@Neeraj Chandrakar

It is wrong because:-

I think DFA can't be possible for this bcz FSM can do modular counting but not normal counting but in question we are not asked about modular counting as here we have to count total number of 1's and 0's  and then see the difference between them which can't be archive with FSM as it doesn't have memory enough to keep track of number of 1's and 0's therefore we have to make TM for this that will have 5 states

Answer 5

1. Initial State: The circuit starts in a state where it outputs $00$, waiting for either condition to be met.
2. Condition 1 $(zk - nk = 2)$: If this condition is met, the circuit transitions to a state where it outputs $10$ indefinitely.
3. Condition 2 $(nk - zk = 2)$: If this condition is met, the circuit transitions to a state where it outputs $01$ indefinitely.
4. No Reset: There's no mention of reset mechanism, so once the circuit enters either of the output states ($10$ or $01$), it remains there.

Therefore, the minimum states required are:

• $1$ state for the initial $00$ output
• $2$ states for the output states $(10 and 01)$
• $2$ additional states to track the difference between $0s$ and $1s$ ($-1$ and $1$) before reaching the output states

Total: 5 states