0 0 votes what is the minimum number of states in FA and DFA that accepts empty language? Theory of Computation + – arch 1.5k views answer comment Share Follow Print See 1 comment 1 1 comment reply Rishabh Gupta 2 commented Nov 27, 2017 reply Follow flag https://gateoverflow.in/142632/theory-of-computation 0 0 replyShare Please log in or register to add a comment.
Best answer 1 1 vote I think the answer will be 1 which will be non-final. This is similar to the problem of a regular language which is a subset of every language and needs only 1 state in its normal DFA. The DFA accepts Language L= {} sumit chakraborty answered Nov 26, 2017 • selected Nov 26, 2017 by Manu Thakur sumit chakraborty comment Share Follow See all 3 Comments 3 3 Comments reply Manu Thakur commented Nov 26, 2017 reply Follow flag yes, answer is one state only, final state f is a subset of all states Q, which can be empty. moreover there is a question on it in gate 2015 set 1, and answer was given 1. 1 1 replyShare Namit Dhupar commented Nov 27, 2017 reply Follow flag Don't you think the initial state should also be the final state for that to "accept" ? 0 0 replyShare sumit chakraborty commented Nov 29, 2017 reply Follow flag The absence of final state indicates that the DFA does not accept any language and hence the language of the DFA is {}. 0 0 replyShare Please log in or register to add a comment.
0 0 votes No Transition from one state to another in an empty language. So 2 Namit Dhupar answered Nov 26, 2017 Namit Dhupar comment Share Follow See all 5 Comments 5 5 Comments reply Show 2 previous comments arch commented Nov 26, 2017 reply Follow flag i was also marked for 1 state but answer given is 2. 0 0 replyShare Namit Dhupar commented Nov 26, 2017 reply Follow flag Yes, these Test Series are never 100% right!! 0 0 replyShare Manu Thakur commented Nov 27, 2017 reply Follow flag in such questions go by the basic definition: F is a subset of Q, and empty subset is also a set. 1 1 replyShare Please log in or register to add a comment.
