Question

Which of the following options is incorrect?

(a) A language L is regular if and only if ~L has finite number of equivalent classes.

(b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.

(c) A language L is NFA-regular if and only if it is DFA-regular.

(d) None of the mentioned

I had been asked this question by my college professor while I was bunking the class.

Question is taken from Properties-Non Regular Languages topic in division Regular Expressions and Languages of Automata Theory

Answer 1

The correct answer is (b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.

Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.