+1 vote
107 views
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:
| 107 views
0
$(i)6 \text{states} (ii) \text{7 states}$
0
Show the resultant transition diagrams

• Please tell me if im wrong
by Active
0
yes you are correct.
0
this is wrong because you haven't used the symbol {b}.
0

arvin, yes you are correct

but i hope he is interested on a only....

0
Yes, I should have added self loops for all states for input 'b'.
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.
by Boss
0
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
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

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

This question is asking about minimal finite automata ,then we should draw nfa or minimal state DFA ,Somebody please confirm [email protected]Shaik Masthan

0
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.