The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+35 votes

Definition of a language $L$ with alphabet $\{a\}$ is given as following.
$$ L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$$
What is the minimum number of states needed in a DFA to recognize $L$?

  1. $k+1$
  2. $n+1$
  3. $2^{n+1}$
  4. $2^{k+1}$
asked in Theory of Computation by Veteran (96.2k points)
edited by | 3.6k views

for n=2
L= a2k k>0   ={aa,aaaa,aaaaaa,aaaaaaaa,....}

that is (aa)+

 DFA will have 3 states .

Well explained.
I did the same way

for n=1

L=a^k | k>0 { a,aa,aaa,aaaa......}

which is aa* or a+  this will take 2 states

for n=2

L=a^2k |k>0 {aa.aaaa,....}

(n+1) wll be answer.
hey prateek, why cant be the answer be k+1......please help me out .....m still in a dilemma among which answer to choose whether n+1 or k+1
got the answer ....thank you

@Praveen Saini Sir, why we come back from q2 to q1? Why can't we loop remaining a's on q2 state?

Another thing, can't be the R.E be aa(a)* Kindly help!

EDIT : Doubt cleared, SORRY to bother, Sir.


for n=2
L= a2k k>0   ={aa,aaaa,aaaaaa,aaaaaaaa,....}

that is (aa)+

if we use aa(a*) then it will be a^n n>=2 , it will contain strings aaa, aaaaa, etc that doesn't belong to L


@Praveen Saini Yes, you're right, Sir! God Bless!


but @Praveen Sir

I have one more doubt

here n and k is not defined to distinguish between them

if we take n=2

and k remain same

then, L=a2n

then will not be (A) as answer

not getting clear view on this

@Praveen Sir

@Arjun Sir

Can anyone chk this query too
Wat is ur question ?? #srestha ...


Read comment of Arjun sr below best answer...

@sreshtha Try to understand that k is a variable. k can take any positive number any time. But n is, like specified, constant for a particular language. So, when you take n=1, you need to make sure that the automata you make satisfies all values of k. I hope I clarified your doubt. Just think about it as a^(4k) OR a^(5k) need to make an automaton which accepts n number of a's, any number of times....matlab ki, a^n, a^2n, a^3n......for all k. Feel free to ask if you don't get it yet.
We are not counting Dead State here, are we?
what is a dead state?
No dead state here because only one alphabet a

1 Answer

+30 votes
Best answer

(B) $n+1$
We need a state for strings of length $0, 1, 2, ... n$ (and their respective multiples with $k$). Each of these set of strings form an equivalence class as per Myhill-Nerode relation and hence needs a separate state in min-DFA.

Myhill-Nerode Class 1 Myhill-Nerode Class 2 Myhill-Nerode Class n Myhill-Nerode Class n+1
$\epsilon$ $a, \#a = n+1, \#a = 2n+1, ...$ $\#a = n-1, \#a = 2n-1, \#a = 3n-1, ...$ $\#a = n, \#a = 2n, \#a = 3n, ...$

One thing to notice here is $k > 0$. Because of this we are not able to combine Class $1$ and Class $n+1$. Had it been $k \geq 0$, we would have had only $n$ equivalent classes and equivalently $n$ states in the minimal DFA. 

answered by Veteran (408k points)
edited by
Is it A. k+1

or B. n+1???
n+1, because n is the constant as told in the definition of L.
in the above ques, does each equivalence class contain strings of different lengths only?
No, Strings of length n, 2n, 3n ... form the same equivalence class.
How? Please elaborate more.
Is it clear now?
Yes, thanx a lot.
Could someone explain Myhill Nerode Theorem a little bit and explain this answer also a bit plz..
So, k is arbitary constant and 'n' is constant,right?

@Arjun Sir, "n is a constant" here is the main key to solution here.

If k would have k >= 0 then it is nothing but mod n counting. since k> 0 we have to reject epsilon hence that extra state.

@Arjun sir, why it would be `N` no. of states if k>=0,i couldn't get it


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,576 questions
54,190 answers
71,147 users