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


closed as off-topic by Emil Jeřábek, Jan Johannsen, Hsien-Chih Chang 張顯之, Lev Reyzin Jun 7 '18 at 3:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Jan Johannsen, Hsien-Chih Chang 張顯之, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Homework exercises are off-topic here, this site is for research-level questions! $\endgroup$ – Jan Johannsen Jun 5 '18 at 10:30
  • $\begingroup$ It's not homework I was stuck so I asked. $\endgroup$ – Saurav Jun 5 '18 at 10:46

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


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