The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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:
asked in Theory of Computation by Active (3.5k points) | 59 views
$(i)6 \text{states} (ii) \text{7 states}$
Show the resultant transition diagrams

2 Answers

0 votes
  • Please tell me if im wrong
answered by Active (3.3k points)
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.
answered by Boss (11.9k points)
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.

Related questions

0 votes
0 answers
0 votes
1 answer
asked Aug 7, 2018 in Theory of Computation by himgta Active (3.5k points) | 55 views
+1 vote
2 answers
asked Jul 14, 2018 in Theory of Computation by himgta Active (3.5k points) | 62 views
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
49,814 questions
54,516 answers
75,286 users