GATE 2000

Question 31

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

A	L must be {aⁿ \|n is odd}
B	L must be {aⁿ \|n is even}
C	L must be {aⁿ\|≥0}
D	Either L must be {aⁿ \|n is odd}, or L must be {aⁿ \| n is even}

Question 31 Explanation:

If first state is final, then it accepts even no. of a’s. If second state is final then it accepts odd no. of a’s.

Correct Answer: D

Question 31 Explanation:

If first state is final, then it accepts even no. of a’s. If second state is final then it accepts odd no. of a’s.

A	L must be {aⁿ \|n is odd}
B	L must be {aⁿ \|n is even}
C	L must be {aⁿ\|≥0}
D	Either L must be {aⁿ \|n is odd}, or L must be {aⁿ \| n is even}