Home › GATE CSE › computerscience › Theory 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)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?