Consider the below statements:

Consider the below statements:

(A) Given an NFA that recognizes L, to build an NFA to recognize the reverse of L , containing every string  in reverse, it suffices to swap the initial and final states and reverse all edges.

(B) All regular languages are decidable. (That is the question Does w belongs to L  when it is known that L is regular, is computable)


(A) Both are False

(B) Both are True

(C) Only S1 is True

(D) Only S2 is True


Answer: D

S1: There can be more than one final states in NFA, so only reversing the states will cause more than 1 start state which is not allowed.

S2: If a language is regular, we can write decider for that. 

NIKHIL JAISWAL nikjais 11 Jan 2018 11:37 am

There can be more than one final states in DFA also, then S1 should not hold even for DFA. Where does it hold then?