The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2k views

A  1-input, 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
asked in Digital Logic by Veteran (69k points)
retagged by | 2k views
not able to interpret this question please explain me this question in a simple way ...

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. 

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 

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.

then how this zknk=2. wts mean ??

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

4 Answers

+35 votes
Best answer
Though the question is from digital logic, answer is purely from automata. As per 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 number of 0's is less than 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, output will be 10 (both these states not having any outgoing transitions) and for other 3 states, output will be 00 as per the given description of the circuit.
answered by Veteran (18k points)
selected by
Arjun Sir i  m not able to understand this explanation ...can we solve it using mealy machine

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. 

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 .
+29 votes

The Automaton will look like this. :D

answered by Active (1.1k points)
Nice explanation!!
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

@ankitgupta.1729 

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

@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.
@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.
Thank you!! I miss interpret the question
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.
+3 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.

answered by Junior (833 points)
+2 votes

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

answered by Active (1.3k points)

@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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
114,178 comments
38,665 users