1 votes 1 votes Consider the minimal Finite automata that accepts all the strings of a’s & b’s where each string contains (i) exactly 5 a’s (ii) atmost 5 a’s The No. of states in each case respectively are: himgta asked Jul 30, 2018 himgta 817 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Anand. commented Jul 30, 2018 reply Follow Share $(i)6 \text{states} (ii) \text{7 states}$ 0 votes 0 votes himgta commented Jul 30, 2018 reply Follow Share Show the resultant transition diagrams 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Please tell me if im wrong Vikas Verma answered Jul 30, 2018 Vikas Verma comment Share Follow See all 4 Comments See all 4 4 Comments reply Shaik Masthan commented Jul 30, 2018 reply Follow Share yes you are correct. 0 votes 0 votes arvin commented Jul 31, 2018 reply Follow Share this is wrong because you haven't used the symbol {b}. 0 votes 0 votes Shaik Masthan commented Jul 31, 2018 reply Follow Share @ arvin, yes you are correct but i hope he is interested on a only.... 0 votes 0 votes Vikas Verma commented Jul 31, 2018 reply Follow Share Yes, I should have added self loops for all states for input 'b'. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes case 1 : exactly 5 a's : we will have dfa = 7 states nfa = 6 states case 2 : atmost 5 a's : we will have dfa = 7 states nfa = 6 states for minimal finite automata we will find minimum (dfa,nfa) which comes out to be 6 states for each case. arvin answered Jul 30, 2018 arvin comment Share Follow See all 5 Comments See all 5 5 Comments reply Shaik Masthan commented Jul 30, 2018 reply Follow Share Finite Automata means it is DFA but not NFA PDA means it is NPDA but not DPDA (i know every DPDA is NPDA) Turing Machine means it is DTM by Default 0 votes 0 votes arvin commented Jul 30, 2018 reply Follow Share but nfa and dfa has the same power and i have read it somewhere that when they ask for minimal finite automata we find the minimum between nfa and dfa. 0 votes 0 votes Shaik Masthan commented Jul 30, 2018 reply Follow Share Note that compare to DFA, NFA always have Less no.of states, therefore it leads to the statement FA means NFA As per my knowledge those are correct. Every DFA is NFA but Every NFA is not DFA, even though power of them is equal therefore if FA means NFA then it always forgetting DFA 0 votes 0 votes himgta commented Jul 30, 2018 reply Follow Share This question is asking about minimal finite automata ,then we should draw nfa or minimal state DFA ,Somebody please confirm it!@Shaik Masthan 0 votes 0 votes arvin commented Jul 30, 2018 reply Follow Share yes u are right but if they are asking for minimal dfa than we have to find minimum dfa else we basically go for minimal nfa. 0 votes 0 votes Please log in or register to add a comment.