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

2 Answers

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

Related questions

0 votes
1 answer
2
asked Aug 7 in Theory of Computation by himgta Active (2.8k points) | 50 views
+1 vote
2 answers
6
asked Jul 14 in Theory of Computation by himgta Active (2.8k points) | 58 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

44,233 questions
49,717 answers
163,877 comments
65,834 users