Talk:Kleene star

Closure

Isn't closure implicit if we talk about an operation "on M"? (anonymous)

I think closure would be implied by saying operation in M. Tortoise3 12:48, 13 December 2006 (UTC)

Pumping Lemma

The pumping lemmas (regular and context-free) are very important observations in language theory, and the Kleene closure is essential to their use, so I think a link to the pumping lemma would be quite appropriate. Any objections? Aragorn2 09:42, 29 Mar 2005 (UTC)

Definition

The notes that say "0/1 denotes...events" seem to be taken out of context...? Tortoise3 12:18, 11 December 2006 (UTC)

Pronounciation

How is it pronounced?

See here: Stephen Kleene. Hermel (talk) 21:09, 25 January 2009 (UTC)

WikiProject class rating

This article was automatically assessed because at least one WikiProject had rated the article as start, and the rating on other projects was brought up to start class. BetacommandBot 04:13, 10 November 2007 (UTC)

Is $V_{1}$ defined?

It seems to me that $V_{1}$ is left undefined here:

$V_{i+1}=\{wv:w\in V_{i}{\mbox{ and }}v\in V\}\,$ where $i>0\,.$

Shouldn't i say "where $i\geq 0$ " ?

I didn't correct it since I'm new in this area.

User:Nillerdk 13:42, 10 November 2007 (UTC)

Fixed by User:141.162.101.50 User:Nillerdk (talk) 06:17, 25 May 2008 (UTC)

Empty Set

Is the empty string ALWAYS in the Kleene Closure of a set? Even the Kleene closure of the empty set? The "given V0=lambda" on this article is unclear. Thanks

Mangledorf (talk) 04:10, 25 September 2008 (UTC)

Yes, indeed. Just plug the empty set into the definition. (The definition is standard, compare any introductory textbook in automata theory, e.g. Hopcroft/Motwani/Ullman.) Hermel (talk) 21:14, 25 January 2009 (UTC)

Idempotence

I think the article should mention that both the star and plus are idempotent operators, including a proof.

--MedeaMelana (talk) 19:41, 27 June 2009 (UTC)

Asterisk in Kleene plus

The askerisk on $\mathbb {N}$ in the definition of $V^{+}$ implies that the natural numbers do not include $0$. As this isn't explicitly stated and this article is about the Kleene star, using the same asterisk symbol, it might be better to define $V^{+}=\bigcup _{i\in \mathbb {N} ,i>0}V_{i}$. --128.227.113.10 (talk) 22:03, 23 October 2009 (UTC) Shouldn't the Kleene plus have it's own wiki page? DHarlan 18 Dec 2012

Concatenation

Is the phrase $\varnothing \varnothing ^{*}$ shorthand for $\varnothing$ concatenated with $\varnothing ^{*}$? There's no symbol (or lack thereof) defined for set concatenation defined in this article, although I've read elsewhere (e.g. Fundamentals of the theory of computation: principles and practice - Raymond Greenlaw, H. James Hoover - 1998) that $\circ$ should be used:

$\varnothing ^{+}=\varnothing \circ \varnothing ^{*}=\{\}=\varnothing$

… then $V_{2}$ would become $V\circ V$

Xaje (talk) 18:12, 27 October 2009 (UTC)

