-
Consider the language L given by the regular expression (a + b) *b (a + b) over the alphabet {a.b}. The smallest number of states needed in a deterministic finite-state automata (DFA) accepting L is ________.
-
- 2
- 4
- 1
- 10
Correct Option: B
The given regular expression is (a + b) * b (a + b). In this all string whose second last bit is ‘b’. So, the minimal NFA is
It can be described as “All string over {a, b} ending with ‘ba’ or ‘bb’. Then the minimal (DFA) accepting (L), find by converting it into minimal DFA by subset construction Algorithm.
Hence, it is a minimal DFA with 4 states.
