The Gateway to Computer Science Excellence
+1 vote
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:
in Theory of Computation by Active | 107 views
$(i)6 \text{states} (ii) \text{7 states}$
Show the resultant transition diagrams

2 Answers

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

arvin, yes you are correct

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

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

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


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

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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
118,146 users