GATE Computer Science (CS) 2020 Solved Papers

Question : 64 of 65

Marks: +1, -0

Consider the following language.

L=\{x ∈(a, b\}^{*}|

number of a's in x is divisi ble by 2 but not divisible by 3
The minimum number of states in a DFA that accepts {L} is ____.

Solution:

{L}= {w} ∈( {a}, {b}) * ∣ {n}_{ {a}}( {w})=

multiple of 2 but not

3 .

{L}_{1}=\{ {n}_{ {a}} \bmod 2=0\} ⇒

need 2 states

{L}_{2}=\{ {n}_{ {a}} \bmod 3 ≠ 0\} ⇒

need 3 states

|L_{1} × L_{2}|=(2 × 3)=6

states.
Minimal DFA design

\Rightarrow

∴ No. of states in min. DFA = 6 states.

Go to Question:

Prev Question

Next Question