Consider the following language:

$L = {x ϵ {a, b}^{*} ∣ n u m b e r o f a^{'} s i n x i s d i v i s i b l e b y 2 b u t n o t d i v i s i b l e b y 3}$

The minimum number of states in a DFA that accepts L is

Open in App

Solution

The minimum number of states in a DFA that accepts:
$L = {x ϵ {a, b}^{} ∣ n u m b e r o f a^{'} s i s d i v i s i b l e b y 2 b u t n o t d i v i s i b l e b y 3}$ is 6 states as shown below:

(or) alternatively it can be designed by taking a product automata of

$L = {x ϵ {a, b}^{} ∣ n u m b e r o f a^{'} s d i v i s i b l e b y 2}$ and $L_{2} = {x ϵ {a, b}^{*} ∣ n u m b e r o f a^{'} s n o t d i v i s i b l e b y 3}$ as shown below:

Minimum DFA for $L_{1}$ :

Minimum DFA for $L_{2}$ :

Product automata $L_{1} \cap L_{2}$ having six states, shown below:

Which is same as our directly designed machine with 6 states.

Suggest Corrections

Similar questions

Consider a DFA over \sum

accepting all strings which have number

of a's divisible by 6 and number of b's

divisible by 8. What is the minimum

numberof states that the DFA will have?

(a + b)^{*} b (a + b)

{a, b}

L (M) \cap L (N)

(0 + 1)^{*} (0 + 1) (0 + 1)^{*}

L \subseteq {0, 1}^{*}

Join BYJU'S Learning Program