[Solved]: Prove that languages which contain words whose lengths are multiples of a constant are regular

Problem Detail: 

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

Asked By : Musicode

Answered By : Rick Decker

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21746

3.2K people like this

 Download Related Notes/Documents