The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+30 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$?

- $k+1$
- $n+1$
- $2^{n+1}$
- $2^{k+1}$

+42

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

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

+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= a^{2k} 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

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=a^{2n}

then will not be (A) as answer

not getting clear view on this

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.

+25 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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,751 questions

46,766 answers

140,658 comments

58,522 users