Search code examples
algorithmregular-languagefinite-automatacomputation-theory

What is the minimum number of states to recognize this language?


Definition of a language L with alphabet {a} is as follows:

L= { a^{nk} | k > 0,n >0}.

There were four options to this question

k+1

n+1

2^(n+1)

2^(k+1)

k > 0, and n is a positive integer constant


Solution

  • I got the answer

    n is a constant and k is any positive integer.

    For example, if n is given as 3, then the DFA must be able to accept 3a, 6a, 9a, 12a, ..

    To build such a DFA, we need 4 states. ans=(n+1)