Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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^*$?
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$).
$$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\}$.
$\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.
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.
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^*$.
