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

## marked as duplicate by D.W.♦, Luke Mathieson, David Richerby, Raphael♦Apr 22 '15 at 8:53

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