Logic Design Questions and Answers – Elimination of Redundant States

This set of Logic Design Multiple Choice Questions & Answers (MCQs) focuses on “Elimination of Redundant States”.

1. When are two states in a state table termed as redundant states?
a) Only the outputs are same
b) Only the next states are same
c) Inputs are same
d) Both outputs and next states are same

Explanation: State tables contain the information about present state, next state and outputs of various state of any algorithmic state machine. Two states in a state table are termed as redundant states if and only if the outputs as well as the next states are same.

2. What step is taken if there are two or more states equivalent?
a) All of them are kept as they are
b) Only one row of such state is kept and others are omitted
c) All of them are omitted
d) Any one row of the equivalent states are omitted

Explanation: If any two states in a state table have identical present state, next state and output then they are termed as equivalent states. Equivalent states are always used to minimize and simplify the state table. So only one row of such state is kept and others are omitted.

3. Which two states are redundant states in the following table?

a) a and b
b) d and f
c) a and f
d) e and f

Explanation: Any two states in a state table having identical present state, next state and output then they are termed as equivalent states. It is clear from the state table that states d and f have absolutely equivalent next state and output configuration. So, they can be considered as equivalent states.

4. Which of the following operations are preformed to find redundant states in any state table?
a) Row matching
b) Column matching
c) Matrix matching
d) Table matching

Explanation: In the state tables, each state, their output and next states are represented in a single row. Hence, we have to perform row matching to find two equivalent states. So, the correct answer is row matching.

5. Suppose two equivalent states in a state table have present and next states as (a, b) for both. If one of them has an output e, then what will be the output of the other state?
a) b
b) a
c) e
d) c

Explanation: State tables are used to describe different states of any finite state machine. If the present state, next state and output of any two states are same then they are called as equivalent states. Thus, the output of the both states will be same, the output of the other state will also be ‘e’.

6. Which one of the following techniques are used for elimination of the redundant states?
a) Row matching technique
b) Column Matching Technique
c) Array matching technique
d) Matrix Matching Technique

Explanation: Two states which appear numerically different, can in actual fact be logically identical. They are termed as redundant states. We have to eliminate these states to simplify our calculation. We eliminate state by using a special technique called row matching technique.

Sanfoundry Global Education & Learning Series – Logic Design.