Consider the regular expression (a + b)(a + b) … (a + b) (n-times). The…
2012
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
- A.
n states
- B.
n + 1 states
- C.
n + 2 states
- D.
2n states
Attempted by 53 students.
Show answer & explanation
Correct answer: C
The regular expression represents all strings of length exactly n over the alphabet {a, b}. A DFA requires states for lengths 0 through n plus a trap state. Therefore, the minimum number of states is n + 2.
A video solution is available for this question — log in and enroll to watch it.