The number of states in the minimum sized DFA that accepts the language defined by the regular expression

(0 + 1)(0 + 1)(0 + 1)
is ______.

Question

Question

This question was previously asked in

GATE CS 2016 Official Paper: Shift 2

Attempt Online

Answer 1

Given regular expression: (0 + 1)*(0 + 1)(0 + 1)*

In this, there is atleast one appearance of (0 + 1).

It generates strings of type {0, 1, 00, 01, 10, 11, 000, 001, 011, ……. }

DFA for the given expression is:

F1 R.S 24.12.19 Pallavi D 2

Number of states in minimum sized DFA for this regular expression = 2