Register

UGC NET CSE | June 2012 | Part 3 | Question: 35

• recategorized by
4,091 views
1 votes
1 votes

Consider the regular expression (a+b)(a+b) ..... (a+b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains

  1. n states
  2. n+1 states
  3. n+2 states
  4. 2$^n$ states
• recategorized by
User Avatar

1 Answer

1 votes
1 votes
ANSWER: OPTION B

Without trap for 1 symbol (a + b) a or b , required 2 states and for 2 symbols (a+b) (a+b) required 3 states and so on... So,
n+1 states for NFA
n+2 states for DFA (include trap state)
Asking for minimum so n+1 states
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4.6k
views
1 answers
3 votes
go_editor asked Jul 7, 2016
4,596 views
UGC NET CSE | June 2012 | Part 3 | Question: 43
The regular expression for the following DFAab*(b+aa*b)*a*b(b+aa*b)*a*b(b*+aa*b)a*b(b+aa*b)*
User Avatar
5.2k
views
2 answers
2 votes
go_editor asked Jul 7, 2016
5,150 views
UGC NET CSE | June 2012 | Part 3 | Question: 52
Match the following : ... )-(d)}$\text{(i)-(c), (ii)-(b), (iii)-(d), (iv)-(a)}$
User Avatar
2.9k
views
2 answers
1 votes
go_editor asked Jul 7, 2016
2,850 views
UGC NET CSE | June 2012 | Part 3 | Question: 39
The following CFG $S \rightarrow aB \mid bA, A \rightarrow a \mid as \mid bAA, B \rightarrow b \mid bs \mid aBB$ generates strings of terminals that haveodd number of a ... of b'sequal number of a's and b'snot equal number of a's and b's
User Avatar
5.5k
views
2 answers
3 votes
go_editor asked Jul 7, 2016
5,476 views
UGC NET CSE | June 2012 | Part 3 | Question: 32
The equivalent grammar corresponding to the grammar $G:S \rightarrow aA, A \rightarrow BB, B \rightarrow aBb \mid \varepsilon$ ...
User Avatar
Link Copied!