# Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular [duplicate]

I have a computer science question: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular

These are all the facts I have been able to gather thus far: an alphabet Σ,

any set L such that

L ⊆ Σ ∗ is called a language over Σ

Fact 1 For any alphabet Σ,

any language over Σ is countable

Languages over Σ Fact 2 For any alphabet Σ , ∅,

there are uncountably many languages over Σ More precisely,

there are exactly C = |R| of languages over any non - empty alphabet Σ Languages over Σ Fact 1 For any alphabet Σ, any language over Σ is countable

Proof By definition, a set is countable if and only if is finite or countably infinite

1. Let Σ = ∅, hence Σ ∗ = {e} and we have two languages ∅, {e} over Σ, both finite, so countable

2. Let Σ , ∅, then Σ ∗ is countably infinite, so obviously any L ⊆ Σ ∗ is finite or countably infinite, hence countable Languages over Σ

Fact 2 For any alphabet Σ , ∅, there are exactly C = |R| of languages over any non - empty alphabet Σ Proof We proved that |Σ ∗ | = ℵ0 By definition L ⊆ Σ ∗ , so there is as many languages over Σ as all subsets of a set of cardinality ℵ0— that is as many as 2 ℵ0 = C

am i on the right track or do i need to rethink? can you please proffer tips on how to slve this if you can

• Welcome to the site. I think your problem is that the facts you gathered are about languages (subsets of $\Sigma^*$), but the question you asked is about showing something is regular. Do you have a definition of regular in your notes? That is the definition you should study and use it to answer the question.
– 6005
Nov 20 '21 at 15:01
• I don't think the proofs of the two facts are necessary in the body of your question. Also please add a bit of formatting of your post (formulæ with $\LaTeX$, better placed line breaks, …) Nov 20 '21 at 15:31
• Golden oldie. Also here: If L is a subset of {0}∗, then how can we show that L∗ is regular?. Nov 20 '21 at 18:50

Hint: Let $$w\in L$$ be the smallest non-empty word. What can you say about the relation between $$L^*$$ and $$w$$? How can you construct one from another?

If $$|L|$$ is finite, the result is trivial (since $$L$$ is regular). Therefore, suppose $$L$$ is infinite. There may be a simpler proof, but I didn't find it.

Consider $$S = \{|u|\mid u\in L\}$$, and $$d = \text{gcd}(S)$$. There exists a finite subset $$S'=\{x_1, x_2, …, x_n\}$$ of $$S$$ such that $$d=\text{gcd}(S')$$. Without loss of generality, suppose $$0 (if $$0$$ is in $$S'$$, we can just remove it). Note that for all $$i\in\{1, …, n\}$$, $$a^{x_i}\in L$$.

Using Bézout's identity, there exist $$a_1, a_2, …, a_n\in\mathbb{Z}$$ such that $$\sum\limits_{i=1}^na_ix_i = d$$.

For convenience, I will suppose that $$d = 1$$ for the remainder of the proof, but it is similar to the general case.

Let $$i_0\in \{1, …, n\}$$ such that $$a_{i_0} = \min\{a_i\mid i\in \{1, …, n\}\}$$, and let $$x = x_1|a_{i_0}|\times \sum\limits_{i=1}^n x_i$$.

Then $$x$$, $$x + \sum\limits_{i=1}^na_ix_i$$, $$x + 2\sum\limits_{i=1}^na_ix_i$$, …, $$x + x_1\sum\limits_{i=1}^na_ix_i$$ are consecutive numbers (since $$\sum\limits_{i=1}^na_ix_i = 1$$), expressed as linear combination with non-negative coefficients of the $$\{x_i\}$$. That means that $$a^x$$, $$a^{x+1}$$, $$a^{x+2}$$, …, $$a^{x+x_1}$$ are words of $$L^*$$. Since $$a^{x_1}\in L$$, that also means that $$\{a^{kx_1}\mid k\in \mathbb{N}\}\subseteq L^*$$. We finally conclude that $$\{a^y\mid y \geqslant x\}\subseteq L^*$$. That means that $$L^*\cup\{a^y\mid y. Since $$\{a^y\mid y < x\}$$ is finite, we conclude that $$L^*$$ is regular.

In the general case, you can also find an integer $$x$$ such that $$L^*\cup \{a^y\mid y< x\} = (\Sigma^d)^*$$. I will let you write the proof by yourself.