The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
2.7k views

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 (107k points)
edited by | 2.7k views
+1
******
+49

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

that is (aa)+

 DFA will have 3 states .

0
Well explained.
+3
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.
0
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
0
got the answer ....thank you
+1

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

+1

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

0

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

0

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

0
@Praveen Sir

@Arjun Sir

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

srestha 

Read comment of Arjun sr below best answer...

0
@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)....you 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.
0
We are not counting Dead State here, are we?
0
what is a dead state?

1 Answer

+28 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 (363k points)
edited by
0
Is it A. k+1

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

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

0
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.
Answer:

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

42,700 questions
48,662 answers
156,620 comments
63,971 users