+22 votes
3.5k views

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?

1. $5$
2. $6$
3. $7$
4. $8$

edited | 3.5k views
0
not able to interpret this question please explain me this question in a simple way ...
+10

The question is about a circuit which takes a 1-bit input and 2-bit output.

I can explain you the question using a diagram of one such circuit, but there is no use. In GATE such questions will come and you must be able to read and interpret them at that moment. This question for example is not so easy to understand (as is many others). It takes at least 1 minute of careful thinking to get the correct interpretation of the question. You can try this, you should be able to get after a few attempts. After question is properly understood, many times answer is easy to get.

0

sir just decode these 2 lines

Let zk,nk denote the number of 0’s and 1’s respectively in initial bits of the input

(zk+nk=k). The circuit outputs 00 until one of the following conditions holds.

after this will try to do more such trick questions

+1
At each clock pulse we are providing an input bit to the circuit. So, after k clock pulse we will have some number of 0 bits (zk) as input and some number of 1 bits (nk) and zk + nk = k.
0

then how this zknk=2. wts mean ??

+1
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
0
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..

## 4 Answers

+44 votes
Best answer
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 bit 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 represents 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$
by Boss (16.1k points)
edited
0
Arjun Sir i  m not able to understand this explanation ...can we solve it using mealy machine
0

Won't we consider an initial state when there is no input given, so the total number of states be 6 and not 5?? After taking the first input, the initial state may go to anyone of -1 or +1.

+2
NO you are there will be only five states.
0
no bcz mealay machine can not perform addition or subtraction as it does not have memory .
0
On input $001111$, the output will be $10$ when it should be $01$.
+55 votes The Automaton will look like this. ?

by Active (1.2k points)
edited
0
Nice explanation!!
+1
Can anyone please explain when input is 000111 then it will be in state C and output will bw 10... but here number of zeros and ones are equal.. So it should give output as 00..

Please clear my doubt
0

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

+2
@ankitgupta.1729

In 000111 even though at the end we have equal no. of 0s and 1s but we got the output as 10 when we saw third zero. And the ques says if kth bit outputs 10 or 01 then all subsequent ticks will give 10 or 01 depending on the case. We will never get 00 after we get 01 or 10.
+3
@akb1115

We are not doing normal counting here. We are just checking if difference between 0s and 1s exceeds 2. Until it exceeds this difference circuit outputs 00 but once the difference exceeds, output is either 01 or 10 depending on which bit's count exceeded the other bit's count first.

Hope it helps.
0
Thank you!! I miss interpret the question
0
At state C whatever be the input ,the output will be 10.

So, you have given 000111.

We are initially at state A, then getting input 0 it moves to B and output is 00.

at state B, getting input 0 it moves to states C and output is 10.

at state C, getting input 0 it moves to C again and output is 10.

at state C, getting input 1 it moves to C again and output is 10.

at state C, getting input 1 it moves to C again and output is 10.

at state C, getting input 1 it moves to C again and output is 10.

So, actually it is repeating in state C.
+4 votes

Zk - Nk.  = { -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.

by Junior (905 points)
+3 votes

It can be solved using concept of TOC hence total no of states is  5 by Active (1.9k points)
0

@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:

+28 votes
4 answers
4
+17 votes
4 answers
5
+15 votes
2 answers
7