Register

#TOC Doubt regarding states

689 views
0 votes
0 votes
Can NFA has more states or equal states than DFA? Say NFA has n states and DFA has m states then -

n>=m possible?
User Avatar

2 Answers

Best answer
2 votes
2 votes

Yes definitely n could be greater than m ( but not always(n>=m).it may)

like if DFA has m states you may introduce a null production and get m+1 state NFA.

An example
• selected by
User Avatar
2 votes
2 votes
epsilon nfa can have any number of states. but minimised nfa can never have more states than dfa
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
2 answers
1
Ayush Upadhyaya asked Sep 12, 2018
651 views
#toc-self doubt
Which of the following below are regular? (1)$\{wxw^r | w \in (0,1)^+,x\in(0,1)^*\}$ (2)$\{wxw^r | w \in (0,1)^*,x\in(0,1)^+\}$ (3)$\{ww^rx|\, w\in (0,1)^*,x \in (0,1)^+\}$ (4)$\{ww^rx| w\in (0,1)^+, x\in (0,1)^*)\}$
Which of the following below are regular?(1)$\{wxw^r | w \in (0,1)^+,x\in(0,1)^*\}$(2)$\{wxw^r | w \in (0,1)^*,x\in(0,1)^+\}$(3)$\{ww^rx|\, w\in (0,1)^*,x \in (0,1)^+\}$(...
User Avatar
3 votes
3 votes
1 answer
2
ashishgateashish asked Mar 13, 2018
1,153 views
#TOC Doubt - Regular expressions
Part A: Given : (b|ab*ab*)* How can it be interpreted as: 1.((b+ab*)ab*)* 2.(b+(ab*ab*))* 3.((b+a)b*ab*)* Part B: 1.What will be its NFA ? 2.Can we draw a direct MINIMAL DFA for such questions?
Part A:Given : (b|ab*ab*)* How can it be interpreted as:1.((b+ab*)ab*)* 2.(b+(ab*ab*))*3.((b+a)b*ab*)*Part B:1.What will be its NFA ? 2.Can we draw a direct MINIMAL DFA f...
User Avatar
0 votes
0 votes
0 answers
3
iarnav asked Jan 30, 2018
202 views
#TOC Doubt
L = anbm / n,m>=1 What type pf Language is this? Also, please tell are n,m are independent or dependent i.e can we have like n=2 and m=3 or both n,m have to have same values!?
L = anbm / n,m>=1What type pf Language is this? Also, please tell are n,m are independent or dependent i.e can we have like n=2 and m=3 or both n,m have to have same valu...
User Avatar
0 votes
0 votes
1 answer
4
Sahil1994 asked Dec 12, 2017
811 views
#TOC DOUBT
A)Is it useful to draw FA if we need to tell the language of the following grammar...? B)What is the language of the following grammar..? C) What will be the final state Of FA and what is the criteria to find out final state.if a given a regular grammar.? S→aB|bA A→aS|bAA|a B→bS|aBB|b
A)Is it useful to draw FA if we need to tell the language of the following grammar...?B)What is the language of the following grammar..?C) What will be the final state O...
User Avatar
Link Copied!