GATE CSE 2011 | Question: 42

Question

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

• A. $k+1$
• B. $n+1$
• C. $2^{n+1}$
• D. $2^{k+1}$

Comments

when K is 1, we get minimum possible string in language is a^n

to accept string of length n,FA requires atleast n+1 states

by pumping lemma, if string accepted by DFA has n states and DFA has also n states , then there is atleast 1 loop in acceptance path of w for that string

if we use self loop, then we can't keep count of how many a's we have read so far, hence we can't say less than  or equal to n states possible.

---

This may help :  https://youtu.be/hxUZRgARn-g?t=631

---

I found one biggest trap here that

k > 0 ................so  the language do not contain ε  and Hence, answer is "n+1"

if it was

k >= 0...............so the language do contain ε  and Hence, answer will be "n"

Answer 1

(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.
$$\begin{array}{|c|c|c|c|}\hline \textbf{Myhill-Nerode} & \textbf{Myhill-Nerode} & \textbf{Myhill-Nerode} & \textbf{Myhill-Nerode}\\\textbf{Class 1} & \textbf{Class 2} & \textbf{Class n} & \textbf{Class n+1}
 \\\hline \text{$\epsilon$} & \text{a,} & \text{#a=n-1,}& \text{#a=n,}\\ & \text{#a=n+1,}& \text{#a=2n-1,} &\text{#a=2n,}\\ & \text{#a=2n+1,}& \text{#a=3n-1,} &\text{#a=3n,}\\ &\text{...}&\text{...}& \text{...} \\\hline  \end{array}$$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. 

Comments

if n is constant then whatever is the value of k,languge will be in AP.

---

Please explain the significance if Myhill nerode theorem w.r.t above question.  I understood the solution with examples but not in context of Myhill Nerode theorem.

---

🚢

Answer 2

The language \( L \) is defined as:

\[
L = \{ a^{nk} \mid k > 0,\ \text{and } n \text{ is a positive integer constant} \}
\]

This means the strings in \( L \) are of the form:

\[
L = \{ a^n,\ a^{2n},\ a^{3n},\ \ldots \}
\]

So, the regular expression representing the language is:

\[
(a^n)^+
\]

---

DFA Construction:

To accept the minimum string \( a^n \), we need a path of \( n \) transitions. For this, we need \(n+1\) states and the last state as final state.
Now, from the final state, create a cycle of length \(n\). Here is an example.

 

---

Hence, the minimum number of states required in the DFA is: \[\boxed{n + 1}\]

 

Answer 3

Given that n is a constant.
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a's except 'ε'.
So DFA will be,

So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.

Answer 4

GATE CS 2011 Video Explanation