Practice free →
HomeGATE CSEcomputerscienceTheory of Computation › The Kleene STAR $L^*$ of a language $L$ is defin…

The Kleene STAR $L^*$ of a language $L$ is defined as

Athe set of all strings $w$ such that $|w| \geq |L|$
B$L \cap \Sigma^*$
C$\{w_1 w_2 \ldots w_k \mid k \geq 0, w_i \in L\}$, i.e. any concatenation of strings from $L$
D$\{w^k \mid k \geq 1, w \in L\}$, exactly one element of $L$ repeated
Answer & Solution
Correct answer: C. $\{w_1 w_2 \ldots w_k \mid k \geq 0, w_i \in L\}$, i.e. any concatenation of strings from $L$
1. Kleene star: $L^*$ is the SMALLEST language containing $L$ and closed under concatenation, including the empty string $\varepsilon$. 2. Formally: $L^* = \bigcup_{k=0}^\infty L^k$, where $L^0 = \{\varepsilon\}$ and $L^k = L \cdot L^{k-1}$ for $k \geq 1$. 3. So $L^*$ contains: $\varepsilon$, every single $w \in L$, every $w_1 w_2$ ($w_i \in L$), and so on. 4. Example: $L = \{a, ab\}$. Then $L^* = \{\varepsilon, a, ab, aa, aab, aba, abab, \ldots\}$. 5. Importantly, $L^*$ always includes $\varepsilon$ (empty string), even if $\varepsilon \notin L$. 6. Options A, B, D are wrong characterisations. _Source: Jeff Erickson, "Models of Computation", §2.1 (Languages and operations)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions