<p>I believe that it's not a research level question.</p>

<p>You can proceed in the following way. First of all, you can prove that for any language $L^* \subseteq 0^{*}$ there exists some $i, j \in \mathbb{N}$ such that $L^* = L_{fin} \cup \{ 0^{j+kn} \; | \; n \in \mathbb{N} \}$ and $L_{fin}$ is a finite language (thus regular). Once you know it, it is easy to construct a proper automaton.</p>

<p>To prove it you can think about elements from $0^*$ as natural numbers and use euclidean algorithm. You can take $k$ as gcd of your set and $y_1, y_2, \ldots y_l$ as some set of generators, such that $k = gcd(y_1, \ldots, y_l)$. To get $j$, you know that there are some non-zero numbers $b_i$, such that $\sum_{i=0}^{n} b_iy_i \; \text{mod} \; y = k$ and take $j = \Pi_{i=0}^l y_i \cdot \sum_{i=0}^{n} b_iy_i$. A language $L_{fin}$ is simply elements from $L^*$ smaller than $j$. </p>

CC BY-SA 4.0
2018-06-05T08:28:03.827Z
2018-06-05T08:28:03.827Z
Bartosz Bednarczyk
<p>Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.<img src="https://i.sstatic.net/6FTSm.jpg" alt="enter image description here"></p>

CC BY-SA 4.0
2018-06-05T10:30:23.363Z
Homework exercises are off-topic here, this site is for research-level questions!
Jan Johannsen
CC BY-SA 4.0
2018-06-05T10:46:50.333Z
It's not homework I was stuck so I asked.
Saurav
<automata-theory><regular-language>
Prove that L* is a regular language
Saurav
# Prove that L* is a regular language

(Asked by: username_0 on 2018-06-05)

Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L\* is regular.![enter image description here](https://i.sstatic.net/6FTSm.jpg)

**Tags:** automata-theory, regular-language

> **Comments:**
> **username_1**: Homework exercises are off-topic here, this site is for research-level questions!  
> **username_0**: It's not homework I was stuck so I asked.  

---

## 1 answers

### Answer by username_2 on 2018-06-05. Score: 1

I believe that it's not a research level question.

You can proceed in the following way. First of all, you can prove that for any language $L^\* \subseteq 0^{\*}$ there exists some $i, j \in \mathbb{N}$ such that $L^\* = L\_{fin} \cup \{ 0^{j+kn} \; | \; n \in \mathbb{N} \}$ and $L\_{fin}$ is a finite language (thus regular). Once you know it, it is easy to construct a proper automaton.

To prove it you can think about elements from $0^\*$ as natural numbers and use euclidean algorithm. You can take $k$ as gcd of your set and $y\_1, y\_2, \ldots y\_l$ as some set of generators, such that $k = gcd(y\_1, \ldots, y\_l)$. To get $j$, you know that there are some non-zero numbers $b\_i$, such that $\sum\_{i=0}^{n} b\_iy\_i \; \text{mod} \; y = k$ and take $j = \Pi\_{i=0}^l y\_i \cdot \sum\_{i=0}^{n} b\_iy\_i$. A language $L\_{fin}$ is simply elements from $L^\*$ smaller than $j$.


---

