edited by
17,380 views
62 votes
62 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}$
edited by

2 Answers

Best answer
48 votes
48 votes

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

edited by
5 votes
5 votes

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:

Related questions

36 votes
36 votes
6 answers
1
go_editor asked Sep 29, 2014
10,713 views
A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below.Which of the following finite state machines is a valid minimal $\tex...
36 votes
36 votes
4 answers
2
go_editor asked Sep 29, 2014
9,196 views
Consider the languages $L1, \:L2 \:and \: L3$ as given below.$L1=\{0^p 1^q \mid p, q \in N\}, \\ L2 = \{0^p 1^q \mid p, q \in N \:and \:p=q\} \: and, \\ L3 = \{0^p 1^q 0^...
27 votes
27 votes
3 answers
3
go_editor asked Apr 23, 2016
8,415 views
Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$
38 votes
38 votes
5 answers
4
Akash Kanase asked Feb 12, 2016
15,597 views
The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.