HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Star operation in CS theory

Submitted by: @import:stackexchange-cs··
0
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^*$?

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.

Context

StackExchange Computer Science Q#9637, answer score: 8

Revisions (0)

No revisions yet.