Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

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$

Example

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

$\Sigma^0=\{\epsilon\}$

$\Sigma^1=\Sigma\Sigma^0=\{0,1\}$

$\Sigma^2=\Sigma\Sigma^1=\{00,01,10,11\}$

$\dots$

$\Sigma^*=\{\epsilon,0,1,00,01,10,11,\dots\}$

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

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.