patternMinor
Star operation in CS theory
Viewed 0 times
theorystaroperation
Problem
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^*$?
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^*$?
Solution
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.
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.
Context
StackExchange Computer Science Q#9637, answer score: 8
Revisions (0)
No revisions yet.