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

  • $\begingroup$ Homework exercises are off-topic here, this site is for research-level questions! $\endgroup$ 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.