3
$\begingroup$

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^*$?

$\endgroup$
6
$\begingroup$

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 finite-length binary strings.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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