GATE 2018 EC – Question 29
A traffic signal cycles from GREEN to YELLOW, YELLOW to RED and RED to GREEN. In each cycle, GREEN is turned on for 70 seconds, YELLOW is turned on for 5 seconds and the RED is turned on for 75 seconds. This traffic light has to be implemented using a finite state machine (FSM). The only input to this FSM is a clock of 5 second period. The minimum number of flip-flops required to implement this FSM is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5
Explanation
The FSM only advances on the 5 s clock, so we count the clock ticks in each light.
- Green: $70/5=14$ ticks
- Yellow: $5/5=1$ tick
- Red: $75/5=15$ ticks
Total $14+1+15=30$ distinct states are needed (one per tick of the cycle). $n$ flip-flops give $2^n$ states, and $2^5=32\ge30>2^4=16$, so 5 flip-flops are needed.