("Machines, Languages, and Computation", Peter J. Denning, Jack B. Dennis & Joseph E. Qualitz, 1978) uses $\bullet$ or $\cdot$ (hard to be sure which, it's somewhere in-between) for concatenation of both strings and sets of strings. ("Introduction to Formal Grammars", M. Gross & A. Lentin, 1970) calls the concatenation of two languages their product, and it is normal practice in mathematics to leave out the symbol for the product operator. Gross & Lentin state that this product operator is associative but not commutative, and use a superscript to denote powers (multiple concatenations of the set with itself). So I guess no symbol is needed after all, but a clarifying explanation of product/concatenation could be in order. Olli Niemitalo (talk) 14:55, 12 January 2012 (UTC)

I explained the product notation in the example, perhaps not the best place but I didn't want to make big changes. Olli Niemitalo (talk) 18:48, 12 January 2012 (UTC)

Lambda representing empty word?

Isn't ε the standard way of representing the empty word? At least the article on Extended Backus–Naur Form uses ε, not λ... --NetRolller 3D 22:36, 7 March 2010 (UTC) No, see the article on empty word. Hermel (talk) 09:02, 11 March 2010 (UTC)

Original introduction?

In which document was the Kleene star introduced? This should be added to the references. Jodi.a.schneider (talk) 14:11, 16 February 2011 (UTC)

definition in less formal terms

For the educated layman (at least this one), processing the procedural definitions in the lede involves a lot of effort and "I think that works out to...". I'm moving the relatively plain-English definition "the collection of all possible finite-length strings generated from the symbols in V" from Definition and notation up to the lede. Thnidu (talk) 12:52, 30 July 2011 (UTC)

When V*=V ?

 Given a set V define

 V0 = { ε } (the language consisting only of the empty string),

 V1 = V

 and define recursively the set

 Vi+1 = { wv : w ∈ Vi and v ∈ V } for each i>0.

 If V is a formal language, then Vi, the i-th power of the set V, is a shorthand for the concatenation of set V with itself i times.
 That is, Vi can be understood to be the set of all strings that can be represented as the concatenation of i strings in V.

 The definition of Kleene star on V is[2]
  V*=∪i in ℕVi = { ε } ∪ V1 ∪ V2 ∪ V3 ∪ V4 ∪ ....  -- Given as Definition.
  

But if V={ε};

V^*=∪_{i in ℕ}V_i = { ε } ∪ V₁ ∪ V₂ ∪ V₃ ∪ V₄ ∪ ....
= { ε } ∪ V , since V contains only a single empty string, all the possible concatenations lead to only V.

Now, that can be = { ε } ∪ { ε }
= { ε } --> according to the definition of union. Right? Considering V^* is a set of "strings", not a set of "sets and strings".

Or, = { ε } ∪ {{ ε } }
= { ε, { ε } } , if V^* is a set of "sets and strings".
I need to know which of these is the right explanation.

And thus, if V= { ε } => V^*=V=V⁺ ?? -- Ananya, Kolkata (India) --Aaniya B (talk) 07:06, 28 December 2013 (UTC)

Your first explanation is correct: Following the definition, if V={ε} we have V₀ = {ε}, as well as V₁= {ε}. When building the set V₂ according to the recursive definition, the only valid choices are w=ε and v=ε (there are no other elements in V₀ and V₁, respectively), so we have V₂ = {εε} = {ε}. The same applies to V₃ = {εε} = {ε}, and so on. Thus we have V_i = {ε} for all i. Now V^* is the infinite union of all V_i, that is, V^*=∪_{i in ℕ}V_i = { ε } ∪ V₁ ∪ V₂ ∪ V₃ ∪ V₄ ∪ ... = { ε }. Hermel (talk) 10:10, 28 December 2013 (UTC)

Link to Power Set

The Power Set describes the set generated by the Kleene star operation, but neither page references the other. I suggest making the relationship explicit. SMesser (talk) 21:45, 1 December 2014 (UTC)

What do you mean by describes?

Given a set A, its power set P(A) is usually, if not always, disjoint from its Kleene star A^*, since the former contains sets while the latter contains strings, which are two quite different kinds of mathematical objects. For example, if A = { 0,1 } is the set of binary digit symbols, then P(A) = { {}, {0}, {1}, {0,1} } is a set consisting of 4 members, while A^* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, ... } is the infinite set of all binary numbers (leading zeroes allowed). Note that e.g. 01 and 10 are different strings, but {0,1} and {1,0} and {0,0,1} and {0,1,1,0} all denote the same set. So I can't see a correspondance between power set and Kleene star.

Maybe the article isn't sufficiently clear in that point and should be improved? - Jochen Burghardt (talk) 12:33, 2 December 2014 (UTC)

"V*" listed at Redirects for discussion

A discussion is taking place to address the redirect V*. The discussion will occur at Wikipedia:Redirects for discussion/Log/2020 May 9#V* until a consensus is reached, and readers of this page are welcome to contribute to the discussion. 1234qwer1234qwer4 (talk) 16:58, 9 May 2020 (UTC)

Contradicts Wikipedia article about Cartesian product of sets

One sentence includes this phrase:

"... concatenation is an associative and noncommutative product, sharing these properties with the Cartesian product of sets."

But the Wikipedia article Cartesian product states that Cartesian product as defined in set theory is not associative:

"Strictly speaking, the Cartesian product is not associative (unless one of the involved sets is empty).

$(A\times B)\times C\neq A\times (B\times C)$".

This contradiction ought to be resolved by someone knowledgeable about the subject.50.234.60.130 (talk) 14:15, 23 December 2020 (UTC)

Thanks for noticing! Indeed, the sets $(A\times B)\times C$ and $A\times (B\times C)$ are usually different. However, they also are always isomorphic: $f:((A\times B)\times C)\to (A\times (B\times C))$, defined by $f(x)=(\pi _{l}(\pi _{l}(x)),(\pi _{r}(\pi _{l}(x)),\pi _{r}(x)))$, i.e. such that $f(((a,b),c))=(a,(b,c))$ is a bijection. Mathematicians often "confuse" being equal and being isomorphic. So, not-so-strictly speaking, $(A\times B)\times C$ and $A\times (B\times C)$ are equal. The article Cartesian product itself tacitly relies on this "sloppy" language when it uses products of more than 2 sets; e.g. "$X_{1}\times \ldots \times X_{n}$" in section Cartesian product#Cartesian products of several sets presupposes that paranthezation doesn't really matter; it says that the product "can be identified" with its leftmost-possible paranthezation, this "identification" just employs an isomorphism similar to my above example. — I'll try to come up with a note along the above lines and add it to the article Cartesian product. - Jochen Burghardt (talk) 17:10, 23 December 2020 (UTC)

On second thought, a similar argument would apply to commutativity: $A\times B$ and $B\times A$, too, are usually different, but always isomorphic.

As a result, I now consider the analogy to Cartesian product as misleading. If there is no objection, I'll remove it from Kleene star#Examples. - Jochen Burghardt (talk) 11:09, 26 December 2020 (UTC)

 Done I removed the phrase, but didn't make any further changes. - Jochen Burghardt (talk) 14:07, 2 January 2021 (UTC)