For a language $L\in\Sigma^*$ we define $$ L^*=\{w\mid \exists k\in \mathbb{N}\cup\{0\}, ∃x_1,...,x_k\in L \ (w=x_1...x_k) \} $$ Let $L$ be a regular language over some alphabet $\Sigma$. Prove that $L^*$ is regular.

  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ Apr 21 '15 at 0:55
  • 5
    $\begingroup$ ... You seem to be asking whether the Kleene star of a regular language is regular. This is a standard result in CS theory that you should be able to find answered in lots of online sites (I searched for "Kleene star" and got over 65000 hits). $\endgroup$ Apr 21 '15 at 1:01
  • 1
    $\begingroup$ ... By the way, welcome to the site! $\endgroup$ Apr 21 '15 at 1:02
  • 1
    $\begingroup$ What is your definition of regular language? $\endgroup$ Apr 21 '15 at 2:50

I have to guess about your definition of a regular language (I can't comment to ask yet...), so I will assume the following:

A language $L$ is regular over an alphabet $\Sigma$ if and only if it can be generated by a regular grammar with terminal symbols $\Sigma$.

We are given that the the language $L$ is regular. Therefore, let $G = (N, \Sigma, P, S)$ be an $\epsilon$-free regular grammar that generates $L$. (Such a grammar can always be constructed by considering any regular grammar that generates $L$, and removing all terminals that only produce $\epsilon$.) We now examine the production process for $L$. We first note that, since any rule is of the form $A \rightarrow a$ or $A \rightarrow aB$, where $A,B \in N$ and $a \in \Sigma$, we have at any point in the process at most one non-terminal at the righthand side of the current sentential form. Secondly, if at any point a rule of the form $A \rightarrow a$ is used, the production process is completed, since the sentential form then only consists of terminal symbols and no further replacement can occur.

Let us now consider rules the form $A \rightarrow a$, and for every such form add a new rule $A \rightarrow aS$. We also add the rule $S \rightarrow \epsilon$. This results in a new regular gammar $G' = (N, \Sigma, P', S)$. It is then straightforward to see that $G'$ generates the language $L^*$, which proves that $L^*$ is indeed regular.

Note that if you were to use the left-hand definition of a regular grammar (only rules of the form $A \rightarrow a$, $A \rightarrow Ba$ or $A \rightarrow \epsilon)$, the proof would be almost the same, adding rules of the form $A \rightarrow Sa$.


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