UGC NET CSE | December 2018 | Part 2 | Question: 32

Question

Consider the language $L$ given by

$$L=\{ 2^{nk} \mid k >0, \text{ and n is non-negative integer number } \}$$

The minimum number of states of finite automaton which accepts the language $L$ is

• A. $n$
• B. $n+1$
• C. $\frac{n(n+1)}{2}$
• D. $2^n$

Comments

4?

Answer 1

For $n=2,\left \{2^{2k} \,|\,k>0 \right \}=\left \{2^2,2^4,2^6....\right \}$, the automata for this language would be:

For $n=3,\left \{2^{3k} \,|\,k>0 \right \}=\left \{2^3,2^6,2^9....\right \}$, the automata for this language would be:

So, for $\left \{2^{nk} \,|\,k>0 \right \}$, the number of states should be $n+1$

So, $(B)$ should be the answer.

Comments

Please check, transition on 2 from S2 should be going to S1. Similar mistake in 2nd diagram

---

Corrected it, thanks

Answer 2

n+1 states will be needed.

When n=0 and k=1,2,3,4,5,...

L1=$2^{nk}$={ $ 2^{0}$ }={ε} , Number of states required for min DFA=1

---

When n=1 and k=1,2,3,4,5,...

L2=$2^{nk}$={ $ 2^{1}$,$ 2^{2}$,$ 2^{3}$,$ 2^{4}$,$ 2^{5}$,... }, Number of states required for min DFA=2

---

When n=2 and k=1,2,3,4,5,...

L3=$2^{nk}$={ $ 2^{2}$,$ 2^{4}$,$ 2^{6}$,$ 2^{8}$,$ 2^{10}$,... }. Number of states required for min DFA=3

L=L1  U L2  U  L3 U ... U  Ln

Therefore for it'll require n+1 states. Let me know if I am wrong somewhere.

Answer 3

Option D is correct.

Minimum n+1 states are required. First put value of n as even e.g 2 u ll see it became the even number series, form a DFA.

Then put value of n as 3 to make it odd number series and again make a DFA.

U will realise n+1 number of states required.