1
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – 6005
    Nov 20 '21 at 15:01
  • $\begingroup$ 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, …) $\endgroup$
    – Nathaniel
    Nov 20 '21 at 15:31
  • $\begingroup$ Golden oldie. Also here: If L is a subset of {0}∗, then how can we show that L∗ is regular?. $\endgroup$ Nov 20 '21 at 18:50
0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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<x_1<x_2<…<x_n$ (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<x\} = \Sigma^*$. 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.

$\endgroup$

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