0 votes 0 votes My doubt is it always true that the number of state in NFA is always less than number of state required in DFA for all language which are regular? Spider1896 asked Aug 10, 2018 Spider1896 993 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Siddharth Bhardawaj commented Aug 10, 2018 reply Follow Share It is false.... 0 votes 0 votes Spider1896 commented Aug 10, 2018 reply Follow Share Pls support your answer through example 0 votes 0 votes Siddharth Bhardawaj commented Aug 10, 2018 reply Follow Share In your question, it is mention that "ALWAYS" , that's the reason it is false. If it is less than or equal to then it will be true. I hope you are getting my point. Make NFA and DFA , and compare them by taking several example , you will definitely get this. :) 0 votes 0 votes Siddharth Bhardawaj commented Aug 10, 2018 reply Follow Share @spider1896 Before solving any question, read the question very carefully, then only you will get the clarity of the questions. 0 votes 0 votes Spider1896 commented Aug 10, 2018 reply Follow Share OK then consider dfa for a number divisible by 2 and nfa for the same number divisible by 2 then in this case dfa will have 2 state but then nfa will have 3 state and then here no of state in dfa will be less than nfa? Plz clear this doubt of mine 0 votes 0 votes Siddharth Bhardawaj commented Aug 10, 2018 reply Follow Share I am hoping that you are asking about " a binary number divisible by 2" . So, string accepted is : 0 10 110 100 1100 1000 and so on... So for dfa and nfa ( for both ) it require only 2 states. suppose q0 and q1 are the two states in minimal dfa and q0 is the final state. q0 ->0 = q0 q0 ->1 = q1 q1->0 = q0 q1 ->1 = q1 I hope so you will get this, otherwise post your nfa and dfa in the comment section. There must be mistakes by you when you have solve this question. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes MAX NO. OF DFA STATES FOR N NFA STATES IS 2^n IT MEANS AT MINIMUM LEVEL BOTH NFA AND DFA EQUAL BUT AT MAX AROUND 2^n STATES Deepanshu answered Aug 10, 2018 Deepanshu comment Share Follow See all 3 Comments See all 3 3 Comments reply Spider1896 commented Aug 10, 2018 reply Follow Share OK then consider dfa for a number divisible by 2 and nfa for the same number divisible by 2 then in this case dfa will have 2 state but then nfa will have 3 state and then here no of state in dfa will be less than nfa? Plz clear this doubt of mine 0 votes 0 votes BASANT KUMAR commented Aug 10, 2018 reply Follow Share can you show your nfa having 3 states?? 0 votes 0 votes Deepanshu commented Aug 11, 2018 reply Follow Share @Spider1896 it never happens 0 votes 0 votes Please log in or register to add a comment.