Proving a language is regular.

[JamesBwoii]

Hi, I'm back with another question, but the opposite of last time.

The question is:

For each positive integer $n$, let ${L}_{n}$ = { ${a}^{k}$ $|$ $k$ is a multiple of $n$ }
Show that for each $n$ the language ${L}_{n}$ is regular. As far as I understand you cannot use pumping lemma to prove a language is regular.

I assume that leaves me with having to do a NFA, DFA or regular expression as I don't know where to begin to create one of those for this language.

Thanks!

 

[Evgeny.Makarov]

The easiest way to define regular languages is using regular expressions. Can you write a regular expression describing $L_1=\{a^k\mid k\ge0\}=\{a\}^*$?

 

[JamesBwoii]

The easiest way to define regular languages is using regular expressions. Can you write a regular expression describing $L_1=\{a^k\mid k\ge0\}=\{a\}^*$?

Honestly no, I just can't see it. I'm really struggling with this particular problem sheet.

 

[Evgeny.Makarov]

Then you should read the definition and examples of regular expressions, for example, in Wikipedia.

 

[blue_raver22]

Hello,

Thank you for your question. Proving that a language is regular can be done in a few different ways, including using the pumping lemma, constructing a NFA or DFA, or using regular expressions. In this case, we can use the construction of a DFA to prove that ${L}_{n}$ is regular for each positive integer $n$.

First, let's define the alphabet for our language as $\Sigma = \{a\}$, since the language only consists of strings made up of the letter "a". Now, let's construct a DFA that recognizes ${L}_{n}$ for a specific value of $n$. We can start by creating a start state, which will be the initial state of our DFA. Then, we will create $n$ states, each representing a multiple of $n$. We will label each state with the corresponding multiple of $n$. For example, if $n = 3$, our states would be labeled 0, 3, 6, 9, etc. The state labeled 0 will be our accept state, since it represents a multiple of $n$ and therefore belongs to ${L}_{n}$.

Next, we will define the transitions between states. Starting from the start state, we will have a transition on the letter "a" to the state labeled 1. From there, we will have a transition on "a" to the next state labeled 2, and so on until we reach the state labeled $n-1$. From this state, we will have a transition on "a" back to the start state, representing the fact that the string has looped back to a multiple of $n$. This process can be repeated for any value of $n$, resulting in a DFA that recognizes ${L}_{n}$.

In conclusion, we have shown that for each positive integer $n$, the language ${L}_{n}$ is regular by constructing a DFA that recognizes it. This proves that ${L}_{n}$ is regular and can be recognized by a finite automaton. I hope this explanation helps. Let me know if you have any further questions.