The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 votes

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?

- $5$
- $6$
- $7$
- $8$

+9

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 *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.

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.

+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

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..

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..

+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$

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$

+52 votes

+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

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.

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.

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

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.

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

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.

+3 votes

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 **

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,541 questions

54,071 answers

187,187 comments

70,978 users