This is a problem involving the theory of regular languages. I am stuck on this problem and do not know how to solve this type of problem.

Prove that the language $B_n = \{ a^k \mid k \text{ is a multiple of } n \}$ is a regular language for any $n \ge 1$.

Let me describe my thoughts thus far: It is easy to show that for $n=1$, we have $B_1 = \{a\}$.

In other words, a regular expression can easily be built for the value of $n=1$, and thus for any $k$.

  • $\begingroup$ sorry about that i was mixing up similar problems, i will change this asap $\endgroup$ – Musicode Feb 18 '14 at 1:09
  • $\begingroup$ $B_1 = \{a\}^*$. $\endgroup$ – Raphael Feb 18 '14 at 8:14

Since the multiples of $n$ are $0, n, 2n, 3n, \dots$, it's clear that $B_n=\{\epsilon, \mathtt{a}^n, \mathtt{a}^{2n}, \mathtt{a}^{3n}, \dots\}$, in other words the set of all strings that can be made by concatenating arbitrarily many copies of $\mathtt{a}^n$. I'll bet you can find a regular expression denoting that language, for any given value of $n$.


Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation R on strings by the rule that x R y if there is no distinguishing extension for x and y. It is easy to show that R is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes.

The Myhill–Nerode theorem states that L is regular if and only if R has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes in R. In particular, this implies that there is a unique minimal DFA with minimum number of states.

For the above problem, try using congruence relation and partition the set of all strings into k equivalence classes.

References : http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem

  • 1
    $\begingroup$ In this case, Myhill–Nerode is massively, massively more complicated than just producing an automaton. $\endgroup$ – David Richerby Feb 18 '14 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.