Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a question about the regular operation 'star' in computational theory.

IF $A$ is $\{ good , bad \}$ then

$A^* = \{ \varepsilon , good, bad , goodgood, goodbad, badgood , \dots \}$

What is the exact "regular operation" mean then ?

Can we use $^*$ operation only for regular language ? I don't think so.

$L = \{0^n1^n \mid n \ge 0 \}$ is a famous example of a non-regular language, but it seems we can create $L^*$?

share|cite|improve this question

The $^*$ is an operator that takes a language (not only regular languages) $L$ and produces a new language $L^*$ called the Kleene closure of $L$. A language is a set of strings over a finite alphabet (alphabets are commonly denoted by $\Sigma$).

Definition of $L^*$

$$L^*=\bigcup_{i\in \mathbb{N}_0}L^i=L^0\cup L^1\cup L^2\dots$$

Where, $L^0=\{\epsilon\}$ and $L^n=LL^{n-1}$ for $n\gt0$


Let $\Sigma=\{0,1\}$.






In other words, $\Sigma^*$ is the set of all binary strings.

share|cite|improve this answer

The operation you refer to (Kleene star) is an operation on languages (sets of strings). The language doesn't have to be regular at all to apply it. It's relation to regular languages is that it is one of the operations (with concatenatin and union) that define regular languages starting from the empty language, the language containing only the empty string, and the languages made of the strings of length one.

share|cite|improve this answer

You can certainly apply the Kleene star operation on any set, however the regular languages are closed under taking the Kleene star. This means that if a language $L$ is regular, so is $L^*$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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