Redirected
recategorized by
4,061 views
1 votes
1 votes

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

  1. $n$
  2. $n+1$
  3. $\frac{n(n+1)}{2}$
  4. $2^n$
recategorized by

3 Answers

1 votes
1 votes

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.

edited by
0 votes
0 votes

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.

0 votes
0 votes

Option 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.

Related questions