# Prove a Language is Regular [duplicate]

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.

• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Apr 21 '15 at 0:55
• ... 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). Apr 21 '15 at 1:01
• ... By the way, welcome to the site! Apr 21 '15 at 1:02
• What is your definition of regular language? Apr 21 '15 at 2:50

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