Question

Prove or disprove each of the following statements. Make sure to identify which proof techniques you are applying and why, such as referring to negations, implications, and universal and existential statements. (a) Any NFA that has more than one state accepts more than one string. (b) If in a DFA D an accepting state can be reached from the start state through a sequence of transitions in which there is a transition from a state to itself, then L(D) is infinite. (c) The converse of the statement in the previous question.

Answer 1

(A) The statement is not true always. If a NFA for an expression "aa" is created it would accept only one string that is "aa" while reject all other strings. If the statement would have been "Any NFA that has more than one accepting states than it accepts more than one string." it would have been true.

(B) The statement is true as the language will go through multiple transitions where it includes a state transition to itself which means the number of transition for language of length k will be n≤k<2n where n is the number of states of DFA this means that L(D) will be infinite.

(C) The converse statement will be false, because if the DFA had no state with the transition on itself than language could be accepted with length k where k<n thus the rule is not satisfied.